> ## Documentation Index
> Fetch the complete documentation index at: https://docs.0907world.cn/llms.txt
> Use this file to discover all available pages before exploring further.
# 第 3 章 栈和队列
本章重点复习栈和队列这两种特殊的受限线性表栈的核心是“后进先出（LIFO）”，队列的核心是“先进先出（FIFO）”掌握它们在不同存储结构（顺序与链式）下的操作特性，以及括号匹配、表达式求值、卡特兰数等典型应用是本章复习的关键
## 栈
* **存储结构**：用一段连续存储单元（数组）存放栈元素
* **关键指针**：常见做法 `top` 指向**当前栈顶元素位置**，或指向**栈顶元素的下一位置**（两种约定均可，需配套一致）
* **时间复杂度**：入栈、出栈、取栈顶均为 $O(1)$
* **空间特性**：需要预先分配容量 `MaxSize`，可能产生空间浪费或容量不足
**易错点：溢出**
* **上溢（overflow）**：栈满仍入栈（越界）
* **下溢（underflow）**：栈空仍出栈（非法）
* **核心思想**：两个栈共享同一数组空间，分别从两端向中间增长
* **优点**：在总空间固定时，能更充分利用存储空间；当一个栈空而另一个栈满的情况减少
* **满栈判定**：两栈顶指针相遇（或满足相邻条件，依约定而定）
```mermaid theme={null}
graph LR
top(("top")) --> nodeC["c | next"]
nodeC --> nodeB["b | next"]
nodeB --> nodeA["a | NULL"]
```
* **存储结构**：用单链表实现，通常把**表头作为栈顶**以便 `Push/Pop` 在表头进行
* **栈顶指针**：指向栈顶结点
* **优点**：
* 不需要预先分配固定容量，理论上只受限于可用内存
* 入栈/出栈无需移动大量元素
* **时间复杂度**：入栈、出栈、取栈顶均为 $O(1)$；额外指针域带来一定存储开销
**核心特性**：栈是受限线性表，核心特性：**LIFO (Last In First Out)**
顺序栈与链栈的基本操作复杂度均为 $O(1)$，差别主要在**空间管理方式**（固定容量 vs 动态分配）实现中需做边界检查与错误处理
## 栈的典型应用与要点
* **思想**：扫描表达式，遇到左括号入栈，遇到右括号则与栈顶左括号进行匹配并出栈
* **关键结论**：
1. 扫描结束时栈必须为空才匹配成功
2. 扫描中任何时刻出现“需要出栈但栈空”则匹配失败
* **中缀**：运算符在中间，日常书写
* **后缀/逆波兰式 (RPN)**：运算符在后，便于用栈求值
* **前缀**：运算符在前
* 约定：运算符有优先级（如 `* /` 高于 `+ -`），多数二元运算符是**左结合**
* 准备：一个**输出序列**和一个**运算符栈**
* 从左到右扫描：
* 遇到**操作数**：直接追加到输出序列
* 遇到**左括号 `(`**：入运算符栈（隔断作用）
* 遇到**右括号 `)`**：反复弹出栈顶运算符到输出序列，直到弹出左括号（左括号不输出）
* 遇到**运算符 `op`**：
* 当栈非空，且栈顶运算符 `topOp` 优先级**高于** `op`，或优先级**等于** `op` 且 `op` 是左结合，则将 `topOp` 出栈并追加；重复直到不满足条件或遇到左括号
* 然后将 `op` 入栈
* 扫描结束：将运算符栈中剩余的运算符依次弹出追加
* **扫描**：操作数入栈；遇到运算符则弹出两个操作数计算后再入栈
* **结束**：结束时栈顶即结果
* **问题表述**：对 $n$ 个元素按固定顺序 $1,2,...,n$ 依次入栈，在允许任意时刻出栈的前提下，一共有多少种不同的出栈序列？
* **结论**：合法出栈序列的种类数为第 $n$ 个**卡特兰数**
$C_n = \frac{1}{n+1} C_{2n}^{n}$
* **推理思路**：
* 入栈记为 $+1$，出栈记为 $-1$共 $2n$ 步，最终高度回 $0$
* 合法性约束：从起点出发的过程中，高度不能降到 $0$ 以下
* 非法路径：通过反射原理，可证明非法路径数为 $C_{2n}^{n+1}$
* 合法路径：$C_{2n}^{n} - C_{2n}^{n+1} = \frac{1}{n+1} C_{2n}^{n}$
* **递推形式**：
$C_0 = 1$
$C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k} \quad (n \ge 1)$
含义：按“最后一次出栈对应的元素”将整体拆成左右两个相互独立的合法子结构
* **递归与函数调用栈**：
* **递归本质**：把大问题分解为规模更小的同类子问题，依靠**系统调用栈**保存返回点与局部状态
* 必须有**递归出口**（终止条件），深度过大可能导致**栈溢出**
* **深度优先搜索 (DFS)**：
* DFS 的“先走到底再回退”天然符合栈的 LIFO 特性
* 递归 DFS 使用系统栈；非递归 DFS 使用显式栈保存待访问结点/状态
## 队列
* **核心思想**：数组首尾相接，指针按模运算循环移动：
* `front = (front + 1) % MaxSize`
* `rear = (rear + 1) % MaxSize`
**判空与判满的方法**：
循环队列必须解决“`front == rear` 时到底是空还是满”的二义性，常见三种方法：
1. **牺牲一个存储单元**（最常用）：
* 判空：`front == rear`
* 判满：`(rear + 1) % MaxSize == front`
* 可用容量：`MaxSize - 1`
2. **增加计数器 `size`**：
* 判空：`size == 0`
* 判满：`size == MaxSize`
3. **增加标志位 `tag`**：区分最近一次操作是入队还是出队
* **存储结构**：用链表实现队列，通常设置 `front` 指向队头结点，`rear` 指向队尾结点
* **带头结点的链队列**：判空常为 `front == rear`（都指向头结点）
* **优点**：
* 不需要预设容量，适合元素个数变化较大场景
* 入队在尾部插入、出队在头部删除，均为 $O(1)$
* **双端队列 (Deque)**：
* 两端允许进入，一端允许退出
* 两端允许退出，一端允许进入
* **队列的常见用途**：
* **层次遍历 (BFS)**：按层推进天然符合 FIFO，典型实现用队列保存待访问结点
* **缓冲与调度**：如打印队列、消息队列、CPU 就绪队列等