第6章 栈：后进先出的艺术

栈这个东西，说白了就是一种「后进先出」的数据结构。我刚开始学的时候觉得它太简单了，不就是个只能从一头操作的线性表吗？后来才发现，越是简单的结构，用好了越能解决复杂问题。

6.1 栈的定义与核心操作

栈（Stack）是一种操作受限的线性表。它只允许在一端进行插入和删除操作，这一端叫做栈顶（Top），另一端叫做栈底（Bottom）。

核心操作就五个：

  • InitStack(&S)：初始化一个空栈
  • Push(&S, x)：元素x入栈
  • Pop(&S, &x)：栈顶元素出栈，用x返回
  • GetTop(S, &x)：读取栈顶元素，不出栈
  • StackEmpty(S)：判断栈是否为空

嗯，这里要注意：Pop和GetTop的区别。Pop是拿走，GetTop只是看一眼。我在项目中见过有人把这两个搞混，结果数据被意外删除了。

栈的特性：后进先出（LIFO, Last In First Out）。就像一摞盘子，你总是先拿最上面的那个。

6.2 顺序存储实现

顺序栈，就是用数组来实现。我习惯用一个整型变量top来指示栈顶位置。空栈时top = -1，有元素时top指向当前栈顶元素的下标。

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top;  // 栈顶指针
} SqStack;

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

// 判断空栈
int StackEmpty(SqStack S) {
    return S.top == -1;
}

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

// 出栈
int Pop(SqStack *S, int *x) {
    if (S->top == -1) {
        return 0;  // 栈空
    }
    *x = S->data[S->top--];
    return 1;
}

// 读栈顶
int GetTop(SqStack S, int *x) {
    if (S.top == -1) {
        return 0;
    }
    *x = S.data[S.top];
    return 1;
}

避坑指南：我曾经在嵌入式项目里用顺序栈，没注意栈的大小限制。结果递归调用太深，栈溢出了，整个系统直接崩溃。从那以后，我养成了一个习惯——凡是栈深度不确定的场景，优先考虑链式存储。

6.3 链式存储实现

链栈，说白了就是用链表来实现栈。入栈就是头插法，出栈就是删除头结点。你想想看，这样操作的时间复杂度都是O(1)，而且不用担心栈满的问题。

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

// 初始化
void InitStack(LinkStack *S) {
    *S = NULL;
}

// 入栈
int Push(LinkStack *S, int x) {
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if (!p) return 0;
    p->data = x;
    p->next = *S;
    *S = p;
    return 1;
}

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

我建议你在实际开发中这样选：如果数据量可控、栈深度已知，用顺序栈；如果数据量不确定、频繁动态变化，用链栈。

栈的存储结构对比 顺序栈 data[0] data[1] data[2] ← top data[3] data[4] 优点：访问快，实现简单 缺点：大小固定，可能溢出 链栈 data next → data next → data NULL ← top 优点：动态扩展，无栈满问题 缺点：需要额外指针空间

6.4 栈的应用：括号匹配

括号匹配是栈最经典的应用之一。你想想看，编译器怎么知道你的代码括号有没有配对？其实就是用栈来做的。

算法思路很简单：遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶是否匹配。如果最后栈为空，说明全部匹配。

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

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

小技巧：我在写代码编辑器插件时，用这个算法实现了括号高亮功能。每次用户输入一个括号，就实时检查匹配情况，不匹配的标红。用户体验特别好。

6.5 栈的应用：表达式求值

表达式求值，说白了就是让计算机理解数学公式。计算机不像人，它看不懂中缀表达式（比如 3+4*2），它更喜欢后缀表达式（比如 3 4 2 * +）。

转换规则：

  • 遇到操作数，直接输出
  • 遇到运算符，与栈顶比较优先级
  • 栈顶优先级高或相等，则出栈并输出
  • 当前运算符入栈
  • 遇到左括号直接入栈，遇到右括号则出栈直到左括号
// 运算符优先级
int priority(char op) {
    switch(op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '(': return 0;
        default: return -1;
    }
}

// 中缀转后缀
void infixToPostfix(char *infix, char *postfix) {
    SqStack S;
    InitStack(&S);
    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(&S, ch);
        } else if (ch == ')') {
            char top;
            while (!StackEmpty(S)) {
                Pop(&S, &top);
                if (top == '(') break;
                postfix[j++] = top;
            }
        } else {
            char top;
            while (!StackEmpty(S)) {
                GetTop(S, &top);
                if (priority(top) >= priority(ch)) {
                    Pop(&S, &top);
                    postfix[j++] = top;
                } else break;
            }
            Push(&S, ch);
        }
    }
    
    while (!StackEmpty(S)) {
        char top;
        Pop(&S, &top);
        postfix[j++] = top;
    }
    postfix[j] = '\0';
}

6.6 栈的应用：递归转非递归

递归虽然写起来爽，但性能是个大问题。每次递归调用都要压栈，深度大了容易栈溢出。我建议你在以下场景考虑转非递归：

  • 递归深度超过1000层
  • 对性能要求极高
  • 嵌入式系统内存受限

以斐波那契数列为例，递归写法：

int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

转成非递归，其实就是用栈模拟函数调用：

typedef struct {
    int n;      // 参数
    int state;  // 0: 未计算, 1: 已计算左子树
    int result; // 计算结果
} Frame;

int fib_non_recursive(int n) {
    SqStack S;
    InitStack(&S);
    
    Frame f = {n, 0, 0};
    Push(&S, f);
    
    while (!StackEmpty(S)) {
        Frame *top = &S.data[S.top];
        
        if (top->n <= 1) {
            top->result = top->n;
            Pop(&S, &f);
            if (!StackEmpty(S)) {
                Frame *parent = &S.data[S.top];
                if (parent->state == 0) {
                    parent->result += f.result;
                    parent->state = 1;
                    Frame child = {parent->n - 2, 0, 0};
                    Push(&S, child);
                } else {
                    parent->result += f.result;
                }
            }
        } else if (top->state == 0) {
            top->state = 1;
            Frame child = {top->n - 1, 0, 0};
            Push(&S, child);
        } else {
            Pop(&S, &f);
            if (!StackEmpty(S)) {
                Frame *parent = &S.data[S.top];
                parent->result += f.result;
            }
        }
    }
    return f.result;
}

核心思想：递归转非递归，本质上就是用栈来模拟函数调用栈。每次递归调用对应一次入栈，每次返回对应一次出栈。你只要把函数参数、局部变量、返回地址这三个东西存到栈帧里，就能手动控制调用流程了。

好了，栈的内容就讲到这里。记住一句话：栈虽小，用处大。从括号匹配到表达式求值，从函数调用到深度优先搜索，处处都有栈的身影。你写代码的时候，遇到「后进先出」的场景，第一个想到的就应该是栈。

专注资料整理

← 上一章 📖 返回目录 下一章 →