三、栈与队列（第 19-30 题）
19. 以下关于栈的描述中，正确的是( )
标签：【互联网/国企笔试超高频】
A. 栈是先进先出(FIFO)的结构 B. 栈具有插入和删除操作的任意性 C. 栈是后进先出(LIFO)的结构 D. 栈中没有数据元素
答案：C
【结论】 栈是后进先出(LIFO)结构，选 C。
【逐项辨析】
- A 错：先进先出(FIFO)是队列的特性，不是栈。
- C 对：栈是后进先出(LIFO, Last In First Out)的线性结构 —— 最后入栈的元素最先出栈。
- B 错：栈只能在栈顶插入(push)和删除(pop),不具有操作的任意性。
- D 错：栈中可以存放任意多个数据元素，只是操作位置受限。
【知识点】 栈的核心特征
| 特征 | 说明 |
|---|---|
| 结构 | 线性表 |
| 操作限制 | 只允许在栈顶插入与删除 |
| 顺序 | 后进先出 LIFO |
| 基本操作 | push（入栈）、pop（出栈）、top（取栈顶）、isEmpty |
| 栈底 | 最先入栈、最后出栈，位置固定 |
“操作受限”是理解栈的关键 —— 它并不是不能存取元素，而是存取位置被限定在栈顶这一端。
【记忆锚点】 “栈像一摞盘子，只能从顶上拿、往顶上放”——最后放上去的最先被拿走(LIFO)。
【易混对比】 栈 vs 队列（最基础的一对对比）：
| 栈 | 队列 | |
|---|---|---|
| 顺序 | 后进先出 LIFO | 先进先出 FIFO |
| 插入端 | 栈顶 | 队尾 |
| 删除端 | 栈顶 | 队头 |
| 典型应用 | 递归、表达式求值、括号匹配 | 进程调度、BFS、打印队列 |
【自测】 元素 1、2、3 依次入栈，则第一个出栈的元素是？
答：3。最后入栈的最先出栈。与第 21、23 题连考。
【知识关联】
- 同库连考：与第 23 题（队列 FIFO）是「栈 vs 队列」对题；与第 26 题（栈应用）、第 27~29 题（双栈队列、两队列栈、最小栈）构成栈专题。
- 工程实现:JVM 方法调用栈、
Stack类（已过时，应用ArrayDeque）、ThreadLocal的栈式上下文、括号匹配、表达式求值都用栈；Deque接口可当栈用。 - 408 / 国企真题:408 与国网「栈与队列」定义题必考。
- 面试追问:①「为什么 JDK 不推荐 Stack 类？」（继承 Vector，锁开销大且语义不清，应用 Deque）；②「递归为什么用栈？」（返回地址与局部变量后进先出）。
【拓展延伸】
变式：输出受限双端队列（第 22 题）、输入受限双端队列都是栈/队列的推广；「一端入同端出」退化为栈，「一端入异端出」退化为队列。
工程应用：浏览器前进后退（双栈）、undo/redo、DFS、函数调用、进制转换、迷宫回溯。
20. 设栈S的初始状态为空，元素a、b、c、d、e、f、g依次入栈，出栈序列为b、d、c、f、e、a、g，则栈S的容量至少是( )
标签：【国企笔试超高频】
A. 1 B. 2 C. 3 D. 4
答案：C
【知识点】 栈容量问题的一般解法与推广
栈最小容量 = 模拟过程中「栈内元素个数」的最大值解题三步:①按入栈顺序逐个 push;②对照出栈序列决定何时 pop;③每步记录深度，取最大值。
推广一 · 与合法性关系：若模拟中需要 pop 但栈顶不匹配 → 序列非法；合法序列必能算出峰值。n 个元素合法序列数 = 卡特兰数 C_n。
推广二 · 最坏/最好:
| 出栈形态 | 峰值容量 |
|---|---|
| 与入栈同序（边入边出） | 1 |
| 完全逆序（全入再全出） | n |
| 本题交错形态 | 3 |
推广三 · 递归对应：递归树的最大深度 = 隐式栈峰值；改非递归时显式栈容量按同一规则估计。不能只看出栈长度或入栈个数，必须逐步模拟——这是 408 与国网反复考的「凭感觉就错」题型。
【推导过程】 按入栈顺序逐一模拟，记录栈内元素个数的最大值
| 步骤 | 操作 | 栈内容（底→顶） | 深度 | 输出 |
|---|---|---|---|---|
| 1 | push a | [a] | 1 | — |
| 2 | push b | [a, b] | 2 | — |
| 3 | pop → b | [a] | 1 | b |
| 4 | push c | [a, c] | 2 | — |
| 5 | push d | [a, c, d] | 3 | — |
| 6 | pop → d | [a, c] | 2 | d |
| 7 | pop → c | [a] | 1 | c |
| 8 | push e | [a, e] | 2 | — |
| 9 | push f | [a, e, f] | 3 | — |
| 10 | pop → f | [a, e] | 2 | f |
| 11 | pop → e | [a] | 1 | e |
| 12 | pop → a | [] | 0 | a |
| 13 | push g | [g] | 1 | — |
| 14 | pop → g | [] | 0 | g |
出栈序列为 b, d, c, f, e, a, g，与题目一致。全程最大深度为 3。
【逐项辨析】
- A 1 / B 2：容量不够。模拟到第 5 步(push d)时栈内已有 3 个元素，会溢出。
- C 3：正确。 恰好容纳模拟过程中的最大深度。
- D 4：容量足够但不是“至少”，多出的空间被浪费。
【知识点】 栈容量问题的一般解法
栈容量 = 模拟过程中栈内元素个数的最大值解题三步:①按入栈顺序逐个 push;②对照出栈序列决定何时 pop;③每步记录栈深度，取最大值。
【记忆锚点】 “边入边记，峰值就是容量”——容量由最拥挤的那一刻决定。
【易错提醒】 不能只凭“出栈序列有多长”或“入栈了几个元素”来猜容量，必须逐步模拟。这类题在 408 与国网笔试中反复出现，是最容易因“凭感觉”而做错的题型之一。
【自测】 若入栈顺序为 1, 2, 3, 4，出栈序列为 2, 3, 4, 1，则栈的容量至少是多少？
答：2。push1, push2, pop2, push3, pop3, push4, pop4, pop1，最大深度为 2。与第 21 题连考。
【知识关联】
- 同库连考：与第 21 题（不可能出栈序列）是「同一模拟技能」的两种问法 —— 本题问「峰值深度」，第 21 题问「序列是否合法」；本题【自测】用的是同一套「逐步入栈出栈、跟踪峰值深度」模拟，别只数入栈个数。
- 工程实现:JVM 栈溢出
StackOverflowError本质就是「递归深度超过了线程栈容量」；手写算符解析、非递归 DFS 都要关心「显式栈最大深度」以预估空间。 - 408 / 国企真题：国网真题库高频「给出入出序列求栈最小容量」；408 类似模拟题。
- 面试追问:①「若出栈序列换成 b,d,c,f,e,g,a，容量还是 3 吗？」（需重新模拟，峰值可能不同）；②「n 个元素任意合法序列，容量最坏是多少？」（n，即全部入完再出）。
【拓展延伸】
完整验算与变式：本题模拟峰值 = 3（步骤 5 与 9）。若改为入栈 1..5、出栈 5,4,3,2,1 → 峰值 5；出栈 1,2,3,4,5 → 峰值 1。
通用结论:
栈最小容量 = max_t |栈内元素个数(t)|
合法出栈序列 ⇔ 任意前缀中「已入未出」数 ≥ 0 且模拟中 pop 顶匹配变式题：入栈 1,2,3,4,5，出栈 4,5,3,2,1 —— 模拟峰值=4（push 1,2,3,4 → pop 4；push 5 → pop 5,3,2,1）。注意 4,3,5,1,2 这类写法不合法：pop 5 之后栈内是 [1,2]，栈顶是 2，必须先出 2 才能出 1。
工程应用：多线程下「工作队列深度监控」、编译器表达式栈深度、正则引擎回溯栈。
21. 一个栈的入栈序列为1, 2, 3, 4，则不可能的出栈序列是( )
标签：【互联网/国企笔试高频】
A. 4, 3, 2, 1 B. 1, 2, 3, 4 C. 1, 4, 2, 3 D. 3, 2, 1, 4
答案：C
【结论】 1, 4, 2, 3 不可能是合法出栈序列，选 C。
【逐项辨析】
- A 4, 3, 2, 1：全部入栈后依次出栈，合法。
- B 1, 2, 3, 4：每入栈一个立即出栈，合法。
- C 1, 4, 2, 3：不合法。 先出 1(push1, pop1)，再出 4 意味着 2、3、4 已依次入栈，此时栈内自底向上为 2、3（栈顶是 3），下一个出栈只能是 3，不可能是 2。
- D 3, 2, 1, 4:push1,2,3 → pop3,2,1 → push4, pop4，合法。
【知识点 · 关键判断技巧】 出栈序列的合法性判据（必背）：
对出栈序列 p₁p₂…pₙ，若存在下标 i < j < k 使 p_j < p_k < p_i，则该序列不合法。
等价说法：序列中任一元素之后，所有比它小的元素必须按降序出现。
以本题 C(1, 4, 2, 3)为例：4 之后比 4 小的有 2 和 3，而 2 < 3 呈升序，违反判据 → 不合法。
合法序列计数：入栈序列长度为 n 时，合法出栈序列共有卡特兰数 C(2n, n)/(n+1) 个。n = 4 时为 14 个。
【记忆锚点】 “大数后面，小数必须从大到小排”——大元素出栈后，剩下比它小的元素只能按降序依次出栈。
【易混对比】 注意“入栈序列固定、出栈序列可变”：n 个元素有 n! 种排列，但只有卡特兰数种合法。本题 4 个元素共 24 种排列，合法 14 种，10 种不合法。这个比例在 408 真题中常被用来设置“有多少种合法出栈序列”的计算题。
【自测】 入栈序列为 1, 2, 3, 4, 5，下列哪个不是合法出栈序列？ A. 5,4,3,2,1 B. 2,1,4,3,5 C. 3,1,2,4,5 D. 1,3,5,4,2
答：C。3 出栈后栈内为 [1, 2]，下一出栈只能是 2，不可能先出 1。408 真题经典考法。
【知识关联】
- 同库连考：与第 20 题（容量）、第 22 题（双端队列序列）构成「序列合法性」三连；同一卡特兰数公式也用于「n 个结点的二叉树形态数」——该题原列第 47 题，本改版已把它替换为 TopK（见文末修订记录），公式同为 C(2n, n)/(n+1)，遇到时按同一套计数方法处理。
- 工程实现：编译器语法分析、括号匹配本质是「出栈入栈合法性」；Java
Deque模拟即可验证序列。 - 408 / 国企真题:408 经典；国网「栈」模块必考「不可能的出栈序列」。
- 面试追问:①「n=4 合法序列有多少？」（卡特兰数 14）；②「如何 O(n) 判断合法性？」（用栈模拟）。
【拓展延伸】
完整验算 C=1,4,2,3:
期望出 1:push1, pop1 → 栈空
期望出 4:push2,3,4 → 栈[2,3,4], pop4 → 栈[2,3]
期望出 2:栈顶是 3 ≠ 2 → 非法 ✓判据:任一元素之后，比它小的元素必须降序出现。C 中 4 之后出现 2 再 3（升序）→ 非法。
变式:
- 入栈 1,2,3,4,5，哪项非法？常用 C=3,1,2,4,5（3 后 1,2 升序非法）。
- 统计合法数：C_n = (2n)!/(n!(n+1)!);n=1,2,3,4,5 → 1,2,5,14,42。
- 双端队列完全自由时 n! 都合法（第 22 题自测）。
工程应用:XML/HTML 标签匹配、undo 栈操作序列校验。
22. 元素 a、b、c、d、e 依次进入一个双端队列（允许在两端进行入队操作），但只允许在同一端进行出队操作（即输出受限的双端队列），则不可能得到的出队序列是( )
标签：【国企笔试超高频】
A. b, a, c, d, e B. d, c, b, a, e C. d, b, c, a, e D. e, c, b, a, d
答案：C
【结论】 不可能得到的出队序列是 d, b, c, a, e，选 C。
【推导过程】 关键前提：d 最先出队，说明 a、b、c 三个元素此时都还留在队列中（它们先于 d 入队且尚未出队）。
“输出受限”意味着只能从同一端出队，但入队可以在两端进行。因此 a、b、c 只能通过“入前端 / 入后端”改变相对次序。穷举这 3 个元素全部入队后的可能排列
[a, b, c] [b, a, c] [c, a, b] [c, b, a]所以 d 出队后，剩余元素的出队次序只能是上述四种之一。
【逐项辨析】
- A b 先出 —— a 入后端、b 入前端，出 b、a；之后 c、d、e 各自“入前端立即出”，得 b, a, c, d, e，可行。
- B d 先出 —— a、b、c 依次入前端得 [c, b, a]（前端入序会逆序，正是【推导过程】列出的第四种排列）,d 再入前端得 [d, c, b, a],e 入后端，从前端依次出 d、c、b、a、e，可行。（若 a、b、c 依次入后端得 [a, b, c]，则 d 入前端后只能出 d、a、b、c，得不到本序列）
- C 要求 d 之后依次出 b、c、a —— 而 [b, c, a] 不在上述四种排列之内，不可能。
- D e 先出 —— a 入后端、b 入前端、c 入前端得 [c, b, a],d 入后端得 [c, b, a, d],e 入前端，依次出 e、c、b、a、d，可行。
【知识点】 双端队列(deque)的受限形态
| 类型 | 允许的入队端 | 允许的出队端 | 说明 |
|---|---|---|---|
| 输入受限双端队列 | 仅一端 | 两端 | 入队受限 |
| 输出受限双端队列 | 两端 | 仅一端 | 出队受限 |
| 一般双端队列 | 两端 | 两端 | 完全自由 |
| 极端受限（一端入、同端出） | 一端 | 同一端 | 退化为栈 |
| 极端受限（一端入、异端出） | 一端 | 另一端 | 退化为队列 |
栈和队列都是双端队列的特例 —— 把双端队列的两端操作各限制掉一个，就退化成栈或队列。
【记忆锚点】 “先入队的都还在里面，排列只有那几种”——做这类题先锁定“先出队元素”入队之前那些元素的可能排列。
【易错提醒】 判断合法性必须穷举剩余元素的可能排列，不能凭感觉。输出受限双端队列是国企笔试“栈与队列”的常考变体，也是 408 的高频难点。
【自测】 一般双端队列（两端都可入可出）中，元素 1, 2, 3 依次入队，能得到多少种不同的出队序列？
答：6 种全部可行(3! = 6)。双端队列比栈更灵活，因为两端都可出队。与第 21 题（n=4 时 24 种排列只有 14 种合法，C₄=14）对照记忆；n=3 才是 C₃=5。
【知识关联】
- 同库连考：与第 21 题（栈序列）对照 —— 栈更受限，非法序列更多；与第 19、23 题（栈/队列定义）以及「双端队列退化为栈/队列」的知识点相连。
- 工程实现:Java
ArrayDeque是双端队列；工作窃取线程池用 deque 两端进出；滑动窗口最大值（第 14 题）用单调双端队列。 - 408 / 国企真题:408 考过双端队列；国网真题库收录「输出受限」变体。
- 面试追问:①「输入受限双端队列和输出受限有何对偶？」（输入受限：一端入、两端出）；②「本题若允许两端出，序列还唯一否？」（更自由，非法集合更小）。
【拓展延伸】
完整验算要点:
d 最先出 ⇒ a,b,c 必仍在结构内。输出受限 ⇒ 只能同一端出。a,b,c 通过两端入队可得排列有限种，穷举后发现 [b,c,a] 不可达 → C 非法。
变式:
- 元素 a,b,c,d 输出受限，若 d 先出，剩余合法排列有哪些？可系统穷举验证。
- 「一端入、同端出」= 栈 → 合法序列=卡特兰数。
- 「一端入、异端出」= 队列 → 唯一序列。
工程应用：消息队列的「多生产者单消费者」、撤销栈+预览队列混合结构。
23. 以下关于队列的描述中，正确的是( )
标签：【国企笔试高频】
A. 队列是先进先出(FIFO)的结构 B. 队列是先进后出(LIFO)的结构 C. 队列具有插入和删除操作的任意性 D. 队列中没有数据元素
答案：A
【结论】 队列是先进先出(FIFO)结构，选 A。
【逐项辨析】
- B错：先进后出(LIFO)是栈的特性，不是队列。
- A 对：队列是先进先出(FIFO, First In First Out)的线性结构 —— 最先入队的元素最先出队。
- C错：队列只能在队尾入队、队头出队，不具有操作的任意性。
- D错：队列中可以存放任意多个数据元素，只是操作位置受限。
【知识点】 队列的核心特征
| 特征 | 说明 |
|---|---|
| 结构 | 线性表 |
| 操作限制 | 队尾入队(enqueue)、队头出队(dequeue) |
| 顺序 | 先进先出 FIFO |
| 基本操作 | enqueue、dequeue、getFront、isEmpty |
| 存储实现 | 顺序队列（数组）、链队列（链表）、循环队列 |
“一端进、另一端出”是队列的本质 —— 与栈的“同一端进、同一端出”恰好相反。
【记忆锚点】 “队列像排队买票，先来的先买”——先入队的最先出队(FIFO)。
【易混对比】 与栈对照（见第 19 题）。记忆主线：栈是“一摞盘子”，队列是“一条队伍” —— 盘子在顶部拿放，队伍从头出、从尾进。
【自测】 元素 a、b、c 依次入队，则第一个出队的元素是？
答：a。最先入队的最先出队。与第 19 题对照记忆。
【知识关联】
- 同库连考：与第 19 题（栈 LIFO）对题；与第 24~25 题（循环队列空/满、元素个数）构成队列专题；与第 26 题（队列应用 vs 栈应用）连考；BFS（第 56/61 题）用队列、DFS 用栈。
- 工程实现：JDK
ArrayDeque/LinkedList可当队列；BlockingQueue是并发生产者-消费者标准件；Kafka/RocketMQ 消息队列、线程池 ready queue、打印假脱机全是 FIFO 语义。逻辑上都是队列，存储上可以是循环数组或链表。 - 408 / 国企真题：408 与国网「队列的特性」定义题必考；干扰项固定是「LIFO=栈」「操作任意性=线性表/双端队列」「没有数据元素」。常与循环队列公式题连排。
- 面试追问:①「优先队列还 FIFO 吗？」（否，按优先级出队，底层常是堆）；②「双端队列何时变成普通队列？」（只允许队尾入、队头出时）；③「循环队列为何能解决假溢出？」（下标取模回绕，头尾相接）。
【拓展延伸】
变式问法:①「队列是？」（FIFO，本题）；②「栈是？」（LIFO）；③「输出受限双端队列能否得到任意序列？」（国企常考，需结合栈模拟判断）。
工程映射：CPU 中断排队、网络设备缓冲、日志异步刷盘、Web 爬虫 BFS 抓取队列、限流令牌桶，都是「先到先服务」的 FIFO 工程化。
易错提醒：「队列」与「优先队列/双端队列」不是同一概念；本题问的是经典队列。D 选项「没有数据元素」明显错——空队列是状态，不是结构定义。
24. 循环队列中，队满的判断条件是( )（设队列容量为M，队头指针front，队尾指针rear）。
标签：【互联网/国企笔试高频】
A. front == rear B. (rear + 1) % M == front C. rear == M - 1 D. front == 0
答案：B
【结论】 队满条件是 (rear + 1) % M == front —— 循环队列靠“牺牲一个存储单元”来区分队空与队满，选 B。
【逐项辨析】
- A
front == rear：这是队空条件。这正是循环队列的核心难点：若不牺牲单元，队空与队满时两指针状态完全相同，无法区分。 - B
(rear + 1) % M == front：正确。 队尾再前进一格就撞上队头，说明下一个位置已被占用，判定为满。 - C
rear == M − 1：只说明队尾指针走到了数组末尾，与队满无关（队尾可以取模绕回下标 0）。 - D
front == 0：队头恰好落在 0 号位置，与队满无关。
【知识点】 设容量 M、数组下标 0 ~ M−1,front 指向队头元素，rear 指向队尾元素的下一个位置:
| 状态 | 判断条件 | 元素个数 |
|---|---|---|
| 队空 | front == rear | 0 |
| 队满 | (rear + 1) % M == front | M − 1 |
| 一般情况 | — | (rear − front + M) % M |
容量 M = 5,已存 4 个元素:
下标: 0 1 2 3 4
[a] [b] [c] [d] [ ]
↑ ↑
front rear
队空?front ≠ rear → 否
队满?(rear+1)%5 = 0 == front → 是(尽管 4 号单元还空着)【记忆锚点】 “空则相等，满则相邻”——队空时两指针相等；队满时 rear 的下一个位置就是 front。
代价：牺牲 1 个单元，容量 M 的循环队列最多只能存 M−1 个元素 —— 这就是代码里常申请 M+1 个空间的原因。
【易混对比】 三种“循环队列”实现方式
| 实现方式 | 队满条件 | 是否牺牲空间 |
|---|---|---|
| 牺牲一个单元 | (rear+1) % M == front | 是，存 M−1 个 |
| 设标志位 tag | rear == front 且 tag = 1 | 否，存 M 个 |
| 设计数器 count | count == M | 否，存 M 个 |
【自测】 容量为 6 的循环队列（牺牲一个单元），当前 front = 3、rear = 0。先删除 1 个元素，再插入 2 个元素，此时队列中有几个元素？
答：删除后 front = 4；插入 2 个后 rear = 2。元素个数 = (2 − 4 + 6) % 6 = 4 个。国网真题库同型题。
【知识关联】
- 同库连考：与第 25 题（元素个数公式）必须连背；与第 19、23 题（栈/队列）、第 56 题（BFS 用队列）同一模块。
- 工程实现:Java
ArrayDeque用循环数组，但不牺牲空位——用count字段区分空满；教材牺牲一个单元是经典教法，工程可带计数器。 - 408 / 国企真题:408 循环队列必考空满条件；国网真题库原题。
- 面试追问:①「不用牺牲单元怎么区分空满？」（加 size 计数）；②「front 与 rear 谁指向元素谁指向空位？」（本题：front 指队头元素，rear 指队尾下一位置 —— 必须先确认约定）。
【拓展延伸】
完整验算:
容量 M=5,下标 0..4
队空:front==rear==0
入 3 个:front=0,rear=3
再入第 4 个: rear=(3+1)%5=4 成功；再入第 5 个: (4+1)%5=0==(front) → 判为队满，**该次插入被拒绝** ✓
此时可用单元 4 个,牺牲 1 个 → 最大元素数 M-1变式:
- 若 rear 指向队尾元素（不是下一位置），满条件变为
(rear+2)%M==front或改用计数。 - 链式队列无此问题，空满看 head 是否 null。
ArrayDeque双倍扩容，无牺牲单元。
工程应用：环形缓冲区 ring buffer、音频/网络收发包缓冲，都用取模环绕。
25. 循环队列中，队列长度（元素个数）的计算公式为( )
标签：【互联网/国企笔试常考】
A. rear - front B. rear + front C. (rear + front) % M D. (rear - front + M) % M
答案：D
【结论】 元素个数 = (rear − front + M) % M，选 D。
【逐项辨析】
- A错：
rear − front在队尾绕回(front > rear)时会出现负数。 - D 对：先加 M 再取模，可处理 rear < front 的情况，保证结果非负。
- C错：公式中不出现 front 与 rear 的加法。
- B错：同 C,
rear + front无意义。
【知识点】 循环队列长度公式的推导
情况 1:rear ≥ front(未绕回)
元素个数 = rear − front
情况 2:rear < front(已绕回)
元素个数 = (M − front) + rear = rear − front + M
两式统一:元素个数 = (rear − front + M) % M示例:M = 6,front = 4,rear = 2(已绕回)
个数 = (2 − 4 + 6) % 6 = 4
验证:4 → 5 → 0 → 1,共 4 个单元 → 正确加 M 是为了把负数抬到正数区间，取模是为了处理“加多了”的情况。
【记忆锚点】 “先补一整圈，再取余”——rear 跑到 front 前面去了，就先加一圈 M 补回来，再对 M 取余。
【易混对比】 三个公式一次记全
| 求什么 | 公式 |
|---|---|
| 元素个数 | (rear − front + M) % M |
| 队空 | front == rear |
| 队满 | (rear + 1) % M == front |
【自测】 M = 10 的循环队列，front = 8,rear = 3，队列中有几个元素？
答：(3 − 8 + 10) % 10 = 5 个。与第 24 题连考。
【知识关联】
- 同库连考：与第 24 题（队空/队满）公式成对记忆；自测中的 front=8,rear=3,M=10 → (3−8+10)%10=5 是经典数字。
- 工程实现:Java
ArrayDeque用tail - head+ mask;Linux kfifo 环形队列同思想。 - 408 / 国企真题:408 与国网「求循环队列元素个数」原题。
- 面试追问:①「为什么必须先 +M 再 %M？」（rear 可能小于 front,C 语言负数取模实现相关）；②「最大能存几个？」（牺牲单元时 M−1）。
【拓展延伸】
完整验算:
公式:len = (rear - front + M) % M
M=10, front=8, rear=3
(3-8+10)%10 = 5%10 = 5 ✓
若 rear=8, front=8 → 0 空
若 rear=7, front=8 → (7-8+10)%10=9 → 满(牺牲1时最大9)变式：「带 count」实现 isEmpty: count==0; isFull: count==capacity。
工程应用：无锁队列、DMA 描述符环、浏览器事件循环任务队列。
26. 以下哪个不是队列的应用场景？
标签：【互联网/国企笔试高频】
A. 操作系统的进程调度 B. 打印任务排队 C. BFS（广度优先搜索） D. 函数递归调用
答案：D
【结论】 函数递归调用用的是栈而不是队列，选 D。
【逐项辨析】
- A 进程调度：就绪队列按 FIFO 排队，是队列的典型应用。
- B 打印任务排队：先提交的先打印，遵循 FIFO，是队列的典型应用。
- C BFS（广度优先搜索）：用队列存储“待访问的邻接顶点”，保证按层扩展，是队列的典型应用。
- D 函数递归调用：使用函数调用栈（运行栈；注意不是操作系统里说的系统调用栈）保存返回地址与局部变量，是栈(LIFO)的典型应用，不是队列。
【知识点】 栈与队列的典型应用对照（必背）：
| 数据结构 | 典型应用 |
|---|---|
| 栈(LIFO) | 函数递归调用、表达式求值（中缀转后缀、后缀求值）、括号匹配、深度优先搜索 DFS、撤销操作(Undo)、浏览器后退 |
| 队列(FIFO) | 进程 / 作业调度、打印任务排队、广度优先搜索 BFS、消息队列、缓冲区、CPU 中断处理排队 |
判断技巧：凡“按到达顺序依次处理”的用队列；凡“后进先出 / 需要回溯”的用栈。
【记忆锚点】 “递归回溯用栈，排队按序用队列”。
【易混对比】 注意 DFS 与 BFS 的对照：DFS 用栈（或递归，隐式栈），BFS 用队列。这一对是图论与栈队列模块的交叉高频考点（见第 56 题）。
【自测】 下列哪一项是栈的应用？ A. 打印任务排队 B. 进程调度 C. 括号匹配 D. 消息队列
答：C。A、B、D 都是队列的应用。与第 56 题(BFS/DFS)连考。
【知识关联】
- 同库连考：与第 19/23 题（栈 vs 队列定义）配套；与第 56/61 题（BFS 用队列、DFS 用栈/递归）交叉高频；与第 60 题（拓扑排序 Kahn 法用队列）相连。
- 工程实现：JVM 调用栈保存局部变量与返回地址——递归深度过大
StackOverflowError，正是栈被压爆；线程池任务队列、消息中间件是队列；表达式求值（算符栈+操作数栈）、括号匹配、JSON/CSS 解析用栈；游戏寻路无权格子用 BFS 队列。 - 408 / 国企真题：「下列哪个不是队列的应用」两边都考，答案固定指认「递归/DFS/括号匹配/表达式求值」等栈应用；反向题「哪个是栈的应用」同理。
- 面试追问:①「递归为什么是栈？」（后调用先返回，返回地址与现场 LIFO 保存）；②「拓扑排序用什么容器？」（Kahn：入度 0 顶点入队）；③「单调队列/单调栈是？」（滑动窗口最值、下一个更大元素，属栈/队列的强化变体）。
【拓展延伸】
变式问法:①「不是队列应用的？」（函数递归，本题）；②「DFS 隐式用了什么？」（调用栈）；③「浏览器前进后退？」（双栈）。
工程映射：微服务调用链的 Trace 栈式上下文；消息队列削峰填谷；操作系统进程就绪队列；迷宫题 DFS 栈 / BFS 队列对照刷题。
易错提醒：DFS 与递归是栈，BFS 是队列，这一对几乎每套卷都考；C 选项 BFS 是队列应用，不要误判为「不是」。
27. 用两个栈可以模拟一个队列的行为。当需要执行入队操作时，应该( )
标签：【互联网面试高频】
A. 直接push到栈1 B. 将栈1所有元素pop到栈2，再push到栈1 C. 直接push到栈2 D. 同时push到两个栈
答案：A
【结论】 入队时直接 push 到栈 1（输入栈），选 A。
【逐项辨析】
- A 直接 push 到栈 1：正确。 栈 1 作为“输入栈”，所有新元素直接压入，代价 O(1)。
- B 把栈 1 全部倒到栈 2 再 push：这是“出队”时才需要做的动作，且方向反了 —— 应为“栈 1 倒入栈 2”，不是“倒出后再压回栈 1”。
- C 直接 push 到栈 2：栈 2 是“输出栈”，用于出队时弹出；直接压入会破坏 FIFO 顺序。
- D 同时 push 到两个栈：元素重复存储，完全错误。
【知识点】 两个栈模拟队列的标准方法
栈 1 = 输入栈(in) 栈 2 = 输出栈(out)
入队:直接 push 到栈 1 → O(1)
出队:① 若栈 2 非空,直接 pop 栈 2
② 若栈 2 为空,把栈 1 全部倒入栈 2,再 pop 栈 2 → 均摊 O(1)关键原理：栈 1 的元素倒入栈 2 后顺序被反转，两次反转即还原 FIFO。
入队 1, 2, 3: 栈1 = [1, 2, 3](栈顶 3)
出队:倒入栈2 栈2 = [3, 2, 1](栈顶 1)
pop 栈2 → 1 ✓ 最先入队的最先出队【记忆锚点】 “进就进 in，出时倒一次”——入队无脑压 in 栈，出队才把 in 倒进 out 栈。
【易混对比】 均摊复杂度分析：每个元素至多被倒入栈 2 一次，所以 n 次操作总代价为 O(n),均摊 O(1)。不要因为“倒栈要 O(n)”就误判为每次 O(n)。大厂面试高频，常要求手写实现并分析均摊复杂度。
【自测】 用两个栈模拟队列，连续入队 n 个元素后再连续出队 n 个元素，总时间复杂度是多少？
答：O(n)。入队 n 次 O(n)，倒栈 1 次 O(n)，出队 n 次 O(n)，合计 O(n)，均摊每次 O(1)。与第 28 题连考。
【知识关联】
- 同库连考：与第 28 题（两队列模拟栈）是完美对偶 —— 必须一起背；与第 23、24 题（队列基础）相连。
- 工程实现：面试手写高频；Java 可用两个
ArrayDeque实现；思想类似「用两个栈做 undo/redo」。 - 408 / 国企真题:408 少见；属互联网面试高频，笔试偶有变式。
- 面试追问:①「均摊复杂度？」（每个元素至多入栈 2、出栈 2 → 均摊 O(1));②「入队 O(1)、出队 O(n) 可以吗？」（可以，出队时倒栈；或反过来）。
【拓展延伸】
完整验算:
入队 a,b,c:全部进 in → in=[a,b,c]
出队:把 in 倒入 out → out=[c,b,a],再 pop → a ✓
再出:out 继续 pop → b
若 out 空且 in 有货,再倒一次
n 次入+出,每元素倒 1 次 → 总 O(n),均摊 O(1)变式：一个栈+一个队列模拟栈/队列；两个栈模拟队列见第 27 题（本题）。
工程应用：日志缓冲与刷盘顺序、撤销栈与回放队列。
28. 用两个队列模拟一个栈，入栈操作时应该( )
标签：【互联网面试高频】
A. 将元素入队到非空的那个队列 B. 将元素入队到空的那个队列 C. 同时入队到两个队列 D. 随意选择一个队列
答案：A
【结论】 入栈时把元素入队到非空的那个队列，选 A。
【逐项辨析】
- A 入队到非空队列：正确。 保持所有元素集中在同一个队列中，另一个队列留空备用。
- B 入队到空队列：会导致元素分散在两个队列，破坏后续出栈逻辑。
- C 同时入队到两个队列：元素重复，完全错误。
- D 随意选择：元素会分散，无法保证 LIFO 顺序。
【知识点】 两个队列模拟栈的标准方法
队列 q1、q2,始终只有一个非空(存放全部元素)
入栈:把元素入队到非空的那个队列 → O(1)
出栈:把非空队列中除最后一个元素外的所有元素依次出队,
并入队到另一个队列,最后把剩下的那个元素出队 → O(n)模拟过程（入栈 1, 2, 3，再连续出栈）：
| 操作 | q1 | q2 | 出栈结果 |
|---|---|---|---|
| 入栈 1 | [1] | [] | — |
| 入栈 2 | [1, 2] | [] | — |
| 入栈 3 | [1, 2, 3] | [] | — |
| 出栈 | [] | [1, 2] | 出 3 ✓ |
| 出栈 | [1] | [] | 出 2 ✓ |
| 出栈 | [] | [] | 出 1 ✓ |
【记忆锚点】 “留一个、挪一堆”——出栈时把前面的元素全部挪到另一个队列，只留下最后一个出队。
【易混对比】 两个栈模拟队列 vs 两个队列模拟栈
| 两个栈模拟队列 | 两个队列模拟栈 | |
|---|---|---|
| 入操作代价 | O(1) | O(1) |
| 出操作代价 | 均摊 O(1) | O(n) |
| 效率 | 较高 | 较低 |
结论：两栈模拟队列的效率明显优于两队列模拟栈 —— 前者均摊 O(1)，后者每次出栈都要挪动 O(n) 个元素。这一对比常被作为面试追问。
【自测】 两个队列模拟栈，连续入栈 n 个元素后再连续出栈 n 个元素，总时间复杂度是多少？
答：O(n²)。每次出栈需挪动 O(n) 个元素，共 n 次出栈 → O(n²)。与第 27 题对照记忆。
【知识关联】
- 同库连考：与第 27 题（双栈模拟队列）对偶连背；与第 19、23 题（栈队列定义）基础。
- 工程实现：面试手写；「留一个、挪一堆」是标准解；复杂度分析常被追问——单次出栈 O(n)、连续入 n 再连续出 n 的总代价为 Θ(n²)（搬运 n(n−1)/2 次），不存在「均摊 O(1)」。
- 408 / 国企真题：互联网面试高频；国企偶见。
- 面试追问:①「入栈和出栈谁贵？」（出栈要把前面 n−1 个挪走）；②「能否入栈 O(n) 出栈 O(1)？」（可以：入时把另一队列元素全部搬过来再入，再搬回）。
【拓展延伸】
完整验算:
入 1,2,3 到 q1
出栈:q1 出 1,2 到 q2,再出 3 → 3 ✓
再出:q2 现有 1,2,把 1 挪回 q1,出 2 ✓
连续入 n 再连续出 n:总搬运多少次?—— 设某次出栈时队列里有 s 个元素,必须先搬走 s−1 个才露出要出栈的那个
总计 Σ(s−1)=(n−1)+(n−2)+...+1+0=n(n−1)/2=Θ(n²)(n=6 实跑 15 次搬运,与 6×5/2=15 吻合)→ 单次出栈均摊 O(n),不是均摊 O(1)变式:k 个队列模拟栈的最小 k 研究；两栈模拟队列见第 27 题。
工程应用：理解「用受限原语表达更丰富语义」——操作系统用信号量模拟各种同步结构。
29. 设计一个支持 push、pop、top 操作，且能在常数时间 O(1) 内获取最小元素的栈(Min Stack)，最常用的实现是( )
标签：【互联网面试高频】
A. 单个栈 B. 两个栈：数据栈 + 辅助栈同步记录当前栈内最小值 C. 一个栈加一个数组 D. 双端队列
答案：B【结论】 最小栈最常用的实现是“数据栈 + 辅助栈”，选 B。
【逐项辨析】
- A 单个栈：只存数据无法 O(1) 得到最小值（除非遍历，为 O(n))。
- B 两个栈（数据栈 + 辅助栈）：正确。 辅助栈与数据栈同步记录“当前栈内最小值”，getMin 直接读辅助栈栈顶。
- C 一个栈加一个数组：数组若随栈同步维护最小值，本质仍是“辅助栈”，只是换了个名字；若不同步则无法 O(1) 取最小。
- D 双端队列：双端队列解决的是两端操作问题，与“O(1) 取最小值”无关。
【知识点】 最小栈(Min Stack)的实现
数据栈 data:正常 push / pop
辅助栈 minSt:与 data 同步
push(x): data.push(x); minSt.push(min(x, minSt.top()))
pop(): data.pop(); minSt.pop()
top(): return data.top()
getMin(): return minSt.top()模拟（依次 push 5, 3, 7, 2，再 pop 一次）：
| 操作 | data 栈 | minSt 栈 | getMin |
|---|---|---|---|
| push 5 | [5] | [5] | 5 |
| push 3 | [5, 3] | [5, 3] | 3 |
| push 7 | [5, 3, 7] | [5, 3, 3] | 3 |
| push 2 | [5, 3, 7, 2] | [5, 3, 3, 2] | 2 |
| pop | [5, 3, 7] | [5, 3, 3] | 3 |
两栈深度始终一致，四个操作全部 O(1)。
【记忆锚点】 “辅助栈跟数据栈同呼吸，每层都记住当时的最小值”。
【易混对比】 另一种优化实现：只在“新值 ≤ 当前最小值”时才压入辅助栈，可节省空间，但 pop 时要判断“弹出的值是否等于辅助栈栈顶”才决定是否弹出辅助栈。两种实现思路不同、复杂度相同，面试中常被追问区别。
【自测】 最小栈中 getMin 的时间复杂度是多少？为什么？
答：O(1)。因为辅助栈栈顶始终保存当前栈内最小值，直接读取即可，无需遍历。LeetCode 155 原题，大厂面试手写高频。
【知识关联】
- 同库连考：与第 14 题（单调队列）、第 93 题(TopK)同属「维护最值」；与第 19、26 题（栈应用）相连。
- 工程实现:LeetCode 155 经典；Java 用两个
Deque<Integer>；优化版「只在更小或相等时压辅助栈」节省空间。 - 408 / 国企真题：互联网面试超高频；国企笔试少见。
- 面试追问:①「push/pop/top/min 都要 O(1)」如何同时满足？（辅助栈同步或存差值）；②「为什么不能用一个变量存 min？」（pop 后不知次小值）。
【拓展延伸】
完整验算:
序列 push 3,2,0,4 时辅助栈(存历史最小):
3 → [3]
2 → [3,2]
0 → [3,2,0]
4 → 若「总是压入当前min」→ [3,2,0,0];getMin=0
pop 4 → 辅助 pop → min 仍 0
pop 0 → 辅助 pop → min=2变式：最大栈；「min 栈 + 计数」压缩空间；差值法用一个栈存「与当前 min 的差」。
工程应用：监控「运行至今最小水位」、交易系统「当日最低价」滚动窗口之外的全局 min。
30. 在栈的应用中，后缀表达式（逆波兰表达式）3 4 + 5 × 6 - 的计算结果是( )
标签：【互联网/国企笔试常考】
A. 25 B. 29 C. 31 D. 19
答案：B
【结论】 后缀表达式 3 4 + 5 × 6 − 的计算结果为 29，选 B。
【推导过程】 从左到右扫描，遇操作数入栈，遇运算符弹出两个操作数运算后结果入栈
| 步骤 | 读入 | 操作 | 栈内容（底→顶） |
|---|---|---|---|
| 1 | 3 | push 3 | [3] |
| 2 | 4 | push 4 | [3, 4] |
| 3 | + | pop 4、3，算 3+4=7,push 7 | [7] |
| 4 | 5 | push 5 | [7, 5] |
| 5 | × | pop 5、7，算 7×5=35,push 35 | [35] |
| 6 | 6 | push 6 | [35, 6] |
| 7 | − | pop 6、35，算 35−6=29,push 29 | [29] |
最终结果 = 29。
【逐项辨析】
- A 25：中途某步运算顺序颠倒或漏算。
- B 29：正确。 按上表逐步模拟得 29。
- C 31：算错中间结果（如把 7×5 算成 35 后误加）。
- D 19：中途把 7×5 误算成 25（与 5×5 混淆），再算 25−6=19；属纯计算错误。注意它不是左右操作数颠倒的结果——颠倒减法得 6−35=−29，取绝对值仍是 29（正确值），推不出 19。
【知识点】 后缀表达式（逆波兰表达式）求值规则
从左到右扫描:
遇操作数 → 入栈
遇运算符 → 弹出两个操作数,运算后把结果压回栈
扫描结束,栈中唯一元素即为结果关键易错点：减法与除法是“次顶元素 op 栈顶元素” —— 即先弹出的作右操作数，后弹出的作左操作数。上表中算 35−6 时，先 pop 出 6（右操作数）、后 pop 出 35（左操作数），故为 35 − 6。
中缀转后缀的规则（必背）：操作数直接输出；运算符入栈前，把栈中优先级 ≥ 它的运算符先弹出输出；遇 （ 入栈，遇 ） 弹出到 ( 为止。
【记忆锚点】 “先弹的是右手，后弹的是左手”——减法和除法一定要注意左右顺序，否则 35−6 会被算成 6−35。
【易混对比】 三种表达式对照
| 表达式 | 形式 | 扫描方向 | 运算符位置 |
|---|---|---|---|
| 中缀 | 3 + 4 × 5 − 6 | — | 操作数之间 |
| 后缀（逆波兰） | 3 4 + 5 × 6 − | 从左到右 | 操作数之后 |
| 前缀（波兰） | − × + 3 4 5 6 | 从右到左 | 操作数之前 |
【自测】 中缀表达式 (3 + 4) × 5 对应的后缀表达式是什么？其值是多少？
答：后缀为 3 4 + 5 ×，值为 35。与本题同型，国网与 408 均考过。
【知识关联】
- 同库连考：与第 27、28 题（栈队列互模）、第 19 题（栈 LIFO）、第 21 题（出栈序列）同一知识面；表达式与编译原理、离散数学前缀/中缀/后缀互化相关。
- 工程实现:Java 脚本引擎、计算器 App、LLVM IR 后缀式求值；
Deque作操作数栈。 - 408 / 国企真题:408「栈的应用」必含后缀表达式；国网真题库常考计算结果。
- 面试追问:①「中缀转后缀用什么？」（算符栈 + 输出）；②「前缀表达式如何求值？」（从右向左扫描，遇运算符弹两操作数）。
【拓展延伸】
完整验算:
3 4 + 5 × 6 −
读 3,4 → 遇 + → 7 入栈
读 5 → 遇 × → 7×5=35
读 6 → 遇 − → 35−6=29 ✓变式:
- 中缀
(3+4)*5-6→ 后缀3 4 + 5 * 6 -。 - 前缀
- * + 3 4 5 6同值 29。 - 含一元负号、幂运算右结合要改扫描方向/优先级表。
工程应用:Shunting-yard 算法、RPN 计算器（HP 经典）、编译器后端指令选择。