栈与队列（一）：栈的定义与抽象数据类型、顺序栈的实现、链式栈的实现、栈的应用（括号匹配、表达式求值）

大家好，欢迎来到这一讲。今天咱们聊聊栈——这个在计算机世界里无处不在，却又低调到不行的数据结构。

说实话，我刚开始学C语言那会儿，觉得栈不就是个“后进先出”的玩意儿吗？有啥好讲的。直到后来做嵌入式项目，写了一个递归解析JSON的模块，结果栈溢出把整个系统搞崩了……嗯，从那以后，我再也不敢小看栈了。

你想想看，函数调用、中断处理、表达式求值、括号匹配，哪个离得开栈？说白了，栈就是计算机系统里的“后悔药”——你最后放进去的东西，最先能拿出来。

1. 栈的定义与抽象数据类型

栈，说白了就是一种操作受限的线性表。它只允许在一端进行插入和删除操作，这一端叫栈顶，另一端叫栈底。

我习惯用一个比喻来理解栈：就像一摞盘子。你洗好一个盘子，就放在最上面；要用的时候，也是从最上面拿。这就是典型的后进先出（LIFO, Last In First Out）。

栈的抽象数据类型（ADT）其实很简单，核心操作就这几个：

• InitStack(&S)：初始化一个空栈
• Push(&S, x)：将元素x压入栈顶
• Pop(&S, &x)：弹出栈顶元素，赋值给x
• GetTop(S, &x)：读取栈顶元素，但不弹出
• StackEmpty(S)：判断栈是否为空
• StackLength(S)：返回栈中元素个数

2. 顺序栈的实现

顺序栈，就是用数组来实现的栈。说白了，就是一块连续的内存空间，加上一个栈顶指针（通常是一个整数下标）。

我记得有一次做嵌入式协议栈，内存紧张得要命，我就用顺序栈来管理嵌套的协议头。为什么？因为顺序栈访问快、开销小，适合资源受限的环境。

来看代码：

#define MAXSIZE 100  // 栈的最大容量

typedef struct {
    int data[MAXSIZE];  // 存放栈元素
    int top;            // 栈顶指针，初始为-1
} SeqStack;

// 初始化
void InitStack(SeqStack *S) {
    S->top = -1;
}

// 判断栈空
int StackEmpty(SeqStack *S) {
    return S->top == -1;
}

// 入栈
int Push(SeqStack *S, int x) {
    if (S->top == MAXSIZE - 1) {
        return 0;  // 栈满，返回失败
    }
    S->data[++S->top] = x;
    return 1;
}

// 出栈
int Pop(SeqStack *S, int *x) {
    if (StackEmpty(S)) {
        return 0;  // 栈空，返回失败
    }
    *x = S->data[S->top--];
    return 1;
}

// 取栈顶
int GetTop(SeqStack *S, int *x) {
    if (StackEmpty(S)) {
        return 0;
    }
    *x = S->data[S->top];
    return 1;
}

3. 链式栈的实现

链式栈，就是用链表来实现的栈。它没有容量限制（只要内存够），适合元素个数不确定的场景。

你想想看，如果我要处理一个深度不确定的递归调用，用顺序栈就可能溢出。这时候链式栈就派上用场了——动态分配，随用随取。

链式栈的实现思路：把链表的头部当作栈顶，每次入栈就是在头部插入节点，出栈就是删除头部节点。这样入栈和出栈的时间复杂度都是O(1)。

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

typedef struct {
    StackNode *top;  // 栈顶指针
    int count;       // 栈中元素个数
} LinkStack;

// 初始化
void InitStack(LinkStack *S) {
    S->top = NULL;
    S->count = 0;
}

// 入栈
int Push(LinkStack *S, int x) {
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if (p == NULL) return 0;  // 内存分配失败
    p->data = x;
    p->next = S->top;
    S->top = p;
    S->count++;
    return 1;
}

// 出栈
int Pop(LinkStack *S, int *x) {
    if (S->top == NULL) return 0;  // 栈空
    StackNode *p = S->top;
    *x = p->data;
    S->top = p->next;
    free(p);
    S->count--;
    return 1;
}

// 取栈顶
int GetTop(LinkStack *S, int *x) {
    if (S->top == NULL) return 0;
    *x = S->top->data;
    return 1;
}

4. 栈的应用：括号匹配

括号匹配，是栈最经典的应用之一。你写代码的时候，编译器是怎么知道你的括号有没有配对的？答案就是——栈。

算法思路其实很简单：

1. 遍历字符串，遇到左括号（'('、'['、'{'）就入栈
2. 遇到右括号（')'、']'、'}'）就检查栈顶是否匹配
3. 如果匹配，弹出栈顶；如果不匹配，直接报错
4. 遍历结束后，如果栈为空，说明所有括号都匹配

来看代码实现：

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

int checkBrackets(char *expr) {
    SeqStack S;
    InitStack(&S);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            Push(&S, ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (StackEmpty(&S)) {
                return 0;  // 右括号多余
            }
            char top;
            GetTop(&S, &top);
            if (!isMatching(top, ch)) {
                return 0;  // 不匹配
            }
            Pop(&S, &top);
        }
    }
    
    return StackEmpty(&S);  // 栈空则全部匹配
}

5. 栈的应用：表达式求值

表达式求值，说白了就是让计算机像人一样计算数学表达式。比如 3 + 4 * 2 - 1，人知道先乘除后加减，但计算机怎么知道？

这里要用到两个栈：一个操作数栈，一个运算符栈。算法是经典的算符优先法：

1. 遍历表达式，遇到数字就压入操作数栈
2. 遇到运算符，就比较它和运算符栈顶的优先级
3. 如果当前运算符优先级高，就入栈；否则，弹出栈顶运算符并计算
4. 遇到左括号直接入栈，遇到右括号就计算到左括号为止

我记得有一次做嵌入式计算器，用户输入了一个超长的表达式，里面嵌套了十几层括号。用递归解析的话，栈空间根本不够。但用这个双栈算法，稳稳地算出来了。

// 简化的表达式求值框架（仅演示核心逻辑）
int evaluate(char *expr) {
    SeqStack numStack;   // 操作数栈
    SeqStack opStack;    // 运算符栈
    InitStack(&numStack);
    InitStack(&opStack);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        if (isdigit(ch)) {
            // 解析完整数字并入栈
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;  // 回退一步
            Push(&numStack, num);
        } else if (ch == '(') {
            Push(&opStack, ch);
        } else if (ch == ')') {
            // 计算到左括号为止
            while (GetTop(&opStack) != '(') {
                // 弹出运算符和两个操作数，计算结果
                // 结果压回操作数栈
            }
            Pop(&opStack);  // 弹出左括号
        } else if (isOperator(ch)) {
            // 处理运算符优先级
            while (!StackEmpty(&opStack) &&
                   priority(ch) <= priority(GetTop(&opStack))) {
                // 弹出并计算
            }
            Push(&opStack, ch);
        }
    }
    
    // 处理剩余运算符
    while (!StackEmpty(&opStack)) {
        // 弹出并计算
    }
    
    int result;
    GetTop(&numStack, &result);
    return result;
}

好了，这一讲的内容就到这里。栈这个东西，看似简单，但用好了能解决很多实际问题。从括号匹配到表达式求值，再到函数调用栈，处处都有它的身影。希望你能动手把代码敲一遍，只有亲手写过，才能真正理解。

---