13.1.3 队列与栈
队列和栈都是线性表的特殊应用。特殊之处不在存储，而在操作受限制：队列限制为队尾入、队头出；栈限制为栈顶入、栈顶出。
队列：先进先出
队列像排队买票：后来的人站到队尾，先来的人从队头离开。
| 操作 | 位置 | 结果 |
|---|---|---|
| 入队 | 队尾 rear | 新元素排到最后 |
| 出队 | 队头 front | 最早进入的元素离开 |
| 序列特点 | 入队顺序与出队顺序一致 | FIFO |
用链式结构实现队列时，课程提到常与循环单链表结合。只要维护队头和队尾，就不需要每次遍历到尾部。
mermaid
flowchart LR
Front["front/队头"] --> A["A"]
A --> B["B"]
B --> C["C"]
C --> Rear["rear/队尾"]栈：后进先出
栈像一端封闭的容器：只能从栈顶放入，也只能从栈顶取出。
| 操作 | 位置 | 结果 |
|---|---|---|
| 入栈 push | 栈顶 top | 新元素成为栈顶 |
| 出栈 pop | 栈顶 top | 当前栈顶离开 |
| 序列特点 | 最后进入的最先出来 | LIFO |
栈不需要循环链表，单链表从头部插入和删除就能很好地实现栈顶操作。
栈序列为什么灵活
若元素按 A, B, C 顺序入栈，出栈序列不只一种：
| 出栈序列 | 是否可行 | 一种操作过程 |
|---|---|---|
ABC | 可行 | A 入 A 出，B 入 B 出，C 入 C 出 |
ACB | 可行 | A 入 A 出，B 入，C 入 C 出，B 出 |
BAC | 可行 | A 入，B 入 B 出，A 出，C 入 C 出 |
BCA | 可行 | A 入，B 入 B 出，C 入 C 出，A 出 |
CBA | 可行 | A 入，B 入，C 入，C 出，B 出，A 出 |
CAB | 不可行 | C 先出时 A、B、C 都已入栈，C 出后栈顶是 B，不能越过 B 取 A |
判断栈序列时，不要背排列，按目标出栈序列模拟即可。
栈容量对序列的影响
如果要求 CBA，必须让 A, B, C 同时在栈中，所以栈容量至少为 3。若要求 BAC，只需 A, B 同时在栈中，容量 2 即可。早年题目会把“出栈序列”和“栈容量”结合起来考。
循环队列
顺序队列若一直入队出队，数组前部会空出来但不能直接利用，形成“假溢出”。循环队列把数组首尾看成环，靠取模让指针回绕。
若采用“少用一个存储单元”的方式：
| 条件 | 公式 |
|---|---|
| 队空 | front == rear |
| 队满 | (rear + 1) % maxSize == front |
| 队列长度 | (rear - front + maxSize) % maxSize |
为什么少用一个单元？因为如果所有单元都用满，队空和队满都可能出现 front == rear，无法区分。
队列与栈对比
| 比较项 | 队列 | 栈 |
|---|---|---|
| 规则 | 先进先出 | 后进先出 |
| 插入位置 | 队尾 | 栈顶 |
| 删除位置 | 队头 | 栈顶 |
| 序列灵活性 | 出队顺序固定 | 出栈顺序随入/出时机变化 |
| 常见应用 | BFS、缓冲区、排队服务 | 函数调用、表达式求值、DFS、括号匹配 |
本节例题
元素按 `A, B, C` 顺序入栈，下列哪一个不可能是出栈序列？
自查清单
- 能否不用背诵，手工模拟栈的出栈序列？
- 能否解释循环队列为什么要“少用一个单元”？
- 能否写出循环队列队空、队满和长度公式？