栈和队列¶
方法速览¶
| 任务 | 方法 | 口诀 |
|---|---|---|
| 栈 | 后进先出 LIFO，只在栈顶进出 | 后进先出 |
| 队列 | 先进先出 FIFO，队尾进、队头出 | 先进先出 |
| 出栈序列判定 | 按目标序列逐个“入栈到它 → 弹出它”模拟，卡住即非法 | 缺谁进谁，进了就弹 |
| 循环队列 | 下标取模 (rear+1) % N；判满常用“牺牲一格” |
转圈取模，留空判满 |
| 双栈当队列 | 入队压 s1；出队时若 s2 空就把 s1 整体倒进 s2 | 倒一次序就翻过来 |
概念与数组实现¶
栈（stack）：只允许在同一端（栈顶）插入删除——后进先出（LIFO）。 队列（queue）：队尾入、队头出——先进先出（FIFO）。
数组实现（栈）：top 指向栈顶元素下标：
数组实现（循环队列）：头尾下标都取模绕圈，防假溢出：
判满判空（牺牲一格法，容量 N 的数组存 N−1 个）：
- 队空：
head == rear； - 队满：
(rear + 1) % N == head； - 元素个数：
(rear - head + N) % N。
STL 实现¶
注意：栈顶用 top()、队头用 front()；pop() 只删不返回值，取值与弹出分两步。priority_queue 默认大根堆。
双栈实现队列¶
两个栈 s1（入）、s2（出）：
- 入队：压进 s1；
- 出队：s2 非空则弹 s2 栈顶；s2 为空则把 s1 全部弹出依次压入 s2（顺序颠倒一次），再弹 s2 栈顶。
例：入队 1、2、3 后出队：s1 = [1,2,3]（3 在顶）→ 倒入 s2 = [3,2,1]（1 在顶）→ 弹出 1 ✓——每个元素最多被搬运一次，均摊 O(1)。栈与队列本质不同，但可以用两个栈实现队列（2022 真题考点）。
出栈序列合法性判定¶
模拟判定法——对着目标序列，缺谁进谁，进了就弹：
- 按入栈顺序把元素依次压栈；
- 每压一个就看栈顶：若正是目标序列当前要出的元素，弹出并后移目标指针（可能连弹多个）；
- 全部压完后栈空且目标走完 → 合法；中途卡住（栈顶不是想要的且没有元素可再压）→ 非法。
例：入栈 1~5，判定出栈序列 4 3 5 2 1：
| 目标 | 操作 | 栈（底→顶） |
|---|---|---|
| 4 | 压 1、2、3、4 → 弹 4 | 1 2 3 |
| 3 | 栈顶即 3 → 弹 | 1 2 |
| 5 | 压 5 → 弹 5 | 1 2 |
| 2 | 弹 2 | 1 |
| 1 | 弹 1 | 空 |
合法 ✓。而 4 3 5 1 2：弹完 5 后栈为 [1 2]，目标要 1 但栈顶是 2 且无元素可压——非法。
禁式（3 元素判非法的捷径）：出栈序列中若出现“…3, 1, 2…”型（大的先出、然后是更早的两个按原序），必非法——n 个元素共 \(\dfrac{1}{n+1}\binom{2n}{n}\)（Catalan 数）种合法序列，n=4 时 14 种。
混合模拟真题演算¶
例（2025 真题）：初始空栈 S、空队列 P，顺次处理 \(A = 7,5,8,3,1,4,2\)：奇数压栈；偶数且栈非空则弹栈顶入 P；偶数且栈空则跳过。
| 读到 | 奇/偶 | 动作 | 栈 S（底→顶） | 队列 P |
|---|---|---|---|---|
| 7 | 奇 | 压 | 7 | 空 |
| 5 | 奇 | 压 | 7 5 | 空 |
| 8 | 偶 | 弹 5 入 P | 7 | 5 |
| 3 | 奇 | 压 | 7 3 | 5 |
| 1 | 奇 | 压 | 7 3 1 | 5 |
| 4 | 偶 | 弹 1 入 P | 7 3 | 5 1 |
| 2 | 偶 | 弹 3 入 P | 7 | 5 1 3 |
结束：P = 5, 1, 3。
练习题目¶
练习 1 · 栈的特性¶
题目
栈的存取原则是（ ）
- A. 先进先出
- B. 后进先出
- C. 随机存取
- D. 按下标存取
答案与解析
答案：B
只在栈顶进出，最后进的最先出（LIFO）。
练习 2 · 队列的特性¶
题目
队列的存取原则是（ ）
- A. 后进先出
- B. 随机存取
- C. 先进先出
- D. 两端都进都出
答案与解析
答案：C
队尾进、队头出，先来的先走（FIFO）——排队买票。
练习 3 · 栈顶输出¶
题目
依次 push 1、2、3、4 后 pop 两次，再 push 5，此时栈顶到栈底依次是（ ）
- A.
5 2 1 - B.
5 3 2 - C.
1 2 5 - D.
5 4 3
答案与解析
答案：A
push 后栈（底→顶）1 2 3 4；pop 两次弹掉 4、3 剩 1 2；push 5 → 栈 1 2 5，顶是 5。
练习 4 · 队列输出¶
题目
依次入队 a、b、c 后出队一次，再入队 d，再出队两次，出队序列是（ ）
- A.
c b a - B.
a b c - C.
b c d - D.
a b d
答案与解析
答案：D
出队从头走：先 a；再入 d 队列 b c d；连出 b、d——共 a、b、d。
练习 5 · 312 禁式¶
题目
入栈顺序 1、2、3，下列不可能的出栈序列是（ ）
- A.
1 2 3 - B.
3 2 1 - C.
3 1 2 - D.
2 1 3
答案与解析
答案：C
要出 3 必须先压 1、2、3，此时 2 在 1 上面，弹完 3 只能先 2 后 1——3 1 2 要求 1 抢在 2 前面，矛盾。“312”型是判非法的最小模式。
练习 6 · 五元素合法序列¶
题目
入栈顺序 1~5，下列出栈序列合法的是（ ）
- A.
4 3 5 2 1 - B.
4 3 5 1 2 - C.
5 4 1 2 3 - D.
2 5 1 3 4
答案与解析
答案：A
模拟：压 1-4 弹 4、弹 3，压 5 弹 5，再依次弹 2、1 ✓。B 在弹完 5 后栈 [1 2] 目标要 1（栈顶 2）卡死；C 弹完 4 后栈 [1 2 3] 目标 1（栈顶 3）卡死；D 弹 2 后压 3 4 5 弹 5，栈 [1 3 4] 目标 1 卡死。
练习 7 · 合法序列计数¶
题目
4 个不同元素依次入栈，可能的出栈序列共有（ ）种。
- A. \(24\)
- B. \(10\)
- C. \(16\)
- D. \(14\)
答案与解析
答案：D
Catalan 数 \(C_4 = \frac{1}{5}\binom{8}{4} = 14\)；全排列 24 里被禁掉 10 种。
练习 8 · 入栈即出的序列¶
题目
若每个元素入栈后立即出栈，n 个元素的出栈序列是（ ）
- A. 与入栈顺序相同
- B. 与入栈顺序相反
- C. 任意
- D. 无法确定
答案与解析
答案：A
进一个弹一个，栈只是“过一手”，顺序不变；全部压完再弹（B）才得到逆序。
练习 9 · 逆序输出¶
题目
依次压入 a、b、c、d 后全部弹出，输出顺序是（ ）
- A.
d c b a - B.
a b c d - C.
a d b c - D. 不确定
答案与解析
答案：A
一口气压完再弹 = 完全逆序——栈天然“倒序输出”。
练习 10 · top 指针¶
题目
数组栈 stk[]，top 指向栈顶元素且空栈 top=0，push x 的操作是（ ）
- A.
stk[top++] = x; - B.
stk[++top] = x; - C.
stk[top] = x; top--; - D.
top++; stk[top-1] = x;
答案与解析
答案：B
top=0 表示空（不存元素），先 ++ 到 1 再存。A 会把元素存进 stk[0] 且空栈语义被破坏——两套约定（top 指向顶 / 指向下一空位）别混用。
练习 11 · 循环队列下标¶
题目
容量 8 的循环队列，rear = 7 时再入队一个元素后 rear =（ ）
- A. \(8\)
- B. \(7\)
- C. \(0\)
- D. \(1\)
答案与解析
答案：C
\((7 + 1) \bmod 8 = 0\)——下标绕回开头，这就是“循环”。
练习 12 · 牺牲一格判满¶
题目
容量 8 的数组实现循环队列（牺牲一格法），最多同时存（ ）个元素；判满条件是（ ）
- A. \(8\)；
rear == head - B. \(8\)；
(rear+1)%8 == head - C. \(7\)；
(rear+1)%8 == head - D. \(7\)；
rear == head
答案与解析
答案：C
留一格空区分“满”和“空”：两者都 head == rear 就分不清了。想存满 8 个要额外维护计数变量。
练习 13 · 队列元素个数¶
题目
循环队列容量 N，head=2、rear=7（rear 指向下一空位），元素个数是（ ）
- A. \(7\)
- B. \(4\)
- C. \(9\)
- D. \(5\)
答案与解析
答案：D
\((rear - head) \bmod N = 5\)（未绕圈时就是差值；绕圈时加 N 再模）。
练习 14 · STL 接口¶
题目
stack<int> s 已有元素，取栈顶并删除，正确写法（ ）
- A.
int x = s.pop(); - B.
int x = s.top(); s.pop(); - C.
s.pop(x); - D.
int x = s.front(); s.pop();
答案与解析
答案：B
pop() 不返回值，先 top() 再 pop()；front() 是队列的接口。
练习 15 · 队列接口¶
题目
queue<int> q 的队头元素用（ ）读取。
- A.
q.top() - B.
q.back() - C.
q.front() - D.
q[0]
答案与解析
答案：C
队列 front/back；top 是栈的——接口混用是最常见的手误。
练习 16 · 双栈实现队列的原理¶
题目
用两个栈 s1、s2 模拟队列，出队时（ ）
- A. 直接弹 s1 栈顶
- B. 做不到
- C. 交替弹 s1、s2
- D. s2 为空时把 s1 全部倒入 s2，再弹 s2 栈顶
答案与解析
答案：D
倒一次顺序：s1 里的“后进先出”经 s2 再反一次变成“先进先出”。倒空后再倒新的一批，每个元素至多搬一次。
练习 17 · 双栈队列追踪¶
题目
依次执行：入队 1、2、3，出队一次，入队 4，出队一次。出队的两个元素是（ ）
- A.
1 2 - B.
3 4 - C.
1 4 - D.
2 3
答案与解析
答案：A
第一次出队：s1=[1,2,3] 倒入 s2=[3,2,1]，弹 1；入队 4 压 s1=[4]；第二次出队：s2 非空直接弹 2。队列序 1、2 ✓。
练习 18 · 栈与 BFS/DFS¶
题目
深度优先搜索（DFS）与广度优先搜索（BFS）分别借助（ ）
- A. 队列、栈
- B. 栈、队列
- C. 都用队列
- D. 都用栈
答案与解析
答案：B
DFS 一条路走到黑（回溯 = 弹栈），BFS 一层层扩（先来先服务 = 队列）。
练习 19 · 中缀转后缀用栈¶
题目
表达式求值 / 中缀转后缀算法中，栈用来存（ ）
- A. 操作数
- B. 运算符（比较优先级决定弹栈）
- C. 括号对
- D. 结果
练习 20 · 队列空判定¶
题目
顺序队列（非循环）只从队尾加、队头删，head > rear（rear 指向下一空位）说明（ ）
- A. 队满
- B. 下标错误
- C. 有一个元素
- D. 队空
答案与解析
答案：D
rear 追着 head 走，追过头（相等或超过）即空。
练习 21 · 双端队列¶
题目
deque（双端队列）的特点是（ ）
- A. 两端都能进能出
- B. 只能一端进出
- C. 先进后出
- D. 自动排序
答案与解析
答案：A
两端开放；栈和队列都是它的特例（只用一端 / 一端进一端出）。
练习 22 · 混合模拟（自编）¶
题目
空栈，顺次处理序列 3, 1, 4, 1, 5：奇数压栈、偶数则弹栈顶（若有）。处理完后栈（底→顶）为（ ）
- A.
3 1 1 5 - B.
3 1 5 - C.
3 1 - D.
5 1 3
答案与解析
答案：B
3 压、1 压、4 偶弹 1（剩 3）、1 压（3 1）、5 压（3 1 5）。
练习 23 · 混合模拟（队列入队）¶
题目
空队列，顺次执行：入 1、入 2、出、入 3、出、入 4。最终队列（头→尾）是（ ）
- A.
1 2 3 4 - B.
3 4 - C.
4 3 2 - D.
2 3 4
答案与解析
答案：D
出队两次走的是 1、2；剩 3、4 在队里（头 3 尾 4）。
练习 24 · 出栈序列数对照¶
题目
3 个元素入栈，合法出栈序列有（ ）种。
- A. \(5\)
- B. \(6\)
- C. \(4\)
- D. \(3\)
答案与解析
答案：A
Catalan \(C_3 = 5\)：全排列 6 种里只有 3 1 2 非法。
练习 25 · 卡住的时刻¶
题目
入栈顺序 a~e，模拟出栈序列 c, d, a, ... 时，弹出 d 之后（栈内 a、b）目标要 a——此时（ ）
- A. 弹 b 再弹 a，序列改为合法
- B. 已无元素可压而栈顶 b ≠ a，序列非法
- C. 把 b 弹掉扔了再弹 a
- D. 重头再压一遍
答案与解析
答案：B
判定法的“卡住”：想要的元素被压在下面、又没有新元素可入，只能判非法——这是 2021 真题 c,d,a,e,b 非法的确切原因。
练习 26 · 输出受限辨析¶
题目
n 个元素依次入栈且允许随时出栈，出栈序列中第一个元素（ ）
- A. 一定是 1
- B. 可以是任意一个
- C. 只能是 1 或 n
- D. 一定是 n
答案与解析
答案：B
想让第 k 个先出：压 k 个、立即弹第 k 个——谁都能当第一个；受限的是后续（被压住的按序受限）。
历年真题¶
2021 年 · 第 5 题¶
题目
对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。
- A.
a, b, c, d, e - B.
e, d, c, b, a - C.
b, a, c, d, e - D.
c, d, a, e, b
答案与解析
答案：D
模拟 D：压 a b c 弹 c，压 d 弹 d（此时栈 [a b]），目标下一个是 a——栈顶是 b 且 e 还没压。若压 e 再弹 e 得 c d e ...，顺序不符；不压则 a 被 b 压着。卡住，非法。
A（进一个弹一个）、B（全压完倒出）、C（压两个弹两个再进出）均合法。
2022 年 · 第 2 题¶
题目
有 \(6\) 个元素，按照 \(6\)、\(5\)、\(4\)、\(3\)、\(2\)、\(1\) 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。
- A.
5 4 3 6 1 2 - B.
4 5 3 1 2 6 - C.
3 4 6 5 2 1 - D.
2 3 4 1 5 6
答案与解析
答案：C
模拟 C：依次压 6 5 4 3，弹 3；目标 4，栈顶正是 4，弹；目标 6，栈顶是 5——压 2、1 后栈 [6 5 2 1]，栈顶 1 ≠ 6，卡住非法（6 被 5 压着，而 5 又被 2、1 压着，救不出来）。
2022 年 · 第 5 题¶
题目
假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。
- A. \(2\)
- B. \(3\)
- C. \(4\)
- D. \(6\)
答案与解析
答案：B
出队序 = 出栈序，模拟“压入 e1~e6、能出就出”：
| 事件 | 栈内（底→顶） | 说明 |
|---|---|---|
| 压 e1、e2 → 出 e2 | e1 | 栈存 1 |
| 压 e3、e4 → 出 e4、e3 | e1 | 峰值 3（e1,e3,e4 同存） |
| 压 e5、e6 → 出 e6、e5 | e1 | 峰值 3 |
| 出 e1 | 空 |
栈最多同时存 3 个 → 容量至少 3。
2022 年 · 第 10 题¶
题目
以下对数据结构的表述不恰当的一项为：（ ）。
- A. 图的深度优先遍历算法常使用的数据结构为栈。
- B. 栈的访问原则为后进先出，队列的访问原则是先进先出。
- C. 队列常常被用于广度优先搜索算法。
- D. 栈与队列存在本质不同，无法用栈实现队列。
答案与解析
答案：D
两个栈串联即可模拟队列（倒一次序）；A/B/C 都是标准表述。
2024 年 · 第 13 题¶
题目
给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 1 2 3 4 5 6，其中 1 最先入栈、6 最后入栈，下面哪种出栈顺序是不可能的？（ ）
- A.
6 5 4 3 2 1 - B.
1 6 5 4 3 2 - C.
2 4 6 5 3 1 - D.
1 3 5 2 4 6
答案与解析
答案：D
模拟 D：弹 1（进出即弹）；压 2 3 弹 3；压 4 5 弹 5——目标 2，栈 [2 4]，栈顶 4 ≠ 2，卡住（压 6 也没用）→ 非法。A 全倒序、B 弹 1 后全压再倒、C 逐段“压两个弹一个”都合法。
2025 年 · 第 15 题¶
题目
给定一个初始为空的整数栈 \(S\) 和一个空的队列 \(P\)。我们按顺序处理输入的整数队列 \(A: 7, 5, 8, 3, 1, 4, 2\)。对于队列 \(A\) 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 \(S\)；如果该数是偶数，且栈 \(S\) 非空，则弹出一个栈顶元素，并加入到队列 \(P\) 的末尾；如果该数是偶数，且栈 \(S\) 为空，则不进行任何操作。当队列 \(A\) 中的所有数都处理完毕后，队列 \(P\) 的内容是什么？（ ）
- A.
5, 1, 3 - B.
3, 1, 5 - C.
7, 5, 3 - D.
5, 1, 3, 7
答案与解析
答案：A
完整逐元素演算见上文“混合模拟真题演算”的七行表格：三次偶数各弹一次栈顶（5、1、3），7 留在栈底永不出。
易错小结¶
- 栈 LIFO 只碰栈顶；队列 FIFO 尾进头出；STL 的
top()（栈）/front()（队列）别混，pop()不返回值； - 出栈序列判定：缺谁进谁、进了就弹，卡住即非法（2019~2024 反复考）；n 元素合法序列 = Catalan 数；
- “312”型是最小非法模式：大者先出后，更早的两个必须逆序出；
- 循环队列取模绕圈；牺牲一格判满
(rear+1)%N == head，判空head == rear； - 两个栈可模拟队列（s2 空时整体倒 s1）；DFS 用栈、BFS 用队列；
- 混合模拟题列表格逐行走，别跳步。