Appearance
栈和队列的定义与基本概念
核心思想
栈的定义
栈（Stack）是只允许在一端进行插入和删除操作的线性表。允许操作的一端称为栈顶（top），另一端称为栈底（bottom）。
┌───┐ ← 栈顶（插入/删除端）
│ e₃│
├───┤
│ e₂│
├───┤
│ e₁│
└───┘ ← 栈底核心特性：后进先出（Last In First Out, LIFO）
栈的基本操作：
| 操作 | 说明 | 时间复杂度 |
|---|---|---|
| InitStack(&S) | 初始化空栈 | O(1) |
| Push(&S, e) | 入栈（栈顶插入） | O(1) |
| Pop(&S, &e) | 出栈（栈顶删除） | O(1) |
| GetTop(S, &e) | 读栈顶元素（不删除） | O(1) |
| StackEmpty(S) | 判空 | O(1) |
队列的定义
队列（Queue）是只允许在一端插入、另一端删除的线性表。插入的一端称为队尾（rear），删除的一端称为队头（front）。
出队 ← [e₁][e₂][e₃][e₄] ← 入队
队头 队尾核心特性：先进先出（First In First Out, FIFO）
队列的基本操作：
| 操作 | 说明 | 时间复杂度 |
|---|---|---|
| InitQueue(&Q) | 初始化空队列 | O(1) |
| EnQueue(&Q, e) | 入队（队尾插入） | O(1) |
| DeQueue(&Q, &e) | 出队（队头删除） | O(1) |
| GetHead(Q, &e) | 读队头元素（不删除） | O(1) |
| QueueEmpty(Q) | 判空 | O(1) |
栈和队列与线性表的关系
三者本质都是线性表，区别在于允许的操作不同：
| 结构 | 插入位置 | 删除位置 | 特性 |
|---|---|---|---|
| 线性表 | 任意位置 | 任意位置 | 无限制 |
| 栈 | 栈顶 | 栈顶 | LIFO |
| 队列 | 队尾 | 队头 | FIFO |
| 双端队列 | 两端均可 | 两端均可 | 可退化为栈或队列 |
卡特兰数：出栈序列计数
n 个不同元素依次入栈，合法的出栈序列总数为卡特兰数：
C(n) = C(2n, n) / (n + 1)| n | 合法序列数 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
408 选择题常问"以下哪个不是合法的出栈序列"，可用卡特兰数验证总数，也可逐步模拟判断。
考研高频考点
- ⭐ 栈和队列的定义与特点（选择题必考）
- ⭐ 合法出栈序列判断（选择题高频）
- ⭐ 栈和队列的应用场景辨析（选择题）
- ⭐ 双端队列的输出序列判断（近年新增考点）
- 操作受限线性表的本质理解（概念辨析）
- 卡特兰数公式及应用
易错：栈是"操作受限的线性表"，不是"特殊的存储结构"。栈描述的是逻辑结构上的操作限制，底层可以用顺序存储（顺序栈）或链式存储（链栈）实现。
易错：双端队列(Deque)两端都可以进行插入和删除。输出受限的双端队列（一端可入可出，另一端只能入）和输入受限的双端队列（一端可入可出，另一端只能出）产生的合法序列不同，408 近年出过相关选择题。
栈和队列的典型应用
| 应用场景 | 使用的数据结构 | 说明 |
|---|---|---|
| 括号匹配 | 栈 | 遇左括号入栈，遇右括号与栈顶匹配 |
| 表达式求值 | 栈 | 操作数栈 + 运算符栈 |
| 递归 | 栈（系统栈） | 函数调用时保存返回地址、局部变量、参数 |
| 层次遍历 | 队列 | 树/图的 BFS 用队列逐层处理 |
| CPU 资源分配 | 队列 | 多进程争用 CPU，按 FIFO 排队（如时间片轮转调度） |
| 打印缓冲区 | 队列 | 多个打印请求排队等待，按提交顺序处理 |
| 设备速度匹配 | 队列 | 主机与慢速外设之间用缓冲区（队列）协调速度差异 |
队列在计算机系统中的应用主要解决两类问题：
主机与外设的速度不匹配：CPU 处理速度远快于打印机等外设。系统设置打印缓冲区（本质是队列），CPU 将打印任务放入队列后继续其他工作，打印机按 FIFO 顺序从队列中取出并执行。
多用户对同一资源的竞争：多个进程同时请求 CPU 运行，操作系统用就绪队列管理——进程按规则入队，CPU 空闲时从队头取出下一个进程执行。