第三世界的妖孽先说一句题外话。“优选算法的后进之道”这个标题，我第一眼看到就想笑——太形象了。“后进”既是“后进生”的“后进”，指栈这个东西在数据结构里看着简单，容易被轻视；又是“后进先出”的“后进”，恰好点出了栈最核心的 LIFO（Last In First Out）特性。做算法题多了你会发现，栈就像是一个低调的老实人，平时不声不响，但一到括号匹配、表达式求值、单调栈、DFS 这些场景，它是真能扛事。
这篇博文我不打算罗列一堆题目，而是想用我刷题和带人过程中总结出来的思路，把“栈到底在解决什么问题”“什么时候该想到栈”“用栈有哪些坑”讲透。无论你是刚开始刷题的新手，还是准备面试想系统过一遍栈的老手，这篇文章应该都能让你对栈有个更立体的认识。内容偏实战，所有代码我默认用 Python 写，思路是通用的，换 Java、C++ 也完全没问题。
1. 栈不是什么“高级”东西？先搞懂 LIFO 的真正价值
很多人觉得栈太简单了，不就是 push 和 pop 吗，考试背过就完了。但你要是真信了这句话，后面做单调栈、表达式求值的时候就会很痛苦。因为栈的妙处压根不在那几个操作上，而在“后进先出”这个顺序规则本身。
1.1 从生活场景理解栈的本质
想象一下往一个窄口瓶子里放球：你放进去的红球在最底下，蓝球在中间，黄球在最上面。想拿出红球，必须先把黄球、蓝球依次倒出来。这个“最后放进去的，最先拿出来”的过程，就是栈。
计算机里的栈就是这块翻版：数据项只能从一端（栈顶）进出，另一端（栈底）是封死的。基于这个限制，栈天然支持三种操作：
- push：把一个元素压到栈顶。
- pop：把栈顶元素弹出来。
- peek / top：只看栈顶元素，不弹出。
这三个操作的时间复杂度都是 O(1)，所以栈在算法里几乎总是作为高效辅助结构出现，不会成为性能瓶颈。
1.2 栈的核心思维模式：延迟匹配
那栈到底解决什么问题？我自己的总结是四个字：延迟匹配。
什么情况下你需要“延迟匹配”？就是当你读到某个信息时，它对应的“另一半”还没出现，你得先把当前信息暂存起来，等将来遇到配对信息再一起处理。典型例子：
- 括号匹配：读到左括号时，你不知道它和哪个右括号配对，只能先压栈存着。
- 函数调用：调用一个函数时，要记住“调用完之后回到哪一行继续执行”，这个返回地址只能压栈存着。
- 撤销操作：编辑器的 Ctrl+Z，要把操作历史压栈，撤销时从最近的操作开始回退。
这类“先发生的事情，后处理”的结构，用队列做不到，用数组自己管理又太麻烦。栈把“存起来”这个动作和“取出来”这个动作的顺序规则固化下来了，你用的时候只需要关心业务逻辑，不用自己维护索引。
所以以后做题，只要发现题目里有“配对”“嵌套”“最近的”“回退”这种关键词，第一反应就应该是：这是不是能栈解决。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 单调栈：解决“下一个更大元素”的标准姿势
如果说基础栈是入门，那单调栈就是栈这个专题里真正拉开差距的地方。面试里高频出现的“每日温度”“接雨水”“柱状图中最大的矩形”“下一个更大元素”，全是单调栈的天下。
2.1 单调栈到底是怎么“单调”的
单调栈，从名字就能看出来：栈内的元素是单调递增或单调递减的。但这里我踩过最大的坑是——你维护的不是栈内元素值单调，而是元素之间的某种比较关系单调。这句话别笑，真搞懂了，单调栈就算掌握了。
用最经典的场景来推导：给定一个数组，找到每个元素右边第一个比它大的元素（Next Greater Element）。暴力做法是双重循环，时间复杂度 O(n²)。单调栈做法是：
维护一个栈，栈内元素从栈底到栈顶是严格递减的（注意是值递减）。从左到右遍历数组：
- 当前元素 x 入栈之前，先看栈顶元素。如果栈顶元素比 x 小，说明 x 就是栈顶元素右边第一个比它大的元素，于是弹出栈顶记录答案。
- 重复这个过程，直到栈为空，或者栈顶元素大于等于 x。
- 把 x 压入栈。
因为所有元素最多入栈一次、出栈一次，整体时间复杂度 O(n)。
2.2 用“每日温度”实战推演一遍
力扣 739 题“每日温度”是这样的：给一个数组 temperatures，返回一个数组 answer，answer[i] 表示第 i 天之后需要等几天才能等到一个更高的温度；如果之后都不存在更高的温度，则 answer[i] = 0。
这个题就是标准的下一个更大元素问题，只是为了求“距离”，所以栈里压的应该是下标而不是值。我建议你拿到这类题先写伪代码：
text复制for i in range(n):
while stack 非空 and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
你看，代码就三行核心逻辑。我当初死活写不好这个题，是因为总想把当前元素和栈顶比，比完就入栈，但不知道什么时候出栈。后来想明白一个原则：出栈的时机，就是出栈元素答案确定的时机。当前元素 i 出现时，它有能力“终结”栈中所有比自己小的元素的等待，因为它们右边的第一个更大元素已经找到了。
这个模式可以套到很多题上。核心要义就一句话：当新元素能打破栈的单调性时，就出栈结算，直到恢复单调。
提示：严格递减 vs 非递增，差在有重复元素时“大于”还是“大于等于”的问题。如果题目要求“严格大于”，那么等于不能出栈；如果要求“大于等于”，等于也要出栈。做接雨水这类题时，这个细节直接决定答案对不对。
2.3 单调栈的完整代码模板
我把自己常用的单调栈模板贴出来，几乎可以直接改着用：
python复制def monotonic_stack(nums):
n = len(nums)
res = [-1] * n # 默认找不到更大元素
stack = []
for i in range(n):
# 如果栈不为空，且当前元素大于栈顶元素（说明栈顶的“下一更大元素”找到了）
while stack and nums[stack[-1]] < nums[i]:
j = stack.pop()
res[j] = nums[i] # 或记录 i - j 等距离信息
stack.append(i)
return res
这模板适用于“下一个更大元素”类。如果题目问“左边第一个比当前元素小的元素”，就把数组倒着遍历，或者从右往左扫；如果问“左边第一个更大的”，就调整比较符号和遍历方向。
单调栈题型的变体很多，但我归纳下来无非三类场景：
- 求右边第一个更大/更小元素：从左往右遍历，遇到更大的就弹栈。
- 求左边第一个更大/更小元素：从右往左遍历，或者从左往右时记录栈内元素。
- 求最大矩形面积/接雨水：利用单调栈维护“柱子”之间的边界关系。
这三种场景覆盖了单调栈 80% 以上的题。遇到新的题，先想它属于哪一类，再套模板，基本能写出框架。
3. 辅助栈：让“两个数据结构互相成就”的巧妙组合
做栈相关的题，你会发现一个很常见的套路：题目摆明了让你用栈，但单独一个栈解决不了问题，于是就需要“辅助栈”——典型的就是最小栈和用栈实现队列。这两个题看着基础，实际里面藏着很多值得展开的细节。
3.1 最小栈：O(1) 查询最小值的空间换时间
力扣 155 题：设计一个栈，支持 push、pop、top、getMin 四个操作，要求 getMin 的时间复杂度是 O(1)。
一个朴素但很常见的错误想法是：用一个变量记录当前最小值。但问题很明显——如果把这个最小值 pop 出去了，你该怎么知道下一个最小值是谁？答案是我们需要一个能记录“历史最小值”的结构，于是很自然地引入辅助栈。
老思路是：主栈正常存数据，辅助栈的栈顶永远存“当前栈内所有元素的最小值”。每次 push x 时：
- 主栈 push x。
- 辅助栈 push min(x, 辅助栈当前栈顶)。
这样辅助栈的栈顶就是当前栈的最小值。pop 时主栈和辅助栈一起 pop，由于辅助栈每一步都记录了当时的“当下最小值”，所以即使最小值被弹出，辅助栈里留下的栈顶依然是剩余元素的最小值。
这个题的精髓在于：你不需要在辅助栈里存所有数据，只需要存一个和主栈同步的“最小前缀序列”。也就是说，辅助栈的大小和主栈一样，但每个位置存的是“从栈底到当前位置的最小值”。
3.2 用两个栈实现队列：倒腾的时机是关键
力扣 232 题：用两个栈实现一个队列。这题我见过无数人写出了能跑的代码，但讲解不出来“为什么这样倒腾是对的”，面一深就露怯。
设计要点：
- 一个栈（inStack）负责入队。
- 一个栈（outStack）负责出队。
- 入队：直接 push 到 inStack。
- 出队：如果 outStack 不为空，直接 pop outStack；如果 outStack 为空，先把 inStack 的所有元素逐个 pop 并 push 到 outStack，然后再从 outStack pop。
为什么这样是对的？因为栈是后进先出，把 inStack 的元素全部倒入 outStack 后，元素顺序就反过来了——变成了先进先出。这个过程相当于把数据“翻转”了一下。
这里有个细节很容易出错：倒入操作只在 outStack 为空的时候做。如果 outStack 还有剩余元素，就不能倒，否则新倒进来的元素会压在旧元素上面，打乱队列顺序。
我个人的理解方式是：把 outStack 想象成一个缓冲队列的“出口通道”，只有通道空了，才允许从仓库（inStack）调货进来。这也解释了为什么这题时间复杂度摊还下来是 O(1)——每个元素最多进 inStack 一次、倒一次、出 outStack 一次，总共三次操作，分摊成本是常数。
这两个题看着简单，但它们的意义在于：你学会了用一个结构“辅助”另一个结构。后面很多更复杂的栈应用题，比如四则运算表达式求值里的操作数栈和运算符栈、浏览器前退后进的双栈管理，本质上都是这个思想的延伸。
4. 括号匹配与表达式求值：最古典的栈应用场景
学栈的入门题几乎都是括号匹配，因为它的逻辑简单到了极点：读到左括号就压栈，读到右括号就弹出栈顶检查是否匹配。但就是这个看似简单的题，可以往深里挖出很多东西，比如表达式求值、HTML 标签闭合校验，甚至编译器里的语法检查。
4.1 多类型括号匹配的注意事项
力扣 20 题“有效的括号”要求处理 ()[]{} 三种括号。代码框架就那样，但有几个细节值得抠：
第一，栈为空时遇到右括号，直接返回 false。这个边界条件新手最容易漏，一旦漏了，直接 panic 或者越界。
第二，用字典做括号配对映射，比写 if-else 漂亮得多，也省得漏掉某种情况：
python复制def is_valid(s: str) -> bool:
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return not stack
第三，最后要检查栈是否为空。如果只用栈是否为空来判断循环结束，那么“(())”这种字符串全匹配后栈正好空，但“((()”这种多了一个左括号的字符串，循环结束后栈不为空，必须 catch 到。
这个题的价值在于让你理解“栈顶元素代表最近未匹配的左括号”——这个概念在深度优先搜索里还会反复出现。只要读到一个右括号，就必须和最近的那个左括号配对，这就是“嵌套结构”的天然匹配，而栈正是处理嵌套结构的最佳选择。
4.2 表达式求值：从“逆波兰”到双栈求值
如果说括号匹配是栈的入门，那表达式求值就是把栈用在“程序语言解析”这个场景里的经典范例。力扣 150 题“逆波兰表达式求值”是简化版，但完整的表达式求值（带加减乘除、括号、多位数）才是真正的考验。
版本一：后缀表达式直接求值
逆波兰式（后缀表达式）的好处是运算符跟在数字后面，不需要括号也知道运算顺序。求值过程完全线性：
python复制def evalRPN(tokens):
stack = []
for token in tokens:
if token in '+-*/':
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[-1]
注意这里有个精度问题：Python 里 a / b 是浮点除法，但负数除法结果会向下取整，不是整数除法，所以要用 int(a / b) 这个写法，它相当于“向零取整”，更符合大多数题目的预期。换成 C++/Java 的时候，直接整数除法就行。
版本二：中缀表达式转后缀
实际面试很少直接给你后缀表达式，更多是给你 "3+2*2" 这种带优先级的普通写法。那我们需要先把中缀表达式转成后缀。转换规则：
- 遇到数字：直接输出（存在结果列表里）。
- 遇到左括号：压栈。
- 遇到运算符：如果栈顶运算符优先级大于等于当前运算符，则弹出栈顶并输出，重复直到栈顶优先级更低，然后把当前运算符压栈。
- 遇到右括号：弹出运算符直到左括号，并把左括号弹出。
转成后缀之后，再用上面的求值流程跑一遍。整个过程是两遍扫描，每遍 O(n)。想通了这套流程，你再看“用栈实现计算器”这类题，就不会觉得无从下手了。
注意：减号和除号的顺序不能反。后缀表达式里
a b -是a - b，不是b - a。这里非常容易错，我建议你在写求值函数时多测几个负数、连续运算的用例。
5. 栈与深度优先搜索：递归的另一种写法
栈专题里有一个很容易被忽略、但面试很喜欢问的考点：递归的本质就是栈。你写的那个递归函数，系统帮你维护了一层又一层的调用栈，每层调用保存着局部变量和返回地址。当你把递归改成迭代时，往往就需要显式地维护一个栈。
5.1 为什么递归能用栈改成迭代
递归函数的执行过程，本质上是磁盘上那句“调用自身”变成了在栈上压入一个新的执行帧。等到最深处的基本情况返回，栈帧逐个弹出，一层层往回计算结果。
所以你只要模拟这个过程：把每次递归调用看成一次压栈，把返回结果看成一次出栈。用什么保存“调用参数”和“返回值”？用栈。
最常见的例子是二叉树的前序遍历。递归版本写起来很顺：
python复制def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
但你要改成非递归写法，就得自己拿栈模拟调用过程：
python复制def preorder_iter(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
注意左右孩子的入栈顺序：因为栈是后进先出，想先访问左子树，就得先把右孩子压进去，再把左孩子压进去。这个“压栈顺序 = 访问顺序的逆序”就是递归转迭代的核心。
5.2 中序遍历和后序遍历的迭代技巧
中序遍历的非递归写法稍微绕一点。因为中序遍历的顺序是“左根右”，你要先一路往左走到最深处，把路径上的节点都压栈，直到左孩子为空，然后弹出节点访问，再转向其右子树：
python复制def inorder_iter(root):
res = []
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
node = stack.pop()
res.append(node.val)
cur = node.right
return res
我觉得这个模板值得背下来，因为它其实对应了“沿着左链压栈，弹出即访问，然后去右子树重复”这个循环结构。你甚至可以拿它去理解 Morris 遍历——Morris 遍历本质上就是省掉了栈，用线索二叉树记录回溯路径，但思想是一样的。
后序遍历的非递归写法最折腾。一个常用技巧是：前序遍历是“根左右”，后序遍历是“左右根”。我们可以先做一个“根右左”的遍历，然后把结果倒过来，就得到“左右根”。代码实现可以这样玩：前序遍历模板里先压左再压右，改成先压右再压左，得到一个“根右左”序列，最后 reverse。
这个技巧说白了就是利用栈的对称性，你如果对“顺序反转”敏感，会发现这类题目都是在栈的特性上做文章。
6. 栈专题常见坑位与自查清单
最后这部分是硬核避坑指南。我见过太多人在栈相关的题上栽跟头，原因都不是不会思路，而是细节没管住。这里整理一下高频 bug 和一套自查流程。
6.1 高频 bug 盘点
空栈弹出
最常见。代码写的没问题，就是忘了检查栈空就 pop。尤其是括号匹配和单调栈里，先弹栈再判断的写法等于埋炸弹。
单调栈比较的方向不对
单调栈单调递增还是递减，取决于你要找“更大元素”还是“更小元素”。我建议拿到题先明确：我要找的是右边第一个更大的，那栈里存的应该是还没找到答案的下标，所以新元素比栈顶大时，栈顶的答案就能确定。反过来找更小的，比较符号就反过来。
这个我总结成一句话：你维护的不是“值的单调性”，而是“候选答案的淘汰规则”。当前元素能淘汰栈顶，说明栈顶的候选身份失效了。谁淘汰谁，就是比较符号。
重复元素的处理
遇到数组里有相等元素，“大于等于”和“严格大于”是两回事。如果题目要求找到严格大于当前元素的下一个元素，那么相等时不弹栈；如果允许大于等于，那相等也弹。建议在写单调栈之前，先用手画两个用例，把边界明确下来。
栈底剩余元素没结算
单调栈跑完之后，栈里可能还留着一些下标，它们右边没有符合条件的元素。如果你初始化答案数组时已经设了默认值，那这部分可以不管；但如果默认值需要根据题目调整（比如距离类题目的 0），就要在循环结束后再扫描一次栈，给剩余元素赋值。
6.2 拿到栈题目的一分钟自查流程
我不建议拿到题立刻写代码，先花一分钟过一遍下面几条，能省很多调试时间：
- 题目是不是在问“配对”“嵌套”“最近的”“最大矩形”这类问题？如果是，逃不开栈。
- 栈里存什么？存值还是存下标？差距题（每日温度）存下标，元素题（下一个更大元素）又得看后续需不需要下标。
- 单调栈的比较规则是什么？大于还是大于等于？决定弹栈条件。
- 循环结束后栈里还剩什么？需要额外处理吗？
- 边界条件是什么？空栈、单元素、全相等、序列倒序——测试用例里都要过一遍。
这套流程看着简单，但如果你每次写栈题都走一遍，会发现很多错误在执行之前就被消灭了。
7. 栈专题的后续扩展思路
栈本身确实简单，但它串起来的知识点可不少。如果你刷完上面这些题还有余力，可以往这几个方向延伸。
一个是“栈 + 哈希表”的组合，典型的是“下一个更大元素 II”那种循环数组问题，需要把数组复制一份再跑单调栈，或者用取模假装复制。这类题训练你对“循环结构”的建模能力。
另一个是“栈 + 动态规划”，比如“接雨水”这道题，既可以用单调栈做，也可以用双指针或动态规划做。我建议你至少用两种方法解一遍，这比刷十道新题更能加深理解——因为你会发现不同解法之间其实是同一套物理直觉的三种表达。
还有一个方向是“栈在系统设计里的影子”，比如浏览器的前进后退、编辑器的撤销重做、函数调用栈溢出分析。把这些真实场景和算法题串起来，你会觉得栈不再是一个冷冰冰的数据结构，而是一种看世界的框架。
我以前带过一位同学，他刷完栈专题后跟我说了一句印象很深的话：“栈就像是一个只能从一端进出的盒子，但这个限制反而让你不得不思考什么才是真正的关键信息。” 这句话我很赞同。数据结构的价值不在于它有多复杂，而在于它的约束条件如何帮助你理清问题模型。栈的 LIFO，就是那种能把“匹配”和“回溯”简化成入栈出栈的约束。
最后分享一个小经验：如果你在做栈相关的题时卡住了，别硬看题解，先拿一张纸，把数组元素一个个手动画栈的入栈出栈过程。画着画着，很多“为什么这里要弹出”“为什么要存下标”的疑问都会自己解开。栈题目的难点从来不是代码，而是你是否在脑子里清晰地看到了“栈顶元素此刻代表谁”。想通了这一点，栈专题就算真正过关了。