---
title: "03-栈与队列"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 03 栈与队列

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 3 篇，相关系列见 [[00-基础与理论|基础与理论]]。

栈和队列都是**操作受限的线性表**：栈只准从一头进出（**后进先出 LIFO**），队列一进一出（**先进先出 FIFO**）。限制越强，用途越专——本章一半在讲"它们能干什么"，一半在讲 408 的经典算术题（出栈序列数、循环队列判满）。

## 一、栈：后进先出

### 栈的基本盘

- 只在**栈顶**操作：push/pop/peek
- 顺序栈：`data[] + top`；**top 指向栈顶元素**时初始 top=-1，push 先 `++top` 再放（若 top 指向栈顶下一格则初始 0，顺序反过来）——两派约定，读题先看约定
- **共享栈**：两个栈共用一个数组，一个从底下往上长、一个从顶上往下长，**栈顶相遇（top1+1==top2）才满**——空间利用率翻倍的巧思
- 链栈：单链表 + **头插法**（头即栈顶），无栈满问题

### 卡特兰数：n 个元素的出栈序列数

n 个元素依次进栈，任意时刻可出栈——合法的出栈序列总数：

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

| n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 合法出栈序列数 | 1 | 2 | 5 | **14** | 42 |

💡 n=3 时 5 种：abc、acb、bac、bca、**cab 不行**（a、b、c 依次进，c 先出后不可能 a 在 b 前？验证：c 先出 → 栈里 b、a，只能 b 后 a → cba✅）。经典陷阱题："n 元素进栈，出栈序列中不可能出现…"——用"**在栈里，先入者后出**"这条规则手推即可。

⚠️ 括号匹配的有效组合数、二叉树形态数（[[05-树与二叉树]]）都是同一个卡特兰数——408 喜欢跨界考。

### 栈的三大应用

1. **括号/符号匹配**：左括号进栈，右括号弹栈配对——编译器词法分析的日常
2. **表达式求值**：见下文中缀转后缀
3. **函数调用栈**：每次调用压一个**栈帧**（参数、局部变量、返回地址）——递归深度就是栈深，"栈溢出 StackOverflow"的字面来源；[[01-操作系统概述|OS]] 的用户栈就是它

⚠️ 中断现场保护（[[07-输入输出系统|计组 IO]]）也用系统栈——压栈/弹栈是硬件级操作。

### 中缀转后缀（手算例题）

后缀（逆波兰）：运算符写在操作数后——**无括号、无优先级歧义**，一遍扫描就能算。

**例：`A + B * C - (D / E + F)` 转后缀**

口诀：**操作数直接输出；运算符看栈顶——栈顶优先级 ≥ 当前，就先弹；左括号只被右括号弹**。

1. `A` → 输出 A
2. `+` → 栈空，进栈 `[+]`
3. `B` → 输出 A B
4. `*` → 栈顶 `+` 优先级低，`*` 进栈 `[+ *]`
5. `C` → 输出 A B C
6. `-` → 栈顶 `*` ≥ `-`，弹 `*`；栈顶 `+` ≥ `-`，弹 `+`；`-` 进栈 `[-]` → 输出 A B C * +
7. `(` → 进栈 `[- (]`
8. `D / E` → 输出 A B C * + D E，`/` 进栈 `[- ( /]`
9. `+` → `/` 弹出，`+` 进栈 `[- ( +]` → 输出 … D E /
10. `F` → 输出 … F
11. `)` → 弹到左括号为止：弹 `+`，丢 `(` → 输出 … F +
12. 结束，弹光：弹 `-` → 输出 … −

**结果：`A B C * + D E / F + -`** ✅

求值：后缀式用栈扫一遍，遇数进栈、遇符弹两个数算完再进——`[(A+ (B*C)) − ((D/E)+F)]` 结构自明。

## 二、队列：先进先出

### 顺序队列的死缺陷 → 循环队列

顺序队列出队后** front 指针前进、前面空间报废**（假溢出）→ 把数组首尾接成环：

```c
// 牺牲一个单元的约定（最常用）
front 指队首元素；rear 指队尾后一格
入队: rear = (rear + 1) % MAXSIZE
出队: front = (front + 1) % MAXSIZE
```

### 循环队列判满三法（408 必考）

| 方法 | 队满条件 | 队空条件 | 代价 |
|---|---|---|---|
| ① 牺牲一个单元 | `(rear+1) % MAX == front` | `rear == front` | 最常用；少存 1 个元素 |
| ② 增设 size 变量 | `size == MAX` | `size == 0` | 多维护一个计数器 |
| ③ 增设 tag 标志 | 入队后 tag=1 且 `rear==front` | 出队后 tag=0 且 `rear==front` | tag 记录"最后一次是入还是出" |

**元素个数公式**（无论哪种约定，背）：

$$\text{个数} = (rear - front + MAX) \% MAX$$

💡 例题：MAX=10，front=3、rear=1 → 个数 = (1−3+10)%10 = **8**。

⚠️ top/rear 指向的约定不同，判空判满就不同——**读题先抠"rear 指哪"**，这是 408 最阴的坑。

### 双端队列与衍生（了解）

- **双端队列 deque**：两头都能进出；两端限制一个方向就是"输出受限/输入受限队列"
- 考题：给一串输入输出序列，判断"能否由该受限队列产生"——手动模拟进出即可

## 三、队列的三大应用

1. **缓冲区/任务排队**：打印队列、消息队列（Kafka/RabbitMQ 的思想原型）——**削峰填谷**
2. **BFS 广度优先搜索**（[[06-图|图]]）：层序遍历的骨架
3. **页面置换 FIFO 算法**（[[06-内存管理|OS 内存管理]]）、**CPU 就绪队列**（[[03-CPU调度|CPU 调度]]：FCFS 就是队列，时间片轮转也是队列）

💡 栈和队列的哲学：**栈是"最近的优先"（时间逆序），队列是"先来的优先"（公平）**——CPU 调度策略之争（优先级 vs 公平）在数据结构层面就是这两兄弟。

## 四、特殊矩阵的压缩存储（顺手收拾）

对称矩阵只存下三角：n(n+1)/2 个元素；下标 i,j（1-based，i ≥ j）→ 一维下标

$$k = \frac{i(i-1)}{2} + j - 1$$

- 三对角矩阵存 3n−2 个
- 稀疏矩阵：**三元组表 (行, 列, 值)** 或十字链表
- ⚠️ 408 常考"给 i,j 求一维下标"——记公式 + 用 i=2,j=1 代入验证（k=1），比背推导快

## 五、盲点自测

1. 共享栈什么时候满？（top1+1 == top2，两栈顶相遇）
2. 4 个元素入栈，合法出栈序列共几种？（卡特兰 C₄=14）
3. 后缀式求值用栈：遇运算符弹几个数？先弹的是左操作数还是右？（2 个；先弹的算**右**操作数）
4. 循环队列 MAX=8，front=5、rear=2，元素几个？((2−5+8)%8=5)
5. 判满三法各自的代价？（牺牲空间 / size 维护 / tag 维护）
6. 中断现场压栈用的是哪种结构？（系统栈——LIFO）
7. BFS 和 CPU 调度 FCFS 的共同骨架？（队列 FIFO）

## 六、动手玩

```python
# 用栈把后缀式求值一遍（对照本文例题）
def eval_postfix(tokens):
    st = []
    for t in tokens:
        if t in '+-*/':
            b, a = st.pop(), st.pop()   # 先弹的是右操作数！
            st.append({'+': a+b, '-': a-b, '*': a*b, '/': a/b}[t])
        else:
            st.append(t if not t.isdigit() else int(t))
    return st[0]

# A=2, B=3, C=4, D=8, E=2, F=5 → 2+12-(4+5) = 5
print(eval_postfix([2,3,4,'*','+',8,2,'/',5,'+','-']))   # 5

# 循环队列：验证个数公式
MAX = 10
front, rear = 3, 1
print((rear - front + MAX) % MAX)    # 8
```

## 参考资料

- 王道《数据结构考研复习指导》第 3 章
- 《算法图解》第 3 章——调用栈的画法极清晰
- [[05-字符编码]]——"烫烫烫"就是未初始化栈内存的 debug 填充
- [[00-刷题理模型|刷题理模型]]——单调栈模板（下一个更大元素、柱状图最大矩形）

⬅️ [[02-线性表|线性表]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[04-串与KMP|串与KMP]]