7.栈

7.栈

明廷盛 嘻嘻😁
  2025-03-27 11:39:01 2025-03-27 11:39:01 Created   2025-03-31 14:07 2025-03-31 14:07 Updated   3.4k Words  17 Mins  

第一章 自测&关键词回顾

视频

计算后缀表达式

  1. 遇到数字, 直接入栈
  2. 遇到符号, 弹出两个数字, 计算后, 再将结果入栈
    • 注意❗: 第二个弹出的操作数 操作符 第一个弹出的操作数 是反的(因为在将中缀表达式转换为后缀表达式的过程中，操作数的顺序被保留了, 只是操作符的顺序变了)

      中转后
  3. 如果遇到了数字, 直接变后缀串; 如果是符号; 看优先级(处理见下图)
  4. 如果遇到了左括号, 入栈; 如果右括号; 出栈(直到栈内的左括号出栈为止)
  5. 最后, 将剩余的弹出即可

第二章 手撕

第一节 链表实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 单链表(有头,头节点存储栈的元素个数) 实现 栈
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

typedef int DataType;
typedef struct LinkStackNode {
    DataType data;
    struct LinkStackNode *next;
} LinkStackNode;

// 创建栈
LinkStackNode *initStack();
// 销毁
void destroy(LinkStackNode *stack);
// 遍历
void traverse(LinkStackNode *stack);
// 入栈
void push(LinkStackNode *stack, DataType data);
// 出栈
void pop(LinkStackNode *stack);
// 获取栈顶元素
DataType top(LinkStackNode *stack);
// 判空
bool empty(LinkStackNode *stack);
// 栈元素个数(突然发现,用有头的会好点😅)
int size(LinkStackNode *stack);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "stack.h"

// 创建栈
LinkStackNode *initStack() {
    // 初始没有数值, 返回表头即可
    LinkStackNode *stackHead = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    stackHead->data = 0;
    stackHead->next = NULL;
    return stackHead;
}
// 入栈
void push(LinkStackNode *stack, DataType data) {
    LinkStackNode *newNode = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    newNode->data = data;
    // 头插法
    newNode->next = stack->next;
    stack->next = newNode;

    stack->data++;  // 栈的大小++
}
// 销毁
void destroy(LinkStackNode *stack) {
    // 之前链表那块实现,都是借用2个临时变量;这里只用一个试试;
    while (stack->next) {
        //  这里相当于一直"头删"
        LinkStackNode *temp = stack->next;
        stack->next = stack->next->next;
        free(temp);
    }
    free(stack);  // 最后把"哨兵头"删掉
}
// 遍历
void traverse(LinkStackNode *stack) {
    LinkStackNode *pmove = stack->next;
    while (pmove) {
        printf("%d\n", pmove->data);
        pmove = pmove->next;
    }
    printf("End Size:%d\n", stack->data);
}
// 出栈
void pop(LinkStackNode *stack) {
    assert(stack->data && "illegal!!!! stack is empty!");
    // 头删
    LinkStackNode *temp = stack->next;  // 存储起来,等会释放
    stack->next = stack->next->next;    // 已经保证不为空了
    stack->data--;                      // 栈的大小--
    free(temp);
}
// 获取栈顶元素
DataType top(LinkStackNode *stack) {
    assert(stack->data && "illegal!!!! stack is empty!");
    return stack->next->data;
}
// 判空
bool empty(LinkStackNode *stack) { return stack->data==0; }
// 栈元素个数(突然发现,用有头的会好点😅)
int size(LinkStackNode *stack) { return stack->data; }

把你写的接口, 丢上去测测, AC就手搓的没问题 题目LINK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include "stack.h"

// https://www.luogu.com.cn/problem/U295781
void oj() {
    int n;
    scanf("%d", &n);

    LinkStackNode *stack = initStack();
    while (n--) {
        char instruction[100];
        scanf("%s", instruction);

        // 1.push x – 向栈顶插入一个数 x ；
        if (!strcmp(instruction, "push")) {
            int x;
            scanf("%d", &x);
            push(stack, x);
        }
        // 2.pop – 从栈顶弹出一个数；
        else if (!strcmp(instruction, "pop")) {
            pop(stack);
        }
        // 3.empty – 判断栈是否为空；
        else if (!strcmp(instruction, "empty")) {
            printf("%s\n", empty(stack) ? "YES" : "NO");
        }
        // 4.query – 查询栈顶元素。
        else if (!strcmp(instruction, "query")) {
            printf("%d\n", top(stack));
        }
    }
    destroy(stack);
}

int main() {
    oj();

    return 0;
}

第二节 数组实现栈

把你写的接口, 丢上去测测, AC就手搓的没问题 题目LINK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DataType int

typedef struct Stack {
    DataType *stack;
    int head;  // 永远指向栈顶
    int maxSize;
} Stack;

// 一.初始化
Stack *init(int maxSize) {
    Stack *myStack = (Stack *)malloc(sizeof(Stack));
    myStack->stack = (DataType *)malloc(sizeof(DataType) * maxSize);
    myStack->maxSize = maxSize;
    myStack->head = -1;
    return myStack;
}
// 二.压栈
void push(Stack *myStack, DataType data) {
    assert(!(myStack->head == myStack->maxSize - 1) && "Stack is over maxSize!");
    myStack->stack[++myStack->head] = data;
}
// 三.出栈
void pop(Stack *myStack) {
    assert(!(myStack->head == -1) && " illegal stack is empty");
    myStack->head--;
}
// 四.遍历
void traverse(Stack *myStack) {
    for (int i = myStack->head; i >= 0; i--) {
        printf("%d\n", myStack->stack[i]);
    }
    puts("END");
}
// 五.取栈顶元素
DataType top(Stack *myStack) {
    return myStack->stack[myStack->head];
}
// 六.判空
bool empty(Stack *myStack) {
    return myStack->head == -1;
}
// 七.栈的大小
int size(Stack *myStack) {
    return myStack->head + 1;
}

void oj(void);  // https://www.luogu.com.cn/problem/U295781
int main() {
    oj();
    return 0;
}

void oj(void) {
    int n;
    scanf("%d", &n);
    Stack *stack = init(1000);
    while (n--) {
        char instruction[100];
        scanf("%s", instruction);
        // 1.push x – 向栈顶插入一个数 x ；
        if (!strcmp(instruction, "push")) {
            int x;
            scanf("%d", &x);
            push(stack, x);
        }
        // 2.pop – 从栈顶弹出一个数；
        else if (!strcmp(instruction, "pop")) {
            pop(stack);
        }
        // 3.empty – 判断栈是否为空；
        else if (!strcmp(instruction, "empty")) {
            printf("%s\n", empty(stack) ? "YES" : "NO");
        }
        // 4.query – 查询栈顶元素。
        else if (!strcmp(instruction, "query")) {
            printf("%d\n", top(stack));
        }
    }
}

第三章 相关应用

第一节 括号匹配问题

力扣: 有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define N 10100
char stack[N];
int top = -1;
char leftParen[] = {'(', '[', '{'};
char rightParen[] = {')', ']', '}'};
/** 判断另一半的括号
 * aim: 栈中弹出的括号
 * x: 右括号
 */
bool isApart(char aim, char x) {
    // 1.如果x是左括号, 一定不对 2.如果x和aim不匹配, 也不对
    for (int i = 0; i < SIZE(leftParen); i++) {
        if (x == rightParen[i] && aim == leftParen[i]) {
            return true;
        }
    }
    return false;
}

bool isValid(char *s) {
    top = -1;
    for (int i = 0; i < strlen(s); i++) {
        // 判断左右括号(没有set数据结构)
        int flag = 0;  // 1表示是左括号, 0表示是右括号
        for (int j = 0; j < SIZE(leftParen); j++) {
            // case1: 左括号
            if (leftParen[j] == s[i]) {
                stack[++top] = s[i];
                flag = 1;
                break;
            }
        }
        // case2: 右括号
        if (top==-1||(!flag && !isApart(stack[top--], s[i])))
            return false;
    }
    return top==-1;
}

第二节 表达式求值

3.2.1 中缀表达式和后缀表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/**在"栈"的应用中,都用数组栈,简单封装 */
// 1. 计算算术表达式
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define N 1000

char stack[N];  // 栈
int head = -1;

int isOperator(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;  // 1级操作符
        case '*':
        case '/':
            return 2;  // 2级操作符
        default:
            return -1;  // 不是操作符
    }
}

// 1.中缀表达式=>后缀表达式 (原始)
char *convertInfix2Postfix(char *infixExpression) {
    char *postfixExpression = (char *)malloc(sizeof(char) * N);
    char *pmove = postfixExpression;

    int i = 0;
    while (i < strlen(infixExpression)) {
        // case1:如果是数字,直接写入"后缀表达式"
        if (isdigit(infixExpression[i])) {
            // STEP1:读取完整数字
            while (isdigit(infixExpression[i])) {
                *pmove++ = infixExpression[i++];  // 等价于先赋值, 后将pmove++==>*pmove = infixExpression[i++]; pmove++;
            }
            // STEP2:添加空格
            *pmove++ = ' ';
            i++;  // 跳过(读取)空格
        } else {
            switch (infixExpression[i]) {
                case '(':  // case2:是(括号
                    stack[++head] = infixExpression[i];
                    break;
                case ')':  // case3:是)括号
                    while (stack[head] != '(') {
                        *pmove++ = stack[head--];
                        *pmove++ = ' ';  // 补空格
                    }
                    head--;  // 弹出'(',但不写入"后缀表达式"
                    break;
                default:  // case4:如果是操作符
                    // 请大哥出来(如果有); 否则就不会执行while,相当于自己直接进去
                    while (head != -1 && isOperator(stack[head]) >= isOperator(infixExpression[i])) {
                        *pmove++ = stack[head--];  // 读操作符
                        *pmove++ = ' ';            // 补空格
                    }
                    // 自己再进去
                    stack[++head] = infixExpression[i];
            }
            i += 2;  // 略过当前操作符及其后面的空格
        }
    }

    // 剩余的依次弹出,并写入
    while (head != -1) {
        *pmove++ = stack[head--];
        *pmove++ = ' ';  // 补空格
    }

    *pmove = '\0';  // 手动补一个\0

    return postfixExpression;
}

void testConversion(char *infixExpression, char *expectedPostfix) {
    char *postfixExpression = convertInfix2Postfix(infixExpression);
    printf("中缀表达式: %s\n", infixExpression);
    printf("转换后的后缀表达式: %s\n", postfixExpression);
    printf("期望的后缀表达式: %s\n", expectedPostfix);

    if (strcmp(postfixExpression, expectedPostfix) == 0) {
        printf("测试通过 ✓\n\n");
    } else {
        printf("测试失败 ✗\n\n");
    }

    // free(postfixExpression);  // 假设你的函数使用了动态内存分配
}

int main() {
    // 测试用例
    testConversion("3 + 4", "3 4 + ");
    testConversion("3 + 4 - 2", "3 4 + 2 - ");
    testConversion("3 + 4 * 2", "3 4 2 * + ");
    testConversion("( 3 + 4 ) * 2", "3 4 + 2 * ");
    testConversion("( ( 3 + 4 ) * 2 )", "3 4 + 2 * ");
    testConversion("9 + ( 3 - 1 ) * 3 + 10 / 2", "9 3 1 - 3 * + 10 2 / + ");
    testConversion("5", "5 ");
    testConversion("12 + 34", "12 34 + ");
    testConversion("1 + 2 * 3 / 4 - 5", "1 2 3 * 4 / + 5 - ");
    testConversion("1 - 2 - 3", "1 2 - 3 - ");
    testConversion("", "");

    return 0;
}

这个版本方便理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 1.中缀表达式=>后缀表达式 (原始)
char *convertInfix2Postfix(char *infixExpression) {
    char *postfixExpression = (char *)malloc(sizeof(char) * N);
    char *pmove = postfixExpression;

    int i = 0;
    while (i < strlen(infixExpression)) {
        // case1:如果是数字,直接写入"后缀表达式"
        if (isdigit(infixExpression[i])) {
            // STEP1:读取完整数字
            while (isdigit(infixExpression[i])) {
                *pmove++ = infixExpression[i++];  // 等价于先赋值, 后将pmove++==>*pmove = infixExpression[i++]; pmove++;
            }
            // STEP2:添加空格
            *pmove++ = ' ';
            i++;  // 跳过(读取)空格
        }
        // case2:如果是操作符
        else if (isOperator(infixExpression[i]) != -1) {
            if (head == -1)
                stack[++head] = infixExpression[i];
            else {
                // 把小弟"踩在"下面
                if (isOperator(stack[head]) < isOperator(infixExpression[i])) {
                    stack[++head] = infixExpression[i];
                }
                // 请大哥出来后,自己再进去
                else {
                    // 请大哥出来
                    while (head != -1 && isOperator(stack[head]) >= isOperator(infixExpression[i])) {
                        *pmove++ = stack[head--];  // 读操作符
                        *pmove++ = ' ';            // 补空格
                    }
                    // 自己再进去
                    stack[++head] = infixExpression[i];
                }
            }
            i += 2;  // 略过当前操作符及其后面的空格
        }
        // case3:是(括号
        else if (infixExpression[i] == '(') {
            stack[++head] = infixExpression[i];
            i += 2;
        }
        // case4:是)括号
        else if (infixExpression[i] == ')') {
            while (stack[head] != '(') {
                *pmove++ = stack[head--];
                *pmove++ = ' ';  // 补空格
            }
            head--;  // 弹出'(',但不写入"后缀表达式"
            i += 2;
        }
    }
    while (head != -1) {
        *pmove++ = stack[head--];
        *pmove++ = ' ';  // 补空格
    }

    *pmove = '\0';  // 手动补一个\0

    return postfixExpression;
}

力扣: 基础计算器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
// 1. 计算算术表达式
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 300010
char stack[N];      // 中=>后的栈
int calcuStack[N];  // 计算"后缀表达式"的栈
int head = -1;
// https://www.luogu.com.cn/problem/P1175
// https://leetcode.com/problems/basic-calculator/solutions/1457045/c-explained-stacks-beginner-friendly-easy-to-understand/  [√]
// 获取"操作符"优先级; 如果不是字符返回-1
int isOperator(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;  // 1级操作符
        case '*':
        case '/':
            return 2;  // 2级操作符
        default:
            return -1;  // 不是操作符
    }
}

char *preProcessing(char *infixExpression) {
    // 1-(    -2) ===>  1-(     0-2)
    char *newExpression = (char *)malloc(sizeof(char) * N);
    int flag =1;  // flag=1 表示前一个为 +-()' '
    int j = 0;
    for (int i = 0; i < strlen(infixExpression); i++, j++) {
        if (infixExpression[i] == ' ') {  // 顺便把空格去了
            j--;
            continue;
        }
        if (infixExpression[i] == '-' && flag)
            newExpression[j++] = '0';
        newExpression[j] = infixExpression[i];
        flag = (infixExpression[i] == '-' || infixExpression[i] == '+' || infixExpression[i] == '(');
    }
    printf("%s\n", newExpression);
    newExpression[j] = '\0';
    return newExpression;
}

// 1.中缀表达式=>后缀表达式 (抽象版)
char *convertInfix2Postfix(char *infixExpression) {
    infixExpression = preProcessing(infixExpression);
    head = -1;
    char *postfixExpression = (char *)malloc(sizeof(char) * N);
    char *pmove = postfixExpression;

    int i = 0;
    while (i < strlen(infixExpression)) {
        if (infixExpression[i] == ' ') {
            i++;
            continue;
        }
        // case1:如果是数字,直接写入"后缀表达式"
        if (isdigit(infixExpression[i])) {
            // STEP1:读取完整数字
            while (isdigit(infixExpression[i])) {
                *pmove++ = infixExpression[i++];  // 等价于先赋值, 后将pmove++==>*pmove = infixExpression[i++]; pmove++;
            }
            // STEP2:添加空格
            *pmove++ = ' ';
        } else {
            switch (infixExpression[i]) {
                case '(':  // case2:是(括号
                    stack[++head] = infixExpression[i];
                    break;
                case ')':  // case3:是)括号
                    while (stack[head] != '(') {
                        *pmove++ = stack[head--];
                        *pmove++ = ' ';  // 补空格
                    }
                    head--;  // 弹出'(',但不写入"后缀表达式"
                    break;
                default:  // case4:如果是操作符
                    // 请大哥出来(如果有); 否则就不会执行while,相当于自己直接进去
                    while (head != -1 && isOperator(stack[head]) >= isOperator(infixExpression[i])) {
                        *pmove++ = stack[head--];  // 读操作符
                        *pmove++ = ' ';            // 补空格
                    }
                    // 自己再进去
                    stack[++head] = infixExpression[i];
            }
            i++;
        }
    }

    // 剩余的依次弹出,并写入
    while (head != -1) {
        *pmove++ = stack[head--];
        *pmove++ = ' ';  // 补空格
    }

    *pmove = '\0';  // 手动补一个\0

    return postfixExpression;
}

// 计算指定"操作符"计算后的结果
int myCalculate(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}
// 2.计算后缀表达式 (9 3 1 - 3 * + 10 2 / +)
int executePostfixExp(char *postfixExpress) {
    head = -1;  // 清空栈
    int i = 0;
    while (i < strlen(postfixExpress)) {
        // case1:如果是数字
        if (isdigit(postfixExpress[i])) {
            char temp[100] = "";
            while (isdigit(postfixExpress[i])) {
                char partNum[2];
                partNum[0] = postfixExpress[i++];
                partNum[1] = '\0';  // 这样转为字符串
                strcat(temp, partNum);
            }
            calcuStack[++head] = atoi(temp);
            i++;  // 跳过空格
        } else {
            int b = calcuStack[head--];  // 注意次序(是反的)
            int a = calcuStack[head--];
            char op = postfixExpress[i];
            calcuStack[++head] = myCalculate(a, b, op);
            i += 2;  // 跳过"操作符"和"空格"
        }
    }
    return calcuStack[head--];
}

int calculate(char *s) {
    char *postfixExpression = convertInfix2Postfix(s);
    // printf("%s\n", postfixExpression);
    int ans = executePostfixExp(postfixExpression);
    return ans;
}

int main() {
    char infixExpression[N];           //  2-1 + 2
    scanf("%[^\n]", infixExpression);  // TODO %[^\n] 是 C 语言 scanf 的扫描集（scanset）用法
    getchar();                         // 吸收输入缓冲区的换行符
    char *postfixExpression = convertInfix2Postfix(infixExpression);
    printf("%s\n", postfixExpression);
    int ans = executePostfixExp(postfixExpression);
    printf("%d", ans);
    return 0;
}

3.2.2 中缀表达式和前缀表达式

这个考的少(没考过)

  1. 转化: ①翻转中缀表达式, 注意如果’(‘要变为’)’, 反之亦然; ②然后像处理中转后的方式一样, 处理翻转后的前缀表达式
  2. 计算: ①处理和计算后缀一样 ②只是从i=strelen(perfixExpression)-1开始遍历(从前缀表达式的字符串末尾开始计算)
  3. 其他: 两个都可以用来对表达式求值, 推荐后缀表达式的求值方式

第四章 上手真题

第五章 比赛怎么用

  • Title: 7.栈
  • Author: 明廷盛
  • Created at : 2025-03-27 11:39:01
  • Updated at : 2025-03-31 14:07:00
  • Link: https://blog.20040424.xyz/2025/03/27/🏫考研/第一部分 数据结构/7.栈/
  • License: All Rights Reserved © 明廷盛
On this page
7.栈
  1. 第一章 自测&关键词回顾
  2. 第二章 手撕
    1. 第一节 链表实现栈
    2. 第二节 数组实现栈
  3. 第三章 相关应用
    1. 第一节 括号匹配问题
    2. 第二节 表达式求值
  4. 第四章 上手真题
  5. 第五章 比赛怎么用