第 7 讲 · 栈与队列

栈和队列都是线性表，但故意限制访问位置。限制看似减少功能，却让操作变成稳定的 $O(1)$，并直接对应两种重要过程：回到最近现场，以及按到达顺序处理。

栈：后进先出

栈只允许在栈顶插入和删除。基本操作包括初始化、判空、取栈顶、进栈和出栈。

顺序栈常让 top 指向当前栈顶，空栈时为 -1；也可以让 top 指向下一个可用位置，空栈时为 0。代码和判断条件必须与约定一致。

int push(Stack *s, int x) {
    if (s->top == MAXSIZE - 1) return 0;
    s->data[++s->top] = x;
    return 1;
}

链栈把链表首部作为栈顶，进栈和出栈都是头部插删，不需要预设固定容量。

两栈共享空间

两个栈可以从同一数组两端向中间生长：一个栈顶递增，一个递减。当两个栈顶相邻时空间才真正用满。它适合两栈总规模变化、但总和有上限的场景。

中缀表达式转后缀

扫描中缀表达式：

• 操作数直接输出；
• 左括号压栈；
• 右括号把运算符弹出直到左括号，并丢弃这对括号；
• 普通运算符先弹出栈中优先级不低于自己的运算符，再入栈；
• 扫描结束后弹出剩余运算符。

括号和右结合运算符需要按题目约定单独处理。

后缀表达式求值

扫描后缀表达式：操作数入栈；遇到运算符时先弹出右操作数，再弹出左操作数，计算后把结果压回。顺序不能反，例如减法应算“第二个弹出的数减第一个弹出的数”。

栈与递归

函数调用时，返回地址、参数和局部变量形成调用记录并压栈。最近调用的函数最先返回，因此与栈完全一致。用显式栈改写递归，本质上是把这些“待完成现场”由运行时改为程序自己保存。

队列：先进先出

队列从队尾插入、队头删除。顺序队列若简单让下标不断右移，即使数组前部已经空出，也可能出现“假溢出”。

循环队列

循环队列用取模让下标绕回数组开头：

$$rear=(rear+1)\bmod M.$$

若 front 指向队头元素，rear 指向下一个可写位置，并牺牲一个单元，则：

• 空：front == rear；
• 满：(rear + 1) % M == front；
• 长度：(rear - front + M) % M。

也可以额外保存元素数或标志位，从而利用全部 $M$ 个单元。做题前一定先确认题目采用哪种约定。

链队列

链队列维护 front 和 rear。入队在尾部插入，出队从头部删除。删除最后一个元素后，必须让两个指针都回到空队状态，否则 rear 会悬空。

优先队列

优先队列不是严格按到达先后取元素，而是每次取优先级最高者。可以用有序表实现，也可以用堆把插入和删除最高优先级元素控制在 $O(\log n)$。

怎样辨认应用

• 括号匹配、撤销操作、表达式、深度优先搜索：栈；
• 排队服务、缓冲区、树的层序遍历、广度优先搜索：队列；
• 调度和事件模拟：普通队列或优先队列。

结构的选择来自“接下来该处理谁”，而不是题目有没有直接出现“栈”或“队列”三个字。