栈基础与设计模式 - 面试完全指南
掌握栈数据结构面试要点。学习有效括号 (LC 20)、逆波兰表达式求值 (LC 150)、最小栈 (LC 155) 以及栈队列互相实现，配合交互式可视化和可复用模板。
概述
栈 是计算机科学中最基础的数据结构之一，也是编程面试中的热门考点。它的 LIFO（后进先出） 特性使其非常适合处理以下问题：
- 匹配配对 （括号、标签）
- 表达式求值 （后缀、中缀）
- 回溯 （撤销操作、深度优先搜索）
- 设计问题 （最小栈、浏览器历史记录）
为什么面试官喜欢考栈
- 考察基础功底 - 基本的 push/pop 操作看似简单，但正确使用需要扎实的逻辑能力
- 优雅的解法 - 很多复杂问题用栈思维可以变得很简单
- 设计模式 - 基于栈的设计考察创建高效数据结构的能力
- 进阶题目的基础 - 单调栈、递归消除、语法解析
栈基础
LIFO 原则
栈操作:
┌───┐
push(3) ───────►│ 3 │ ← 栈顶
├───┤
│ 2 │
├───┤
│ 1 │
└───┘
pop() 返回 3:
┌───┐
│ 2 │ ← 新栈顶
├───┤
│ 1 │
└───┘核心操作
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
push(x) | 元素入栈（添加到栈顶） | O(1) |
pop() | 弹出并返回栈顶元素 | O(1) |
peek()/top() | 返回栈顶元素（不弹出） | O(1) |
isEmpty() | 检查栈是否为空 | O(1) |
什么时候使用栈
- 需要逆序处理元素
- 匹配开闭符号
- 追踪状态且需要撤销
- 将递归转换为迭代
题目一：有效括号 (LC 20)
问题描述
给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 每个右括号都有一个对应的相同类型的左括号
解题思路
把括号想象成俄罗斯套娃：
- 每个左括号开启一个新的”层级”
- 每个右括号应该匹配最近的未匹配左括号
- 栈天然地追踪这种”最近”的关系
输入: "({[]})"
逐步分析:
'(' → 入栈 → stack: ['(']
'{' → 入栈 → stack: ['(', '{']
'[' → 入栈 → stack: ['(', '{', '[']
']' → 匹配 '[' → 出栈 → stack: ['(', '{']
'}' → 匹配 '{' → 出栈 → stack: ['(']
')' → 匹配 '(' → 出栈 → stack: []
结果: 栈为空 → 有效 ✓代码实现
交互式可视化
复杂度分析
- 时间: - 单次遍历字符串
- 空间: - 最坏情况全是左括号
边界情况
- 空字符串 → 有效
- 单个括号 → 无效
- 全是左括号 → 无效
- 类型不匹配
"(]"→ 无效 - 顺序错误
"([)]"→ 无效
题目二：逆波兰表达式求值 (LC 150)
问题描述
根据逆波兰表示法（后缀表达式），求表达式的值。
有效的运算符包括 +、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意：除法向零截断。
什么是逆波兰表达式
逆波兰表达式把运算符放在操作数后面：
| 中缀表达式 | 逆波兰表达式 |
|---|---|
1 + 2 | 1 2 + |
(1 + 2) * 3 | 1 2 + 3 * |
4 + 13 / 5 | 4 13 5 / + |
解题思路
逆波兰表达式天生适合栈求值：
- 数字 → 入栈
- 运算符 → 弹出两个操作数，计算，结果入栈
输入: ["2", "1", "+", "3", "*"]
逐步分析:
"2" → 入栈 2 → stack: [2]
"1" → 入栈 1 → stack: [2, 1]
"+" → 弹出 1、2 → 2+1=3 → 入栈 3 → stack: [3]
"3" → 入栈 3 → stack: [3, 3]
"*" → 弹出 3、3 → 3*3=9 → 入栈 9 → stack: [9]
结果: 9代码实现
交互式可视化
关键要点
-和/的顺序很重要：先弹出b，再弹出a，计算a op b- 除法向零截断：Java/JS 自动实现；Python 需要
int(a/b) - 最终只剩一个元素：就是最终结果
复杂度分析
- 时间: - 每个 token 处理一次
- 空间: - 栈最多存放 n/2 个数字
题目三：最小栈 (LC 155)
问题描述
设计一个支持以下操作的栈：
push(val)- 元素入栈pop()- 移除栈顶元素top()- 获取栈顶元素getMin()- 在 O(1) 时间内检索栈中最小元素
难点
朴素的 getMin() 是 O(n) - 需要遍历整个栈。但我们需要 O(1)！
为什么不能直接排序？ 因为栈是一个动态数据结构：
- 元素不断地被添加和移除
- 每次查询都排序需要 O(n log n)
- 我们需要最小值能够随着元素的进出自动更新
核心洞察：前缀最小值
让最小栈能够 O(1) 工作的关键洞察是：最小栈本质上就是在维护前缀最小值！
想一想——在任意时刻，栈中的元素恰好是 [element_0, element_1, ..., element_top]。最小值就是：
min(element_0, element_1, ..., element_top) = prefixMin[top]为什么这对栈有效？
- LIFO 特性：元素只能从栈顶移除
- 当我们在索引 i 处压入元素时：
prefixMin[i] = min(prefixMin[i-1], element[i]) - 当我们弹出时：位置
top-1的前缀最小值仍然有效！
示例：压入序列 [3, 5, 2, 7, 1]
索引: 0 1 2 3 4
元素: 3 5 2 7 1
前缀最小: 3 3 2 2 1 ← 截止到该位置所有元素的最小值
弹出 1 时: prefixMin[3] = 2 对于 [3,5,2,7] 仍然正确
弹出 7 时: prefixMin[2] = 2 对于 [3,5,2] 仍然正确为什么弹出时不需要重新扫描？
神奇之处在于前缀最小值与后来的元素无关。[3,5,2] 的最小值不会因为我们后来压入 7、1 或任何其他元素而改变。这与”滑动窗口最小值”等问题有本质区别——在那里窗口可以移动。
解题思路：双栈法
维护一个辅助栈来追踪每一层的最小值：
操作: push(-2), push(0), push(-3), getMin, pop, top, getMin
主栈 最小栈 说明
[] [] 初始状态
[-2] [-2] -2 是当前最小值
[-2,0] [-2] 0 > -2，最小值不变
[-2,0,-3] [-2,-3] -3 <= -2，入最小栈
getMin() → -3 (最小栈栈顶)
[-2,0] [-2] 弹出 -3，等于最小值，最小栈也弹出
top() → 0
getMin() → -2代码实现
交互式可视化
为什么这样做有效
- 入栈时，如果是新的最小值（或相等），就记录下来
- 出栈时，如果弹出的是当前最小值，最小栈也要弹出
- 最小栈的栈顶始终是当前栈状态的最小值
替代方案：单栈存储元组
存储 (value, currentMin) 对：
def push(self, val):
if not self.stack:
self.stack.append((val, val))
else:
self.stack.append((val, min(val, self.stack[-1][1])))复杂度分析
- 时间: 所有操作都是
- 空间: - 最小栈可能和主栈一样大
扩展：最小队列
理解了最小栈之后，一个自然的问题是：能否构建一个最小队列？
队列是 FIFO（先进先出），这与栈的 LIFO 看起来完全不同。在队列中，我们从前端移除但从后端添加——所以”前缀最小值”技巧不能直接使用。
队列的难点
队列: [3, 1, 4, 1, 5] (从前到后)
↑ ↑
出队在这里 入队在这里
出队 3 时: 最小值仍然是 1 ✓
出队 1 时: 最小值变成 1（另一个 1）最小值取决于中间的元素——我们不能只追踪前缀！
解法：双最小栈
还记得我们如何用两个栈实现队列吗？我们可以用两个最小栈做同样的事！
inStack: 接收入队操作，追踪"右半部分"的最小值
outStack: 服务出队操作，追踪"左半部分"的最小值
总体最小值 = min(inStack.getMin(), outStack.getMin())每个栈独立维护其前缀最小值。当我们将元素从 inStack 转移到 outStack 时，它们会被反转——这正是 FIFO 行为所需要的，而且我们在转移过程中为 outStack 重建前缀最小值。
为什么双最小栈有效
- Push：添加到
inStack并更新minSoFar→ O(1) - Pop：从
outStack弹出，为空时转移 → 均摊 O(1) - GetMin：比较两个栈的栈顶 → O(1)
每个元素最多被转移一次，所以所有操作都是均摊 O(1)。
使用场景
- 滑动窗口最小值（窗口大小可变时）
- 需要最小/最大值追踪的队列算法
- 带有最小/最大指标的限流器
扩展：双端最小队列
如果我们需要一个支持 O(1) 最小值查询的**双端队列（deque）**呢？
双端队列允许从两端进行 push/pop：
pushFront(val),pushBack(val)popFront(),popBack()getMin()- 仍然是 O(1)！
前缀最小值的问题
对于双端队列，元素可以从任一端移除。我们的前缀最小值技巧失效了：
双端队列: [3, 1, 4] 从左计算的前缀最小: [3, 1, 1]
从右计算的后缀最小: [1, 1, 4]
如果 popFront() 移除 3: 需要后缀信息
如果 popBack() 移除 4: 需要前缀信息单独的前缀或后缀都不够用！
解法：单调双端队列
不追踪前缀最小值，而是维护一个单调双端队列——一个元素始终保持非递减顺序的双端队列。
主双端队列: [3, 1, 4, 1, 5]
单调双端队列: [1, 1, 5] ← 只有可能成为最小值的元素
关键洞察：如果我们依次压入 2、3、1...
- 当 1 到来时，3 和 2 在 1 存在期间永远不可能是最小值
- 所以我们从单调队列中移除它们！单调双端队列的前端始终是当前最小值。
单调双端队列如何维护最小值
pushBack(val) 时：
- 从后端移除所有 > val 的元素（它们永远不会是最小值）
- 将 val 添加到后端
pushFront(val) 时：
- 从前端移除所有 > val 的元素
- 将 val 添加到前端
popFront/popBack 时：
- 如果移除的值等于单调队列的前端/后端，也一并移除
GetMin： 直接返回单调队列的前端！
对比：最小栈 vs 最小队列 vs 最小双端队列
| 特性 | 最小栈 | 最小队列 | 最小双端队列 |
|---|---|---|---|
| 核心技术 | 前缀最小值 | 双最小栈 | 单调双端队列 |
| Push | O(1) | O(1) | 均摊 O(1) |
| Pop | O(1) | 均摊 O(1) | O(1) |
| GetMin | O(1) | O(1) | O(1) |
| 空间 | O(n) | O(n) | O(n) |
| 复杂度 | 简单 | 中等 | 最复杂 |
实际应用
- 滑动窗口最大/最小值 (LC 239) - 经典单调队列问题
- 跳跃游戏 VI (LC 1696) - 单调队列优化 DP
- 和至少为 K 的最短子数组 (LC 862) - 单调队列优化
题目四：用队列实现栈 (LC 225)
问题描述
仅使用队列的基本操作（push、peek/front、pop、empty）实现一个后进先出（LIFO）的栈。
解题思路
队列是先进先出，但我们需要后进先出。技巧：每次入栈后旋转元素，使最新元素在队首。
Push 1: queue = [1]
Push 2: queue = [2] → 旋转 → queue = [2, 1]
Push 3: queue = [3, 2, 1] → 实际过程:
[3] → [3,2,1] → 旋转 2 次 → [3,2,1]
实际: push 3，然后把 2 个元素移到后面:
[2,1,3] → [1,3,2] → [3,2,1]代码实现
旋转原理
push(3) 之前: queue = [2, 1] (2 在队首 = 栈顶)
1. 添加 3 到队尾: queue = [2, 1, 3]
2. 把 2 移到队尾: queue = [1, 3, 2]
3. 把 1 移到队尾: queue = [3, 2, 1]
现在 3 在队首 = 新栈顶 ✓复杂度分析
- Push: - 需要旋转 n-1 个元素
- Pop/Top/Empty:
题目五：用栈实现队列 (LC 232)
问题描述
仅使用栈的基本操作（push、pop、peek、empty）实现一个先进先出（FIFO）的队列。
解题思路：双栈法
使用两个栈：
inStack：接收所有入队操作outStack：服务所有出队/查看操作
当 outStack 为空时，把 inStack 的所有元素转移过来 - 这会反转顺序，从而实现先进先出！
push(1), push(2), push(3):
inStack = [1, 2, 3] (3 在栈顶)
outStack = []
pop():
outStack 为空 → 转移: 从 inStack 弹出，压入 outStack
inStack = []
outStack = [3, 2, 1] (1 在栈顶)
从 outStack 弹出 → 返回 1 ✓ (先进先出！)代码实现
为什么是均摊 O(1)
每个元素：
- 入
inStack一次 - O(1) - 转移到
outStack一次 - O(1) - 从
outStack弹出一次 - O(1)
总计：每个元素 3 次操作，均摊 O(1)。
复杂度分析
- Push:
- Pop/Peek: 均摊 ，最坏
- Empty:
模板与套路
套路一：匹配配对
用于匹配开闭元素的场景：
def matchingPattern(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in pairs.values(): # 开符号
stack.append(char)
elif char in pairs: # 闭符号
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0套路二：表达式求值
用于后缀/前缀求值或计算器问题：
def evaluateExpression(tokens):
stack = []
for token in tokens:
if is_operator(token):
b, a = stack.pop(), stack.pop()
stack.append(apply_operator(a, b, token))
else:
stack.append(parse_number(token))
return stack[0]套路三：辅助栈设计
用于需要 O(1) 访问某个聚合值（最小值、最大值等）的场景：
class DesignStack:
def __init__(self):
self.stack = []
self.aux_stack = [] # 追踪最小/最大等
def push(self, val):
self.stack.append(val)
if should_update_aux(val, self.aux_stack):
self.aux_stack.append(val)
def pop(self):
val = self.stack.pop()
if self.aux_stack and val == self.aux_stack[-1]:
self.aux_stack.pop()
return val复杂度分析
| 题目 | 时间 | 空间 |
|---|---|---|
| 有效括号 | O(n) | O(n) |
| 逆波兰表达式求值 | O(n) | O(n) |
| 最小栈（所有操作） | O(1) | O(n) |
| 用队列实现栈 | O(n) push，其他 O(1) | O(n) |
| 用栈实现队列 | 均摊 O(1) | O(n) |
面试技巧
常见错误
- 忘记检查空栈：
pop()或peek()前要检查 - 操作数顺序错误：逆波兰表达式中，先弹出 b 再弹出 a，计算
a op b - 没处理边界情况：空输入、单个元素
- 整数除法截断问题：Python 的
//向负无穷取整；需要向零截断时用int(a/b)
如何清晰表达思路
- 明确问题：“我需要按后进先出的顺序匹配括号”
- 解释为什么用栈：“栈的 LIFO 特性天然适合处理……”
- 用例子演示：用小输入逐步展示
- 讨论边界情况：空输入、全是同类型、不匹配
面试官可能的追问
- 最小栈：“如果需要最大值而不是最小值呢？” → 同样的方法
- 有效括号：“如果有其他字符怎么办？” → 跳过非括号字符
- 逆波兰表达式：“如何处理带括号的中缀表达式？” → 调度场算法
- 栈队列转换：“能用一个队列/栈实现吗？” → 可以，但有不同的权衡
总结
栈问题的关键要点：
- LIFO 很强大 - 非常适合匹配、回溯和逆序处理
- 辅助栈 可以实现看似不可能的 O(1) 操作
- 双栈技巧 可以在 LIFO 和 FIFO 之间转换
- 访问栈顶前务必检查空栈
掌握这些基础，你就能应对面试中的任何栈问题！