数据结构栈专题复盘：从后进先出到单调栈的算法实战指南

如果要在数据结构里挑一个“接口最简单、坑却最多”的代表，我会毫不犹豫选栈。它只有入栈、出栈、查看栈顶、判空这几件事，五分钟就能背完，可一旦进入算法实战——括号匹配、表达式求值、单调栈、用栈模拟递归——你会发现“后进先出”这四个字背后藏着一整套思维。这篇文章是优选算法栈专题的完整复盘，我会把栈这个结构的底层逻辑、经典题型、通用套路，以及我自己踩过的坑和排查经验一次说清楚。适合准备算法面试、正在刷题遇到栈就发怵、或者刚学完数据结构还想再深挖一层的读者。

“后进之道”这个标题有双关的意思。栈最核心的性质就是后进先出，后进来的元素最先出去，这是栈的本体；而对于很多自认为基础薄、起步晚的算法学习者来说，栈专题反而是最容易“后来居上”的板块，因为它的知识点高度收敛，题型高度套路化，只要把几个经典模型吃透，进步会非常快。我自己就是在栈专题上完成了从看到题没思路，到二十分钟内写完核心代码的转变，所以想把这一套东西原原本本分享出来。

1. 为什么说栈是“后进之道”

1.1 后进先出不是抽象概念，是生活常识

很多人第一次学栈，会被“stack”这个英文词吓到，觉得它是一个冷冰冰的抽象数据结构。其实栈的后进先出每天都在发生。你往背包里叠衣服，先放进去的压在底下，后放进去的在上层，要拿最底下的那件，必须先把上层的一件件拿出来，这就是一个严格的栈模型。自助餐厅里一摞餐盘，服务员拿走的一定是刚洗好放在最上面的那个，下面的盘子只有等上面的被取走才露出来。浏览器里的“后退”按钮，也是把当前页面压进一个栈，后退时从栈顶取出上一个页面。

这些例子的共性是“最近的状态优先被处理”。栈不关心更早的信息是否重要，它只允许你临时保存一批状态，并且强制只能从最近保存的那个状态继续。这种约束乍看有局限，但在算法里恰恰是优势：很多问题要处理的就是嵌套结构、历史恢复、延迟结算，用数组或队列反而绕路。理解了这一点，再看题目里为什么该用栈，就不会停留在“因为别人用了栈”的层面。

1.2 栈的底层逻辑：简单却不简陋

从实现角度，栈可以看作一个受限的线性表，它只需要两个基本操作：在尾部加入元素，以及从尾部移除元素。因为操作只发生在尾部，用数组实现是天然选择：预分配一块连续内存，维护一个栈顶指针，push 时写入并移动指针，pop 时指针回退。所有操作的时间复杂度都是 O(1)。链表也能实现同样复杂度，但数组模拟在内存连续性和缓存友好性上明显更优，这也是我在工程和刷题里一律用数组模拟栈的原因。

用 Python 写栈甚至不用自己造轮子，直接拿 list 当数组用就行。append 对应入栈，pop 对应出栈，stack[-1] 对应栈顶，四行代码就是完整骨架：

python复制stack = []
stack.append(1)   # 入栈
stack.append(2)   # 入栈
top = stack[-1]   # 查看栈顶
stack.pop()       # 出栈

C++ 里我同样推荐用 vector 代替 std::stack，原因是 vector 可以随时遍历、可以读到栈中任意位置的元素，而 std::stack 默认只给你栈顶的访问权限，调试起来很别扭。Java 则优先用 ArrayDeque，而不是老旧的 Stack 类，Stack 继承了 Vector 的同步开销，在算法竞赛里属于不必要的损耗。语言差异放在后面细说，这里先记住结论：栈的实现非常简单，真正决定水平的是你选择怎么用它。

1.3 栈带来的三个思维转变

为什么说栈专题能让人“后进”？因为它会逼着你完成三个思维转变。

第一，从只关注“当前状态”，变成关注“历史状态”。普通数组遍历时，你只关心当前下标和全局变量；栈却要求你把之前遇到但还没处理完的状态保存起来，等到合适时机再弹出。比如括号嵌套，必须记住每个未匹配左括号的位置，这天然就是历史状态管理。

第二，从递归思维变成迭代思维。系统调用栈本身就是栈，递归函数能做的事情，理论上显式栈都能做。很多不敢碰递归转迭代的人，只是没有把“函数调用栈”具象化。

第三，从盲目尝试变成“延迟结算”。栈特别适合处理需要等一个关键信息出现后，再回头答复之前所有未决元素的问题。单调栈就是这类思想的典型，后面会集中展开。

这三个转变不是背八股背出来的，是通过具体题目练出来的。这也是为什么我建议栈专题不要只看不写，哪怕简单的题目，也要在编辑器里真实跑一遍再往下走。

2. 栈的四大经典应用场景

2.1 括号匹配：栈的“入门第一课”

括号匹配是栈最经典的场景，也是几乎所有教材讲栈时都会用到的例子。判断一个字符串里的括号是否合法，规则只有三条：左括号必须按顺序入栈；右括号出现时必须与栈顶左括号类型匹配；字符串结束时栈必须为空。匹配规则用代码表达很直接：准备一个从右括号到左括号的映射表，遍历字符串时遇到左括号就入栈，遇到右括号就检查栈顶是否等于映射值，下面这个版本我在面试里写过很多次，顺手就能写出来：

python复制def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in mapping:
            if not stack or stack[-1] != mapping[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

这里最容易错的是两点：一是右括号来临时忘记检查栈空，直接访问 stack[-1] 导致越界；二是只检查数量没检查类型，让 (] 这种输入溜过去。写这道题时如果把“栈顶必须匹配当前右括号”这个约束想清楚，后续很多题都会顺很多。

括号匹配不只存在于题目里，编译器语法分析、IDE 代码高亮、表达式校验，底层都有类似逻辑。理解了括号匹配，再看字符串解码、标签闭合校验，会发现它们都是同一个模型，只是外层多包了几层壳。

2.2 递归转迭代：用显式栈接管系统栈

递归的本质是系统帮我们维护了一个函数调用栈，每一次递归调用都把当前参数、局部变量、返回地址压栈，返回时再弹出。所以任何递归算法理论上都可以改成显式栈的迭代算法。这么做不是为了炫技，而是为了防止递归层数过深导致栈溢出，以及在某些需要严格控制调用顺序的场景下掌握主动。

最常见的例子是二叉树的深度优先遍历。递归版前序遍历大家都知道，核心就三行：先访问当前节点，再递归左子树，最后递归右子树。改成显式栈时，就要注意入栈顺序。因为栈是后进先出，为了让左子树先被访问，必须先把右子树压进栈，再把左子树压进栈。很多新手第一次写迭代遍历，顺手把左子树先 push 了，结果访问顺序完全反掉，浪费时间排查。

python复制def preorderIterative(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

这个例子很小，但它背后是一条重要经验：显式栈模拟递归时，入栈顺序与递归执行顺序恰好相反。遇到“先后处理 A 再处理 B”的递归逻辑，迭代时就要先压入后处理的 B，再压入先处理的 A。这个规律在树、图、回溯算法里会反复出现。

2.3 浏览器的前进后退，是双栈的教科书

很多人不知道，浏览器历史记录就是栈的经典工程应用。试想你要支持“后退”和“前进”两个方向，一个栈不够，得用两个。当前页面是基准，后退栈保存之前的页面序列，前进栈保存你后退时经过的页面。当你点“后退”，当前页面从后退栈弹出，然后压入前进栈；点“前进”时，从前进栈弹出，压回后退栈；当你在当前页面输入新地址，前进栈要整体清空，因为你已经走出了原来的历史路线。

这套逻辑用两个栈实现，代码不超过二十行。编辑器的撤销与重做、图片处理软件的步骤回退，也都是同一个原理。刷题遇到“用两个栈实现队列”这类题目时，不要觉得它只是脑筋急转弯，它背后就是这些真实场景的抽象版本。理解了工程背景，设计题会有一种“原来如此”的通透感。

2.4 单调栈：栈在算法实战里真正的王牌

如果说前三类应用是栈的常规操作，那单调栈就是拉开水平差距的地方。单调栈是指栈内元素从栈底到栈顶保持单调递增或递减，它不只是为了存状态，而是为了在线性时间内解决一类“找左右最近更大或更小元素”的问题。

一个形象的理解方式是排队看人。你站在队伍里，想知道右边第一个比你高的人在哪个位置。如果你够高，左边那些比你矮的人根本不会阻碍你的视线，他们会在看到一个更高的人时被清出队伍。单调栈做的就是这件事：维护一个从栈底到栈顶单调递减的序列，每次新元素入栈时，把栈内所有比它矮的元素弹出去。弹出去的那一刻，就是这些元素找到答案的时刻。

用一句口诀概括：“谁破坏了单调性，谁就是答案的触发者。”后面在题型部分，我会把单调栈的套路彻底展开，并用一道经典题完整走一遍。

3. 栈专题的高频题型与解题套路

3.1 括号类题目的两个层次

括号题看似简单，但如果只停留在“验证字符串是否合法”，那只是第一层。第二层是“最长有效括号”，给定一个只包含左括号和右括号的字符串，找出最长的有效括号子串长度。这类题用栈可以很巧妙地只存索引，而不是存括号本身：

python复制def longestValidParentheses(s: str) -> int:
    stack = [-1]
    ans = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                ans = max(ans, i - stack[-1])
    return ans

核心思想是：栈底始终保存一个“未被匹配的右括号的索引”，作为当前合法段的起点减一。遇到右括号时弹栈，如果栈空说明这个右括号没有匹配项，把它当作新起点压入；如果栈不空，当前索引减去栈顶索引，就是这一段有效括号的长度。

这里的易错点在于初始化栈为 [-1]。没有这个 -1，第一对有效括号的长度就永远少算 1。很多人直接背这个初始化，但不知道为什么，一旦题目变形就懵。理解了“栈底是最后一个未匹配位置”后，才算是真正掌握。

3.2 单调栈的套路化模板

我试着把单调栈总结成一套可操作的模板，下面这个版本专门用来求每个元素右侧第一个比它大的元素下标，刷题时可以直接套，更重要的是理解每一步在做什么：

python复制def nextGreater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = i
        stack.append(i)
    return result

注意，栈内保存的是下标，比较时用下标去取 nums 里的值。每当当前元素 nums[i] 大于栈顶元素时，说明栈顶元素终于遇到了它的“右侧第一大”，于是弹栈并记录答案。当前元素入栈，等待自己右侧的更大元素。整个过程每个下标最多入栈一次、出栈一次，所以是 O(n)。

如果题目要求的是“右侧第一个更小元素”，只需要把比较符号换成大于号；如果是“左侧第一个更大”，可以倒序遍历数组，套路完全对称。我建议第一次学单调栈时不要背代码，而是拿一个数组手写一次弹栈、入栈全过程，理解了“弹出时结算”之后，所有变种都不再可怕。

3.3 设计题：最小栈和双栈队列

栈专题里有一类设计题，不考复杂算法，纯粹考对栈结构的掌控。最典型的是最小栈：支持入栈、出栈、取栈顶、取最小值，要求所有操作都是 O(1)。一个很自然的方案是用辅助栈同步记录当前最小值，每次入栈时把当前最小值也压入辅助栈，弹栈时同步弹出。这里的关键是辅助栈顶永远保存的是当前栈内的最小值：

python复制class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        x = self.stack.pop()
        if x == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

注意辅助栈的同步条件：入栈时只有 x 小于等于当前最小值才需要入辅助栈；出栈时，如果弹出元素等于辅助栈顶，辅助栈也要弹出。很多人写这题时忘记处理相等值，导致最小值提前出栈，这就是典型踩坑点。

双栈实现队列则是另一道经典设计题。一个栈专门负责入队，另一个栈专门负责出队。出队时，如果出队栈为空，就把入队栈的所有元素倒过去。因为在入队栈中，最早进入的元素在栈底，倒入出队栈后它变成栈顶，正好可以最先弹出。这个过程摊还下来每个元素只会被移动两次，均摊 O(1)，性能非常好。

3.4 表达式求值：操作符优先级与两个栈

表达式求值是栈的另一大考区。给定一个中缀表达式，比如 3 + 4 * 2 - 1，可以用两个栈分别存操作数和操作符。扫描时遇到数字压入操作数栈，遇到操作符则先比较优先级：如果当前操作符的优先级不高于操作符栈顶，就把栈顶操作符弹出并计算结果，再把结果压回操作数栈；否则当前操作符直接入栈。遇到左括号直接入栈，遇到右括号则一直弹出计算直到左括号。最后清空操作符栈。

这里最容易出错的是优先级判断和括号处理。我建议先掌握“中缀转后缀表达式”再写计算器。后缀表达式的计算只需要一个操作数栈，扫描后缀表达式，遇到数字入栈，遇到操作符从栈顶取两个数字计算再入栈。中缀转后缀时，数字直接输出，操作符则遵循“当前操作符优先级低于栈顶时，栈顶出栈”的规则。理解了这两步，任何带括号、带负号的计算器题都能稳定解出。

4. 实操现场：单调栈解“柱状图中最大的矩形”

4.1 题目先读清楚

这道题是栈专题里我非常推荐反复写三遍以上的题：给定一个非负整数数组 heights，每个数代表一根柱子的高度，所有柱子宽度都是 1，求这些柱子能勾勒出的最大矩形面积。我最早做这题时，第一反应是枚举左右边界，维护区间最小高度，复杂度 O(n^2)，数据一大就超时。它真正考验的，是你能不能把“每个柱子作为高度时的最大宽度”这件事想透。

4.2 核心思路：确定每根柱子能撑起多宽

换个视角看答案。任何最终答案矩形，它的高度一定等于某一个柱子的高度。因为如果矩形高度低于所有包含柱子的高度，那完全可以向上增加一点，直到顶到某根更矮的柱子。于是问题转化为：以第 i 根柱子作为矩形高度，向左和向右找到第一根比它矮的柱子，矩形的宽度就是左右两个矮柱子之间的区间长度，面积等于 heights[i] * (right - left - 1)。

暴力情况下，对每个柱子都向左向右扩展，最坏仍然是 O(n^2)。如何一次遍历同时算出左右边界？这正是单调栈擅长的事情。我维护一个从栈底到栈顶高度递增的栈，从左到右扫描。当新柱子高度小于栈顶柱子高度时，栈顶柱子右侧第一根比它矮的柱子就是当前新柱子，而左侧第一根比它矮的柱子，就是弹出它之后的新栈顶。于是左右边界都齐了，可以立刻结算面积。

4.3 哨兵技巧：免去判断栈空

直接实现这道题需要处理两个边界：扫描结束后栈里还有剩余柱子，以及某根柱子左边根本没有更矮柱子。处理办法是在数组首尾各加一个高度为 0 的哨兵，经典写法如下：

python复制def largestRectangleArea(heights):
    heights = [0] + heights + [0]
    stack = []
    ans = 0
    for i in range(len(heights)):
        while stack and heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1
            ans = max(ans, h * w)
        stack.append(i)
    return ans

头部哨兵保证每个柱子左侧一定有一个高度更小的边界，尾部哨兵则强制把栈里所有剩余柱子全部弹出结算。有了这两个哨兵，while 循环里不太需要担心空栈，因为第一次循环会把索引 0 入栈，后面再遇到其他柱子，只要高度大于等于 0，就不会出现栈空后访问栈顶的尴尬。

4.4 用一个小例子完整走一遍

拿 heights = [2, 1, 5, 6, 2, 3] 演示。加哨兵后变成 [0, 2, 1, 5, 6, 2, 3, 0]。

索引 0 的哨兵入栈。索引 1 高度 2，比栈顶高，入栈。索引 2 高度 1，比栈顶高度 2 矮，弹出索引 1，此时栈顶是索引 0 的哨兵，宽度等于 2 - 0 - 1 = 1，结算面积 2 * 1 = 2；然后索引 2 入栈。

索引 3 高度 5、索引 4 高度 6 都直接入栈，因为它们都比栈顶高。索引 5 高度 2，比栈顶高度 6 矮，先弹出索引 4，宽度等于 5 - 3 - 1 = 1，面积 6；再弹出索引 3，宽度等于 5 - 2 - 1 = 2，面积 10；之后栈顶高度 1 小于 2，索引 5 入栈。

索引 6 高度 3，直接入栈。索引 7 是尾部哨兵高度 0，开始强制弹出：弹出索引 6，宽度等于 7 - 5 - 1 = 1，面积 3；弹出索引 5，宽度等于 7 - 2 - 1 = 4，面积 8；弹出索引 2，宽度等于 7 - 0 - 1 = 6，面积 6。所有弹出过程中最大值是 10，所以答案是 10。

你会注意到，每一根柱子被弹出时，结算的面积恰好都是“以它为高度，左右第一个更矮柱子为边界”的最大矩形。这就是单调栈“弹栈即结算”的直观体现。整个过程每个下标最多入栈一次、出栈一次，时间复杂度 O(n)，空间 O(n)。

4.5 等号到底用大于还是大于等于

很多人在写单调栈时会纠结 while 里到底用严格大于还是大于等于。我的建议是使用严格大于，也就是只有当前元素严格小于栈顶时才弹出。原因是遇到相等高度时，让新元素继续入栈，旧元素等到最后再统一结算，最左侧的那个相同高度柱子会计算出覆盖整个相等区间的最大面积，逻辑更清晰。

拿 heights = [2, 2] 来说，用严格大于时，第二个 2 不会立刻弹出第一个，而是入栈。尾部哨兵来临时，先弹出第二个 2，再弹出第一个 2。第一个 2 结算时宽度覆盖两根柱子，得到正确面积 4。如果用大于等于，虽然也能通过，但在理解上需要多绕一层。刷题阶段我强烈建议固定用严格大于，把注意力放在“弹栈触发条件”本身，而不是在两种写法之间反复切换。

5. 避坑实录与问题排查技巧

5.1 最隐蔽的坑：while 里忘记判栈空

新手写单调栈时最常见的报错是索引越界。比如求下一个更大元素，一上来就写 while nums[stack[-1]] < nums[i]，完全忘了栈可能为空。解决有两个方案：要么每处 while 都加 stack and 条件；要么像柱状图那样在数组前后加哨兵，从结构上避免空栈。

两个方案我都用过，刷题场景里哨兵更省心，但面试手写时，我会先写带 stack and 的版本，因为它和脑中逻辑一致，哨兵版本容易被面试官追问边界含义。无论用哪种，一定要先想清楚栈空的语义。

5.2 单调递增还是递减，别靠背

这是栈专题里问得最多的问题。我的判断方法很简单：先想清楚你需要在什么时候结算答案。比如“右侧第一个更大元素”，当前元素比栈顶大时，栈顶的答案出现了，此时弹出栈顶，因此栈内需要保持递减，当前元素破坏递减性才会触发弹出。

而“柱状图中最大矩形”需要找左右更矮的柱子，当前元素比栈顶矮时，栈顶的边界出现了，因此栈内保持递增。一句话：破坏单调性的那一刻，往往就是触发结算的时机。先决定“谁破坏、谁触发”，再决定单调方向，就不会记反。

5.3 栈里存索引还是存值

单调栈题里，栈里存的一定是下标，而不是值。因为结算答案时往往需要计算下标差，比如柱状图宽度、每日温度间隔天数。如果你只存高度，宽度算不出来；如果在弹栈时用 heights[stack[-1]] 去取值，就能同时拿到值和位置。

经常有同学把 stack.append(i) 写成 stack.append(nums[i])，最后拿不到索引又回来改，很浪费时间。建议一开始就建立条件反射：单调栈存索引，取数值时再去数组里取。

5.4 递归转迭代，顺序反了是大坑

模拟递归时，栈的入栈顺序和递归执行顺序相反。以二叉树前序遍历为例，递归顺序是先根、再左、再右，迭代就要先压右子树、再压左子树。不少人在写树的迭代遍历时，因为顺序反了，输出结果和递归版完全对不上。

其实有个保底技巧：如果递归版已经写好，可以直接照着递归的调用顺序反向入栈。递归里哪个分支最后执行，哪个分支就最先进栈。这个规律可以用在很多需要手动模拟栈的场景。

5.5 语言选型带来的真实差异

Python 刷题用 list 模拟栈最直接，append 和 pop 都是常数时间，不需要额外引入 deque。C++ 我更推荐 vector 而不是 std::stack，vector 的 push_back 和 pop_back 同样 O(1)，而且支持随机访问，调试时可以打印任意位置。Java 一定不要用 Stack 类，它继承了 Vector 的同步锁，性能差，官方也建议用 ArrayDeque 代替。

这些差异在小数据量下不明显，但在单调栈这类大循环里，容器实现的差别会直接影响常数。现场手写与其依赖封装，不如回归数组。

另外，如果遇到递归调用超过语言默认限制，第一反应不要是无限加大递归深度，因为递归本身有函数调用栈内存开销，更好的做法是把递归改成显式栈迭代。栈专题练的就是这个能力。

5.6 一份问题排查速查表

我把平时排查栈相关 bug 的路径整理成了一张速查表，照着看能少走很多弯路：

表格不是银弹，但对照排查能省不少时间。我每次写完一个栈相关题目，如果有 bug，都是沿着这张表的思路去定位，基本能在几分钟内找到问题。

6. 从“后进”到“进阶”：栈专题的训练建议

6.1 按题型分组刷，不要乱序刷

栈专题虽然题量不大，但乱序刷很容易卡在同一个思维盲区。我建议按括号匹配、栈与递归、单调栈、表达式求值、设计题五大类分组训练。每一组先做两到三道基础题，理解套路后再挑战变形题。

比如括号匹配可以从普通有效括号，升级到最长有效括号、字符串解码；单调栈可以从“右侧第一个更大”起步，再做每日温度、柱状图最大矩形、接雨水。分组的好处是你能在同一段时间内反复强化同一个模型，形成肌肉记忆。

6.2 一道题至少给出“暴力加优化”两种写法

我见过不少同学，最常见的习惯是上来就找最优解，跳过暴力思路。可栈专题尤其是单调栈，如果没有暴力解的对比，很难理解优化到底优化了什么。以每日温度为例，暴力就是对每个位置向右扫描，复杂度 O(n^2)；单调栈优化后变成 O(n)。

建议先把暴力写出来，跑一个随机大数组，看着它超时，再写单调栈版本，两个版本对比着学习。真到了面试时，面试官也更喜欢听你先讲暴力、再讲优化，这是完整思考过程的一部分。

6.3 建议动手实现一个简易栈

刷题之外，我还推荐用自己熟悉的语言实现一个固定容量的栈，包含扩容和缩容逻辑。这个练习不是为了造轮子，而是要理解数组模拟栈时索引移动的含义。当你亲手写出 append 和 pop 背后的逻辑，再看题目里的栈操作，就不会再觉得浮在半空。

实现完之后，你可以用自己的栈去跑一遍括号匹配，体感会完全不同。栈这个结构虽然简单，但动手实现一遍带来的理解深度，往往比刷十道简单题更有效。

我个人做栈专题最大的感受是：越简单的结构，越考验抽象能力。后进先出四个字，初看是限制，细看是特性，再往深看是一整套和“最近最相关”问题打交道的方式。把这个专题啃下来，受益的不只是几道题的解法，而是一种遇到嵌套、回溯、延迟计算场景时，本能想到用栈去建模的敏感性。如果你也在栈专题上挣扎，别急着追求题量，先把这几个套路吃透，状态会完全不一样。