Sherfiter's wiki for fun

第 3 章 · 栈与队列

栈和队列的名字都来自生活:叠盘子(最后放的最先取)和排队买饭(先来的先走)。把它们从生活里请进计算机之后,你会发现这两个「受限的线性表」几乎撑起了整个运行时世界:每次函数调用就是一次入栈(计组第 10 章的栈帧)、每次广度优先搜索就是一次出队、你按 Ctrl+Z 撤销的是栈、消息系统里排队的是队列。本章把它们的实现做扎实,再用两道经典题(括号匹配、表达式求值)练出真正的手感。

3.1 栈:只开一个门

栈(后进先出,LIFO)只允许在栈顶操作。实现极其简单,顺序栈一个数组加一个下标:

typedef struct { int data[1000]; int top; } Stack;   // top 指向栈顶元素的下一格

void push(Stack *s, int v) {
    if (s->top >= 1000) return;          // 栈满
    s->data[s->top++] = v;
}
int pop(Stack *s) {
    if (s->top == 0) return INT_MIN;     // 栈空(用哨兵值,或返回错误码)
    return s->data[--s->top];
}

push 和 pop 都是 O(1),没有之一。链式栈就是链表头插(2.2 的 push_front 原样可用),不设上限,但每个节点多付一个指针加一次 malloc。工程上还有一个「免实现」的顺序栈:系统调用栈本身就是(C 的局部变量、递归),计组第 10 章画过的栈帧图就是这章的顺序栈在硬件里的样子,连「爆栈」这个 bug 都是一脉相承的。

栈的精神在一个词里:最近。所有「需要回放最近发生的事」的场景都是栈:函数调用(谁调用我,我返回给谁)、编辑器的撤销、浏览器的后退、括号匹配(最近未闭合的括号必须最先被闭合)。

3.2 循环队列:把数组弯成环

队列(先进先出,FIFO)头出尾进。顺序实现的尴尬:数组头删一个,后面全体前移,O(n)。解法是把数组弯成环:下标越界就绕回 0,用两个指针(队头 front、队尾 rear)追逐,任何操作只动指针:

#define CAP 1024
typedef struct { int data[CAP]; int front, rear; } Queue;

void enq(Queue *q, int v) {
    if ((q->rear + 1) % CAP == q->front) return;   // 满
    q->data[q->rear] = v;
    q->rear = (q->rear + 1) % CAP;
}
int deq(Queue *q) {
    if (q->front == q->rear) return INT_MIN;       // 空
    int v = q->data[q->front];
    q->front = (q->front + 1) % CAP;
    return v;
}

一个必须吃透的细节:满和空在这个方案里都是 front == rear 吗?空是;满时若不处理也会「绕一圈重合」,于是留一个格子不用,用 (rear + 1) % CAP == front 判满(牺牲一个位置换一个不用额外变量的判满条件)。另一种方案是维护 size 计数器,不牺牲格子但要同步维护。这是教材的经典考题,也是环形缓冲区(ring buffer)的通用套路:内核的网络包队列、音频驱动、Kafka 的磁盘日志分区,用的都是它。第 5 章图的邻接表、第 6 章 BFS 的待访问队列,都会用到本章的队列。

3.3 双端队列:两头都开

双端队列(deque)两头都能进出,兼收栈和队列的全部能力。标准库(std::deque、Python collections.deque)的实现是「分块连续 + 块表」:既保住头尾 O(1),又保留较好的局部性。滑动窗口最大值是它的招牌题:窗口右移时,队尾弹出所有比新元素小的(它们永远不会成为答案),队头超窗弹出,单调队列的队头永远是窗口最大值,均摊 O(1) 完成每个元素的进出。

3.4 实战一:括号匹配

编译器每分钟都在做的事:检查括号是否合法。栈的解法自然到近乎直觉:

int match(const char *s) {
    char st[1000]; int top = 0;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') { st[top++] = c; continue; }
        if (c == ')' || c == ']' || c == '}') {
            if (top == 0) return 0;                 // 右括号多了
            char o = st[--top];
            if ((c==')'&&o!='(') || (c==']'&&o!='[') || (c=='}'&&o!='{'))
                return 0;                            // 交叉匹配(如 "(]")
        }
    }
    return top == 0;                                 // 左括号多了?
}

三个返回路径对应三种非法(右多、交叉、左多),写完拿 ([)] 测一下,能返回 0 才算真懂。这题的普适价值在于演示了栈的通用姿势:嵌套结构,处理到哪层,哪层的现场就压在栈顶。

3.5 实战二:表达式求值

人类写 3 + 4 * 2(中缀),括号和优先级让人脑和编译器都头疼;计算器真正喜欢的形态是后缀表达式(逆波兰式)3 4 2 * +,一次从左到右扫描:数字入栈,遇运算符弹两个数算完压回,扫描结束栈里剩一个数就是答案,无优先级、无括号、无歧义:

3 4 2 * + 的求值过程:
3 入栈        栈: [3]
4 入栈        栈: [3, 4]
2 入栈        栈: [3, 4, 2]
* 弹 4,2 → 8  栈: [3, 8]
+ 弹 3,8 → 11 栈: [11]    ← 答案

中缀转后缀用「运算符栈」:数字直接输出,运算符按优先级决定「自己入栈还是先把栈顶弹出去」,左括号入栈当护身符,右括号把栈里到左括号为止的全弹出来。这套双栈算法(Dijkstra 提出)是编译器表达式解析的原型,习题里请亲手实现一遍,算「先把编译原理的一角摸到」。

常见错误

  • 循环队列判满写反。front == rear 既是空又是(未处理的)满,忘留空格子或忘计数,队列会在环上「追尾」自己。
  • 出栈空检查漏掉。pop 空栈是未定义行为(顺序栈读负下标,链式栈解引用 NULL),接口要么返回错误码要么断言,别裸奔。
  • 递归转迭代时栈溢出。深递归(第 9 章的树遍历)手动用显式栈改写时,把「入栈时机」写错(该先进右子树先进了左子树),遍历顺序悄悄错掉,结果对一半最迷惑人。

练习

  1. 实现:用两个栈实现一个队列(入队进 A,出队时 A 空则把 A 全倒进 B 再弹)。算每个元素最多被搬几次,验证均摊 O(1)。
  2. 手算:把 (1 + 2) * (3 - 4) / 5 转成后缀表达式,再用栈求值,写出每步栈内容。
  3. 动手:写单调队列版的滑动窗口最大值,数组 10 万、窗口 1000,和暴力 O(n·k) 对比耗时。
  4. 思考:函数调用为什么必须用栈(而不是队列或数组)?想想嵌套调用的返回顺序,以及第 10 章计组里 rsp 寄存器的动作,用本章的语言重新描述一遍。
豫ICP备2026027944号