栈和队列
栈和队列是两种"受限"的数据结构。面试官想知道你不只是会用，而是理解为什么需要这些限制。
面试考察点
面试官通过这道题想考察：
1. 你是否理解"受限"数据结构的意义
2. 你是否能举出实际的应用场景
3. 你是否能解释函数调用栈的原理
4. 你是否能理解"单调栈"这种扩展思想
一、栈（Stack）
1.1 什么是栈？（入门级解释）
现实类比：叠盘子
┌─────┐
│盘子4│ ← 最后放上去的，最先被拿走
├─────┤
│盘子3│
├─────┤
│盘子2│
├─────┤
│盘子1│ ← 最先放上去的，最后被拿走
└─────┘
特点：后进先出（Last In First Out, LIFO）
专业解释：
栈是一种只允许在"一端"进行插入和删除的线性表。
这一端叫"栈顶"（Top）
另一端叫"栈底"（Bottom）
操作：
- push(x)：把 x 压入栈顶
- pop()：弹出栈顶元素
- top()：查看栈顶元素（不弹出）
- empty()：判断是否为空
1.2 栈的核心原理（面试必问）
面试官追问："栈为什么叫'后进先出'？这个限制有什么用？"
我来解释栈的核心思想：
栈就像一个桶：
- 只从上面放东西（push）
- 只从上面取东西（pop）
- 你永远动不到下面的东西
这有什么用？
1. 历史记录：撤销操作
你写了很多字，现在 Ctrl+Z 撤销，
栈会弹出最近的操作，逆序恢复。
2. 函数调用：保存调用现场
main() 调用 func1()，func1() 调用 func2()
调用顺序：main → func1 → func2
返回顺序：func2 → func1 → main
正好符合栈的 LIFO 特性！
3. 括号匹配：消除嵌套关系
( ( ( ) ) ) ← 括号是嵌套的，用栈来处理
1.3 函数调用栈的原理（面试高频追问）
面试官追问："你能说说函数调用时栈里发生了什么？"
这是必须理解的知识点！
代码执行顺序：
function outer() {
let a = 1; // 第2步
inner(); // 第3步
let b = 2; // 第5步
}
function inner() {
let x = 10; // 第4步
console.log(x);
}
outer(); // 第1步
调用栈的变化过程：
Step 1: outer() 被调用
┌─────────────────┐
│ outer() │ ← 栈顶
│ 返回地址: main │
│ 变量: a = ? │
└─────────────────┘
Step 2: a = 1 执行
┌─────────────────┐
│ outer() │
│ a = 1 │
└─────────────────┘
Step 3: inner() 被调用（outer 暂停）
┌─────────────────┐
│ inner() │ ← 栈顶
│ x = ? │
├─────────────────┤
│ outer() 暂停 │
│ a = 1 │
└─────────────────┘
Step 4: inner() 执行完毕，弹出
┌─────────────────┐
│ outer() 恢复 │ ← 栈顶
│ a = 1 │
└─────────────────┘
Step 5: outer() 继续执行完毕，弹出
┌─────────────────┐
│ (空) │
└─────────────────┘
面试加分点：递归调用就是函数调用栈的应用！
递归调用（计算阶乘）：
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
factorial(4) 的调用栈：
factorial(4)
↓ 调用
factorial(3)
↓ 调用
factorial(2)
↓ 调用
factorial(1) → 返回 1
↑
factorial(2) → 返回 2*1 = 2
↑
factorial(3) → 返回 3*2 = 6
↑
factorial(4) → 返回 4*6 = 24
这就是为什么递归太深会"栈溢出"！
栈的深度 = 递归调用的层数
1.4 栈的实际应用场景
| 应用 | 说明 | 面试能说出来吗？ |
|---|---|---|
| 函数调用 | 保存调用现场，递归就是栈的应用 | 必须理解 |
| 括号匹配 | 编译器用栈检查语法错误 | 常见面试题 |
| 表达式求值 | 中缀转后缀，后缀求值 | 经典算法题 |
| 浏览器前进/后退 | 后退就是弹出之前访问的页面 | 实际应用 |
| 编辑器撤销 | Ctrl+Z 就是弹出操作历史 | 实际应用 |
1.5 单调栈（进阶扩展）
面试追问："你知道单调栈吗？什么时候用？"
普通栈：只管 LIFO
单调栈：栈内元素保持单调递增或递减
应用：找下一个更大/更小的元素
示例：求每个元素的"下一个更大元素"
nums = [2, 1, 2, 4, 3]
单调递减栈（栈顶最小）：
遍历元素，维护栈：
2: 栈空，2 入栈 stack = [2]
1: 1 < 2，2 弹出，1 入栈 stack = [1]
→ 2 的下一个更大是 1
2: 2 > 1，2 入栈 stack = [1, 2]
4: 4 > 2，2 弹出 stack = [1, 4]
→ 2 的下一个更大是 4
→ 1 的下一个更大是 4
3: 3 < 4，3 入栈 stack = [1, 4, 3]
结果：2→1, 1→4, 2→4, 4→null, 3→null
二、队列（Queue）
2.1 什么是队列？（入门级解释）
现实类比：银行排队
队首 队尾
↑ ↑
[张三] [李四] [王五] [赵六] →
↑
先来的先服务
特点：先进先出（First In First Out, FIFO）
和栈的区别：
栈（一端操作）： 队列（两端操作）：
┌───────────┐ ┌───────────┐
│ 只能从 │ │ 队尾进 │
│ 栈顶操作 │ │ 队首出 │
└───────────┘ └───────────┘
2.2 队列的核心原理
队列就像排队买东西：
- 新来的人从队尾加入（enqueue）
- 服务员从队首服务（dequeue）
这就是为什么叫"先进先出"——先来的先被服务。
2.3 队列的实际应用
| 应用 | 说明 |
|---|---|
| 任务调度 | 操作系统用队列管理待执行的任务 |
| 广度优先搜索（BFS） | 图/树的层序遍历用队列 |
| 消息队列 | 异步通信，解耦生产者和消费者 |
| 打印队列 | 多个打印任务排队 |
| 滑动窗口 | 单调队列实现 O(n) 滑动窗口 |
2.4 什么是循环队列？（面试追问）
面试官追问："普通队列有什么问题？什么是循环队列？"
普通队列的问题：
假设队列大小是 5：
初始：[空] [空] [空] [空] [空]
front rear
↑ ↑
（队首） （队尾）
入队 3 个元素：
[A] [B] [C] [空] [空]
front ↑
rear
入队 2 个元素：
[A] [B] [C] [D] [E]
↑
rear
出队 3 个：
[空] [空] [空] [D] [E]
↑
front/rear
问题：队列没满，但队尾已经到头了！
队首虽然有空位，但无法入队！
这就是"假溢出"问题。
循环队列的解决方案：
循环队列：把队列想象成一个环
rear
↓
┌──[ ]──┐
/ \
[ ] [ ]
\ /
└──[ ]──┘
↑
front
关键：rear 到达末尾后，绕回开头
front 到达末尾后，也绕回开头
判断队满/队空：
- 队空：front == rear
- 队满：(rear + 1) % n == front
2.5 双端队列（Deque）
面试追问："什么是双端队列？有什么用？"
Deque = Double Ended Queue
两端都可以入队和出队：
┌────────────────────────────────────┐
│ 队首 ←→ [元素] ←→ [元素] ←→ 队尾 │
└────────────────────────────────────┘
可以当：
1. 栈用（从一端进出一端）
2. 普通队列用（一段进另一端出）
3. 滑动窗口（两端都用到）
滑动窗口最大值：
用单调递减的双端队列，
每次窗口滑动时：
- 从队尾加入新元素
- 从队首移除超出窗口的元素
- 队首就是当前窗口最大值
三、面试真题讲解
题目1：有效的括号（LeetCode 20）
考察点：栈的应用 + 边界条件处理
问题：给一个字符串，判断括号是否匹配
"({[]})" → true
"([)]" → false
核心思想：
1. 遇到左括号，入栈
2. 遇到右括号，检查栈顶是否有匹配的左括号
3. 匹配则弹出，不匹配则 false
4. 最后栈空才是 true
面试官追问：为什么要用栈？
回答：因为括号是嵌套的！
最近看到的左括号，应该最先被匹配。
这就是栈的 LIFO 特性！
"({[]})"
↑
看到 {，期望后面有 } 来匹配它
看到 (，期望后面有 ) 来匹配它
最内层的 { } 先被匹配，这不就是栈吗？
题目2：最小栈（LeetCode 155）
考察点：设计数据结构，理解栈的变体
问题：设计一个栈，还要能 O(1) 获取最小值
普通栈只能 O(1) 获取栈顶
但最小值需要 O(n) 查找
如何 O(1) 获取最小值？
方案：用一个辅助栈存储"当前最小值"
stack: [5, 2, 3, 1, 4]
minStack: [5, 2, 2, 1, 1]
↑ ↑ ↑ ↑ ↑
每一步的最小值
push(x):
stack.push(x)
minStack.push(min(x, minStack.top()))
pop():
stack.pop()
minStack.pop()
top():
return stack.top()
getMin():
return minStack.top()
面试追问：空间能优化吗？
回答：可以把最小值存为 (value, min) 的元组，
或者用数学方法（存差值），
但会增加代码复杂度。
题目3：滑动窗口最大值（LeetCode 239）
考察点：单调队列的高级应用
问题：求滑动窗口的最大值
nums = [1,3,-1,-3,5,3,6,7], k=3
滑动窗口：
[1,3,-1] → 最大是 3
[3,-1,-3] → 最大是 3
[-1,-3,5] → 最大是 5
[-3,5,3] → 最大是 5
[5,3,6] → 最大是 6
[3,6,7] → 最大是 7
答案：[3,3,5,5,6,7]
单调队列的原理：
核心思想：维护一个单调递减的队列
遍历数组：
1. 从队尾加入新元素
2. 从队首移除超出窗口的元素
3. 队首就是当前窗口最大值
详细过程（k=3）：
[1] → 队列 [1]，输出 null（窗口未形成）
[1,3] → 3>1，1 弹出，队列 [3]
[1,3,-1]→ -1<3，入队，队列 [3,-1]，输出 3
[3,-1,-3]→ -3<-1，-1弹出，-3入队，队列 [3,-3]，输出 3
[-1,-3,5]→ 5>-3，-3弹出，5入队，队列 [5]，输出 5
[-3,5,3] → 3<5，入队，队列 [5,3]，输出 5
[5,3,6] → 6>3,6>5，3和5弹出，6入队，队列 [6]，输出 6
[3,6,7] → 7>6，6弹出，7入队，队列 [7]，输出 7
为什么这样做是对的？
因为新加入的元素比队列里所有元素都大，
那么队列里所有元素都不可能成为最大值了！
这就是"单调性剪枝"。
四、面试总结
栈和队列的核心区别
┌─────────────────────────────────────────────────┐
│ 线性表 │
│ │
│ ┌───────────────┐ ┌───────────────┐ │
│ │ 栈 │ │ 队列 │ │
│ │ (Stack) │ │ (Queue) │ │
│ ├───────────────┤ ├───────────────┤ │
│ │ 只在一端操作 │ │ 两端操作 │ │
│ │ LIFO │ │ FIFO │ │
│ │ 撤销/返回 │ │ 排队/调度 │ │
│ └───────────────┘ └───────────────┘ │
└─────────────────────────────────────────────────┘
常见追问汇总
| 追问 | 考察点 | 回答要点 |
|---|---|---|
| 函数调用栈是什么？ | 操作系统基础 | 保存调用现场，递归就是栈的应用 |
| 递归为什么可能栈溢出？ | 调用栈深度 | 栈空间有限，递归太深会耗尽 |
| 括号匹配为什么用栈？ | LIFO 特性 | 最近看到的左括号最先匹配 |
| 什么是循环队列？ | 队列优化 | 解决假溢出，首尾相连 |
| 什么是单调栈/单调队列？ | 进阶应用 | 保持单调性，O(n) 优化 |
面试能加分的回答
1. 知道栈在函数调用中的应用
"函数调用的返回地址、参数、局部变量都存在栈里"
2. 知道递归和栈的关系
"递归本质上是函数调用栈的应用，循环是递归的迭代版本"
3. 知道滑动窗口最大值用单调队列
"维护单调递减队列，队首是最大值，O(n) 时间"
4. 知道队列在 BFS 中的应用
"树的层序遍历、图的最短路径都用队列"
相关题目
- LeetCode 20 - 有效的括号 - 栈基础
- LeetCode 155 - 最小栈 - 辅助栈
- LeetCode 239 - 滑动窗口最大值 - 单调队列
- LeetCode 84 - 柱状图中最大的矩形 - 单调栈进阶