第五章：栈与栈的应用

栈这个东西，说白了就是一种「后进先出」的数据结构。我刚开始学的时候觉得它太简单了，不就是个受限的线性表吗？直到后来做嵌入式协议栈解析，才发现栈的用处远比想象中大得多。

你想想看，函数调用、括号匹配、表达式求值，这些场景背后都有栈的影子。今天我们就把它彻底讲透。

5.1 栈的顺序存储与链式存储

栈有两种实现方式：顺序栈和链式栈。我个人习惯在嵌入式开发中用顺序栈，因为内存可控、访问快。但如果你不知道数据量有多大，链式栈更灵活。

5.1.1 顺序栈

顺序栈就是用数组实现的。核心就三个东西：一个数组、一个栈顶指针、一个容量上限。

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;  // 栈顶指针，-1表示空栈
} SeqStack;

入栈操作：

int push(SeqStack *s, int value) {
    if (s->top == MAX_SIZE - 1) {
        return -1;  // 栈满
    }
    s->data[++s->top] = value;
    return 0;
}

出栈操作：

int pop(SeqStack *s, int *value) {
    if (s->top == -1) {
        return -1;  // 栈空
    }
    *value = s->data[s->top--];
    return 0;
}

5.1.2 链式栈

链式栈就是用链表实现的。入栈相当于头插法，出栈相当于删除头节点。

typedef struct Node {
    int data;
    struct Node *next;
} StackNode;

typedef struct {
    StackNode *top;  // 栈顶指针
} LinkedStack;

入栈：

void push(LinkedStack *s, int value) {
    StackNode *node = (StackNode*)malloc(sizeof(StackNode));
    node->data = value;
    node->next = s->top;
    s->top = node;
}

出栈：

int pop(LinkedStack *s, int *value) {
    if (s->top == NULL) return -1;
    StackNode *temp = s->top;
    *value = temp->data;
    s->top = temp->next;
    free(temp);
    return 0;
}

5.2 括号匹配检测

这个场景太经典了。写代码时括号不匹配，编译器报错，你一行一行找？用栈几行代码就搞定。

思路很简单：

• 遇到左括号（'('、'{'、'['）就入栈
• 遇到右括号就出栈，检查是否匹配
• 最后栈为空则匹配成功

int isMatching(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '{' && right == '}') ||
           (left == '[' && right == ']');
}

int checkBrackets(const char *expr) {
    SeqStack stack;
    stack.top = -1;
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        if (ch == '(' || ch == '{' || ch == '[') {
            push(&stack, ch);
        } else if (ch == ')' || ch == '}' || ch == ']') {
            int topChar;
            if (pop(&stack, &topChar) != 0) {
                return 0;  // 栈空，右括号多余
            }
            if (!isMatching(topChar, ch)) {
                return 0;  // 不匹配
            }
        }
    }
    return stack.top == -1;  // 栈空则匹配
}

5.3 表达式求值：中缀转后缀

我们平时写的表达式叫中缀表达式，比如 3 + 5 * 2。计算机直接算很麻烦，因为有优先级和括号。但后缀表达式（也叫逆波兰表达式）就简单多了，从左到右扫一遍就能算。

中缀转后缀的规则：

1. 遇到操作数直接输出
2. 遇到运算符，如果栈为空或栈顶为 '('，直接入栈
3. 否则，比较优先级：当前运算符优先级高于栈顶，入栈；否则出栈并输出，直到满足入栈条件
4. 遇到 '(' 入栈，遇到 ')' 出栈直到 '('
5. 最后将栈中所有运算符出栈

int priority(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

void infixToPostfix(const char *infix, char *postfix) {
    SeqStack stack;
    stack.top = -1;
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];
        if (isdigit(ch)) {
            postfix[j++] = ch;
        } else if (ch == '(') {
            push(&stack, ch);
        } else if (ch == ')') {
            int top;
            while (pop(&stack, &top) == 0 && top != '(') {
                postfix[j++] = top;
            }
        } else {  // 运算符
            int top;
            while (stack.top != -1 && peek(&stack, &top) == 0 
                   && top != '(' && priority(top) >= priority(ch)) {
                pop(&stack, &top);
                postfix[j++] = top;
            }
            push(&stack, ch);
        }
    }
    
    int top;
    while (pop(&stack, &top) == 0) {
        postfix[j++] = top;
    }
    postfix[j] = '\0';
}

5.4 后缀表达式求值

后缀表达式求值就更直接了：

1. 遇到数字入栈
2. 遇到运算符，出栈两个数字，计算结果再入栈
3. 最后栈顶就是结果

int evalPostfix(const char *postfix) {
    SeqStack stack;
    stack.top = -1;
    
    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];
        if (isdigit(ch)) {
            push(&stack, ch - '0');
        } else {
            int a, b;
            pop(&stack, &b);  // 注意顺序：先出栈的是右操作数
            pop(&stack, &a);
            switch (ch) {
                case '+': push(&stack, a + b); break;
                case '-': push(&stack, a - b); break;
                case '*': push(&stack, a * b); break;
                case '/': push(&stack, a / b); break;
            }
        }
    }
    
    int result;
    pop(&stack, &result);
    return result;
}

5.5 本章知识体系

下面这张图把栈的核心逻辑串起来了，你看一遍就能记住：

栈的核心就一句话：后进先出。不管是顺序栈还是链式栈，入栈出栈都是 O(1) 的操作，效率非常高。括号匹配和表达式求值，说白了就是利用了这个特性。

---

公众号:蓝海资料掘金营，微信deep3321