# 第三章：栈和队列

> 参考资料：《数据结构》第 3 章课件，共 105 页。以下页码均为原文档从 1 起的页序。配套讲义：[第三章 栈和队列](/数据结构/栈和队列/)。

## 0. 本章概述

本章讲两种操作受限的线性表：栈只允许在一端插入和删除，遵循后进先出（LIFO）；队列在一端插入、另一端删除，遵循先进先出（FIFO）。两者都可以用顺序存储或链式存储实现，核心操作都能做到 O(1)，但边界条件、判空判满和指针更新是主要难点（课件第 2—3 页）。

学习顺序：定义与 ADT → 顺序栈与链栈 → 栈的典型应用 → 队列定义 → 循环队列与链队列 → 队列应用 → 对比、复杂度与选型。

本章伪代码统一采用 C 风格：结构体通过指针参数修改，动态存储用 `malloc`/`free`；不使用 C++ 引用、模板或 `new`/`delete`，也不把不同语言的容器写法拼进同一段算法。课件中 `Push(&S, e)`、`SeqQueue &Q` 等接口写法只表示“按引用修改”，实现时统一改成指针参数。

## 1. 栈的定义、术语与 ADT（课件第 7—12 页）

栈是仅允许在表的一端进行插入和删除的线性表。允许操作的一端称为栈顶，另一端称为栈底；不含元素时为空栈。元素按 a₁、a₂、…、aₙ 的顺序进栈，出栈顺序必为 aₙ、…、a₂、a₁，这就是 LIFO。栈顶、栈底是逻辑概念，与内存地址高低无关；top 指针指向栈顶，bottom 指向栈底。

抽象数据类型包含：`InitStack`、`DestroyStack`、`ClearStack`、`StackEmpty`、`StackLength`、`GetTop`、`Push`、`Pop`，其中 Push 与 Pop 是核心操作。约定 aₙ 端为栈顶、a₁ 端为栈底。

**区分三个“清空/销毁”操作：** Init 分配空间并置为空；Clear 只把栈顶指针复位、不释放空间；Destroy 释放全部空间并置空指针。

## 2. 出栈序列的合法性（课件第 13 页）

给定进栈顺序 1、2、3，合法出栈序列有 123、132、213、231、321，共 5 种；312 不可能。判断依据：若某元素最先出栈，则它之前进栈的元素仍在栈中，且越晚进栈越靠近栈顶，出栈顺序只能与进栈顺序相反。

合法序列数为卡特兰数：

$$
\mathrm{Catalan}(n)=\frac{1}{n+1}\binom{2n}{n}
$$

例如 n = 3 时为 5，n = 4 时为 14。该公式的适用前提是“进栈顺序固定、每个元素进栈一次、出栈可在任意时刻发生、不允许中途穿插其他元素”。

## 3. 顺序栈（课件第 14—26 页）

结构定义：

```c
typedef struct {
    ElemType *pBase;   /* 基址，栈底 */
    ElemType *pTop;    /* 栈顶的下一个空位 */
    int stacksize;     /* 当前容量 */
} SeqStack;
```

约定 `pTop` 指向真实栈顶元素的下一个位置，于是：空栈为 `pTop == pBase`，元素个数为 `pTop − pBase`，栈满为 `pTop − pBase >= stacksize`。若改用“top 指向栈顶元素”的约定，则空栈为 `top == −1`、个数为 `top + 1`、满为 `top == MAXSIZE − 1`；两套公式不能混用。

**进栈：** 先判满；满则 `realloc` 扩容，成功后用新基址重算 `pTop = newBase + 旧元素个数`，再 `*pTop = e; pTop++`。先移动指针再写入会把元素放到错误位置。若 `realloc` 失败，课件用 `exit(OVERFLOW)` 终止，工程代码通常返回错误码。

**出栈：** 先判空；`e = *(pTop − 1); pTop--`。先读取再移动；也可以先 `pTop--` 再读 `*pTop`，两种写法等价，都先取得原栈顶元素、再更新栈顶位置。**取栈顶：** 只读 `*(pTop − 1)`，不移动指针。弹出后原单元仍保留旧值，但已不属于栈的有效范围，下一次 Push 会覆盖。

**复杂度成立条件：** 不扩容时 Push、Pop、GetTop 都是 O(1)。扩容单次 O(n)；若容量按固定增量增加，复制总量随 n 平方增长，摊还代价是 O(n)；只有按比例扩容（如翻倍）时，摊还才是 O(1)。

## 4. 链式栈与双端栈（课件第 27—35 页）

链式栈把栈顶设在单链表表头：`S` 为附加头结点，`S->next` 是栈顶。Push 用头插法：`s->next = S->next; S->next = s`；Pop 删除 `S->next` 并 `free`。空栈为 `S->next == NULL`。链栈不会“满”，只有内存分配失败；Push、Pop 均为严格 O(1)。

双端栈让两个栈共享一个数组：栈 1 底在下标 0、栈 2 底在下标 MAXSIZE−1，分别向中间增长。判决条件：栈 1 空 `top1 == −1`，栈 2 空 `top2 == MAXSIZE`，共享栈满 `top1 + 1 == top2`。优点是空间互补，缺点是只适合两个栈、且不能同时任意增长。注意第 3 节顺序栈的 `pTop` 指向下一空位，而这里 `top1`、`top2` 是栈顶元素下标；按此约定，栈 1 个数为 `top1 + 1`，栈 2 个数为 `MAXSIZE − top2`，不能套用 `pTop − pBase`。

**选型：** 元素个数可预估、追求连续存储与缓存局部性，用顺序栈；个数波动大或需要动态增长，用链式栈；两个栈此消彼长时可考虑共享栈。

## 5. 栈的典型应用（课件第 36—52 页）

**逆序输出与进制转换：** 反复取余压栈，再弹出即得高位到低位。1348 转八进制：余数 4、0、5、2 入栈，弹出 2、5、0、4，结果为 (2504)₈。时间 O(log n)，空间 O(log n)。注意 n = 0、负数与基数范围的边界。

**回文判定：** 全部压栈后逐个弹出与原串比较；时间 O(n)、空间 O(n)。可只压前半、双指针比较，把额外空间降为 O(1)。若 `char` 是单字节，多字节编码字符会被拆开，必须按编码单元处理。

**括号匹配：** 左括号压栈；右括号到来时，若栈空则为多余右括号，否则弹出栈顶比较类型；扫描结束栈非空则为缺少右括号。`([)]` 数量相等但类型不匹配。时间 O(n)，最坏空间 O(n)。实现只识别三种括号，字母、数字、空白等一般字符跳过；字符串、注释里的括号要先做词法处理，不属于本实验语法。该模型可扩展到 HTML/XML 标签匹配。

**中缀表达式求值：** 用操作数栈 OPND 和运算符栈 OPTR，`#` 作结束标志。比较 OPTR 栈顶 θ₁ 与当前 θ₂：θ₁ 高则先算，θ₂ 高则压栈，相等则脱括号或结束。`*`、`/` 高于 `+`、`−`；同级左结合。执行二元运算时先弹右操作数、再弹左操作数。`3+4*2-(1+1)#` 的计算过程为 4×2 = 8、3+8 = 11、1+1 = 2、11−2 = 9。结束条件必须同时满足：输入已消费完、OPTR 只剩栈底哨兵 `#`、OPND 恰余一个值；`3#` 是合法的单操作数表达式，而 `3+4#` 归约后得 7。数值口径：输入为非负整数字面量，支持二元 `+ − * /` 与括号，显式拒绝一元正负号；运算结果可为有限小数（`5/2 = 2.5`、`1/2+1/2 = 1`），用浮点实现时需说明近似与输出精度，不能与整数除法口径混用。其他边界：多位数、空白、除零、括号不配对、非法字符都要显式处理；课件算法只直接支持非负整数。

**后缀表达式求值：** 遇操作数压栈，遇运算符弹出右、左操作数计算后压栈；扫描结束栈中必须恰剩一个值。例 `5 1 2 + 4 * + 3 -` = 14。时间 O(n)；辅助空间取决于扫描过程中同时未归约的操作数个数，也就是操作数栈的最大深度，最坏 O(n)，不能简单写成“嵌套深度”或“表达式树深度”。

**递归与显式栈：** 系统调用栈自动保存返回地址、参数与局部变量；递归过深会栈溢出。把递归改为显式栈时，调用映射为压栈、返回映射为弹栈，还需保存“当前处理到哪一步”的状态。代价是代码复杂，收益是容量可控、可暂停恢复。显式栈不一定更省空间：它与递归保存的活动记录同阶，主要收益是避开系统栈深度限制；只有压缩递归状态时辅助空间才可能真正下降。

**N 皇后：** 按行放置，`col[r]` 记录第 r 行皇后列号；冲突条件为同列或 `|c₁ − c₂| = r₂ − r₁`。前进即压栈，第 r 行无可用列则回退弹栈，属于深度优先回溯与剪枝。4 皇后首解为 (2,4,1,3)，次解 (3,1,4,2)；n = 2、3 无解，n = 8 有 92 解。简单实现未剪枝的全排列上界为 n! 量级（阶乘阶，不是固定底数的 cⁿ），每放一个皇后再做 O(n) 冲突检查，含检查上界 O(n·n!)；剪枝减少实际访问结点但不给未证明的紧界。空间 O(n)（递归深度与 col 数组）；用固定数组时还必须检查 n 不超过数组容量。

## 6. 队列的定义与 ADT（课件第 53—57 页）

队列只允许在队尾插入、在队头删除，遵循 FIFO。a₁ 为队头、aₙ 为队尾；入队顺序与出队顺序相同。ADT 包括 `InitQueue`、`DestroyQueue`、`ClearQueue`、`QueueEmpty`、`QueueLength`、`GetHead`、`EnQueue`、`DeQueue`。

**本章统一约定：** 循环队列中 `front` 指向队头元素下标，`rear` 指向队尾元素的下一个空位；空队列 `front == rear`；满队列 `(rear + 1) % MAXQSIZE == front`。链式队列中 `front` 指向附加头结点、`rear` 指向最后一个数据结点，空队列 `front == rear`。

## 7. 循环队列（课件第 58—68 页）

顺序队列若 `front`、`rear` 只增不减，出队留下的前端空位无法复用，`rear` 到达数组末端时出现“假溢出”。把数组看成环，入队、出队后都执行取模：`rear = (rear + 1) % MAXQSIZE`、`front = (front + 1) % MAXQSIZE`，即可循环利用空间。

元素个数：

$$
\mathrm{length} = (\mathrm{rear}-\mathrm{front}+\mathrm{MAXQSIZE}) \bmod \mathrm{MAXQSIZE}
$$

空、满都可能有 `front == rear`，有两种区分方案：① 增加长度/计数变量，空为 0、满为 MAXQSIZE，空间利用率高但多维护一个状态；② 牺牲一个单元，规定满条件 `(rear + 1) % MAXQSIZE == front`，实际容量为 MAXQSIZE−1，状态最少、最常用。若采用计数器方案，必须连同指针约定一起替换（例如 `rear` 指向真实队尾元素、满以 `length == MAXQSIZE` 判断，可存满 M 格）；也可以用 `tag` 记录最后一次操作。替代方案不能与牺牲单元公式混用。

**基本操作：** Init 分配数组并置 `front = rear = 0`；EnQueue 判满后写入 `pBase[rear]` 再移动 rear；DeQueue 判空后取 `pBase[front]` 再移动 front；长度用上式；GetHead 只读 `pBase[front]`。全部 O(1)。

**例：** MAXQSIZE = 8，依次入队 A—G 后满（front = 0、rear = 7）；出队 A、B、C 后 front = 3；入队 H、I、J 后 rear = 2，再次满，元素占下标 3、4、5、6、7、0、1，此时 rear 所指的下标 2 暂不存元素，是判满所需的空位。它不是固定保留的槽位：再出队一次后 front = 4，下一次入队就会把新元素写入下标 2，空位随 front、rear 一起移动，牺牲的是容量中的一个元素。

## 8. 链式队列（课件第 69—76 页）

链队列用带头结点的单链表：`front` 指向头结点，`rear` 指向最后一个数据结点，空队列时二者都指向头结点。入队：新结点链到 `rear` 之后，再让 `rear` 指向新结点；出队：删除 `front->next`，若删除的正是 `rear` 所指结点（队列只剩一个元素），必须令 `rear = front`，否则 rear 悬空。EnQueue、DeQueue 均为 O(1)，不会队满（除非内存耗尽）。

**与循环队列比较：** 循环队列用连续数组、容量固定为 MAXQSIZE−1、无指针开销、缓存局部性好；链队列按需分配、容量只受内存限制、每结点多一个指针、实现时要注意尾指针更新。最大长度可预估时优先循环队列，长度波动大时优先链队列。

## 9. 队列应用（课件第 77—86 页）

**滑动窗口求移动平均：** 课件用了两组题设：第 79 页是每秒采集 1 次、k = 3 的演示；第 80—82 页是每秒上报 10 次、每秒读取一次、算法取窗口常量 100 的教材例，且原始材料对窗口是 10 次还是 100 次的表述并不一致。两者不能混用：100 次按每秒 10 次计算覆盖 10 秒，k = 3 覆盖 3 秒。用循环队列保存最近 k 个值，队列满时先出队最旧值、再入队新值，同时增量维护总和：入队加、出队减。每次采样 O(1)、每次输出 O(1)、空间 O(k)；若每次输出重新遍历，单次 O(k)。预热期有两种口径：本讲义与实验采用暖启动——未满窗口分母取当前项数（k = 3 时前三个输出为 20.00、21.25、21.17），满窗后分母取 k；课件第 79 页演示与第 82 页算法则采用等待满窗——窗口未满时不输出（第 79 页前两次显示“--”，从第 3 个样本起输出 21.17、22.33、22.83；第 82 页预热期返回 DATA_NOT_ENOUGH、分母恒为 HIST_TIMES）。两种口径不能混用，也不能一边显示“窗口 k 的平均”一边用不足 k 个样本去除。边界：该队列是独立的温度队列，元素类型 `ElemType` 取 `double`（温度含小数，不能沿用 `char` 或整型），物理容量取 k+1（牺牲一个单元）；浮点累加长期运行可能误差累积，必要时定期重算；若采样间隔不均，“最近 k 个样本的平均”不等于“最近 k 秒的时间平均”。

**生产者—消费者缓冲：** 生产者入队、消费者出队；队满时生产者等待或丢弃，队空时消费者等待；FIFO 保证按到达顺序处理。键盘、网络、打印缓冲都用这一模型。这里的等待/唤醒属于并发同步，需要条件变量、信号量或互斥锁，循环队列本身不提供线程安全；满时是等待、丢弃还是覆盖，必须明确策略。容量是延迟与吞吐的权衡。

**层次遍历（补充）：** 课件仅把树/图广度优先遍历列为队列应用方向，未展开算法。要点是队列保存当前层待处理结点，处理时将孩子入队，从而按层输出。

## 10. 对比、复杂度与易错点（课件第 87—95 页）

| 比较项   | 栈                                | 队列                         |
| -------- | --------------------------------- | ---------------------------- |
| 规则     | LIFO                              | FIFO                         |
| 操作位置 | 仅栈顶                            | 队尾入、队头出               |
| 判空     | `pTop == pBase`（或 `top == −1`） | `front == rear`              |
| 判满     | 元素数 >= 容量，需扩容            | `(rear+1)%MAXQSIZE == front` |
| 链式要点 | 栈顶在表头，头插头删              | front 头结点、rear 尾结点    |
| 典型应用 | 递归、括号、表达式、回溯          | 缓冲、窗口、BFS、调度        |

**系统与语言中的体现：** 函数调用栈、递归深度限制、浏览器前进后退（两个栈）、编辑器撤销重做（两个栈）、编译器运算符栈；进程调度（FCFS）、消息队列、TCP 滑动窗口、Java `Queue`/`LinkedList`、Python `collections.deque`。

**复杂度汇总：** 栈与队列基本操作 O(1)；顺序栈扩容单次 O(n)、按比例扩容摊还 O(1)，固定增量扩容不成立；中缀/后缀求值 O(n)、空间为栈最大深度最坏 O(n)；N 皇后简单实现未剪枝时全排列 n! 量级、含冲突检查 O(n·n!)，剪枝只减少实际访问结点；滑动窗口每样本 O(1)；两个栈模拟队列 EnQueue O(1)、DeQueue 摊还 O(1)、最坏 O(n)。

**易错点：**

1. pTop 的两种约定混用，导致判空、判满、长度三处同时错。
2. Push 先移指针再写入；Pop 先移指针后仍按旧位置读写。正确的出栈写法有两种：先读 `items[top−1]` 再 `--top`，或先 `--top` 再读 `items[top]`，两者都先取得原栈顶元素、再移动指针。
3. `realloc` 后沿用旧 `pTop`，形成悬空指针。
4. Clear 误 `free`、Destroy 只置空不释放。
5. 循环队列漏取模，`rear++` 越界；或直接用 `rear − front` 计算长度。
6. 牺牲单元后仍按 MAXQSIZE 作为可存元素数。
7. 链队列删除最后一个结点后忘记更新 `rear`。
8. 只数括号个数，不检查类型与嵌套。
9. 中缀求值先弹左操作数、后弹右操作数，减法除法结果反转。
10. 位序从 1 起、下标从 0 起，两者差 1；N 皇后、双端栈、循环队列都容易在这里出错。
11. 把第 79 页的 k = 3 演示与第 80—82 页的 100 次窗口混成同一题设，或把“最近 k 个样本”当成“最近 k 秒”。
12. 计数器/长度方案与牺牲单元方案的判满公式混用；或把双端栈 top1/top2 套用 pTop 的下一空位公式；或把暖启动的“当前项数分母”与固定窗口的“分母恒为 k”混用。

**自测清单：** 能否不看书画出顺序栈的判空判满公式？能否说明 Push 的摊还复杂度成立条件？能否写出循环队列长度公式并解释为什么加 MAXQSIZE？能否解释链队列 `rear` 更新为什么必要？能否用栈模拟中缀求值并处理括号与优先级？能否说明回溯与穷举的区别？