学算法时，栈和队列这两个结构容易被低估。它们简单到用一句话就能讲完——一个后进先出，一个先进先出——可到了刷题实战的时候，翻车率却意外的高，其中有不少人虽然能背下API，却回答不上来“为什么广度优先搜索要配队列而不是栈”，也有人见到单调栈就套模板，却连该存下标还是存值都分不清。
这篇文章不打算重复教科书式的定义，而是从实战角度聊聊对栈和队列的理解：它们到底在模拟什么场景，哪些高频题背后是同一个套路，哪些坑是几乎每个人都要踩一遍的，以及如何安排一条务实的刷题路线。无论你刚接触算法，还是已经刷了不少题想查漏补缺，这篇应该都能给你一点参考。
1. 栈和队列到底在模拟什么：先别急着背API
1.1 栈的后进先出，其实每天都在用
有些数据结构离生活近到容易被忽略。编辑器的“撤销”、浏览器的“后退”，行为就是栈：后进来的操作最先被撤销，最近访问的页面最先被回退。函数调用也是栈，假设A调用B，B调用C，那么C返回后先回到B，再回到A，这背后就是一套系统调用栈。“爆栈”这个概念，其实就是深度递归时，系统维护的调用栈被压满了。
理解这个场景，再看栈相关的题会顺很多。括号匹配时，为什么遇到右括号要看“最近”那个未匹配的左括号，因为匹配顺序天然就是栈。树和图的深度优先搜索（DFS）通常用递归写，但递归本质是在隐式使用系统栈；改写为迭代时，一个显式的栈完全可以接替系统调用栈。栈并不是什么“高级技巧”，它就是程序运行的基本机制之一。
1.2 队列的先进先出，是最朴素的排队逻辑
队列对应的是“排队”。打印任务、消息队列、操作系统的任务调度，都是先来的先被处理。算法里最典型的队列应用是广度优先搜索（BFS）：从起点出发，先处理距离为1的点，再处理距离为2的点。这个顺序天然是先进先出，和队列完全匹配。如果换成栈，就会变成深度优先地一条路走到底。
面试里常有人被追问“BFS为什么用队列而不用栈”，回答卡壳并不是因为不懂定义，而是没把“先进先出”和“逐层扩散”对应起来。队列的价值不是“能存数据”，而是它恰到好处地维护了“先到先处理”这个顺序。
1.3 实现层面的选择：数组、链表还是deque
刷题时一般不需要手写完整的栈和队列，但理解实现有助于分析复杂度。栈用数组实现，关键在于维护一个top指针，入栈加一，出栈减一；链表实现则用头插头删。队列用数组实现时，出队后队头前移，前排空间就浪费了，因此常见做法是“循环队列”，用取模让rear绕回数组头部。判空判满的条件，我会在第5章专门展开。
C++里stack和queue的默认底层容器是deque，不需要自己操心扩容；Python刷题通常用list模拟栈，用collections.deque模拟队列。我的习惯是：笔试环境里能用现成容器就用现成容器，思路集中在解题逻辑上；只有题目明确要求“设计一个栈/队列”时，才需要从头实现。设计题考的是边界处理，和普通题不一样。
2. 单调栈：一类高频题，一个模板吃透
2.1 什么特征的题目，会暗示你上单调栈
单调栈是栈在算法题里出场率最高的应用典型。它专治一类问题：在数组中，找一个元素的“右边第一个比它大/小的元素”“左边最近的更大/更小元素”，以及由此衍生的“接雨水”“柱状图最大矩形”等。这些题的题干里通常有“下一个更大”“最近更大”“左右两侧第一个”这类词。
另一个很灵敏的信号是：暴力枚举区间是O(n^2)，看不出明显优化思路，但隐隐觉得“元素之间的相对顺序信息可以维护一下”。比如问“每一天要等几天才出现更高温度”，暴力是每个位置往后查，更聪明的做法是从右往左维护一个递减栈，每个元素右边第一个更大者的位置就出来了。
2.2 单调栈模板：从“下一个更大元素”开始
以“下一个更大元素”为例：给定数组nums，返回每个元素右边第一个比它大的值，不存在就填-1。单调栈实现的思路是，用栈存下标，栈底到栈顶对应的nums值保持递减。每来一个新元素，把所有比它小的栈顶元素弹出，因为对这些弹出元素来说，“右边第一个更大元素”就是当前这个新元素。
def next_greater(nums): n = len(nums) res = [-1] * n stack = [] # 存下标，栈底到栈顶对应值递减 for i in range(n): while stack and nums[stack[-1]] < nums[i]: res[stack.pop()] = nums[i] stack.append(i) return res这个模板里有几个细节值得思考。栈里存的是下标，不是值，因为很多题要返回索引距离，而且下标能唯一区分相同值的不同位置。while条件里是小于号，意味着弹出的条件是“遇到严格更大的值”；如果题目要求找“不小于”的最近元素，就改成小于等于。方向取决于题目问的是更大还是更小。模板并不难，难的是识别题目如何转化为这个结构。
2.3 从模板到真题：手推一遍再加一题实践
只看模板很难直接把“接雨水”这类题套进去。我建议拿到一道题，先在纸上画一个简单例子来推演。
以“柱状图最大矩形”为例：每个柱子能形成矩形的最大宽度，取决于它左右两边第一根更矮的柱子。这正好是单调栈能算的：某根柱子出栈时，栈中它下面的那个元素就是左侧第一根更矮者，逼它出栈的元素是右侧第一根更矮者。定好左右边界，矩形面积就出来了。这是单调栈经典应用。
“接雨水”也是同一套思想，不过方向稍有不同：从左到右用递减栈，遇到比栈顶高的柱子时，当前栈顶当作凹槽底部，弹出后的新栈顶作为左边界，当前元素作为右边界，然后结算这一段能接多少水。我建议拿[2,1,3]这样的短数组把入栈、出栈、结算的过程完整写在纸上，之后再写代码。只有亲手推过，模板才算真正变成自己的。
3. 从BFS到滑动窗口：队列的三种打开方式
3.1 BFS层序遍历：队列最顺理成章的用法
BFS用队列几乎是一个结论：二叉树的层序遍历、图的按层扩展、网格里的最短路径，套路都是先把起点入队，循环弹出队首，处理邻居，再把邻居入队。
但“按层输出”有一个特别容易踩的细节：队列里可能混着不同层的节点。比如处理第一层时，把第二层节点加进了队列尾部；如果直接在for循环里用len(q)作为循环次数，这些新加的节点会混进来。正确做法是把当前层长度先存到变量里，然后按这个数量循环。
from collections import deque def bfs_level_order(root): q = deque([root]) while q: sz = len(q) # 必须提前记录当前层节点数 for _ in range(sz): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right)注意如果处理的是图而不是树，要额外维护一个visited集合，否则环会让节点重复入队，队列可能越来越大。树的BFS不需要，因为树没有环。这个“拿到一层先数个数”的小技巧，在几乎所有层级类BFS里都通用。
3.2 单调队列：滑动窗口最大值如何做到O(n)
“滑动窗口最大值”是队列方向的另一座大山。给定数组和一个窗口大小k，求每个窗口内的最大值。暴力法是O(nk)，优先队列是O(n log k)，但单调队列可以做到O(n)。
思路是用双端队列维护“当前窗口最大值候选下标”，队首永远是最大值的下标。新元素进入时，先把队列尾部所有比它小的元素弹掉——这些元素在该新元素存活期间不可能成为最大值；再把队首所有已经滑出窗口的下标弹出。代码这样写：
def max_sliding_window(nums, k): from collections import deque q = deque() res = [] for i, v in enumerate(nums): while q and nums[q[-1]] <= v: q.pop() q.append(i) if q[0] <= i - k: q.popleft() if i >= k - 1: res.append(nums[q[0]]) return res注意它和单调栈的相似性：入场时都在清理“以后也用不上”的元素。区别在于，单调栈处理的是“下一个更大”这种距离问题，单调队列处理的是“固定窗口内的最大”这种区间问题。原理都是借助局部有序信息，避免对每个元素反复扫描。
3.3 优先队列不是队列：一个容易混淆的名字
“优先队列”这个名字很误导人。它本质是堆，出队顺序不按入队时间，而按优先级。C++里的priority_queue、Python里的heapq，和“队列”的FIFO语义没什么关系。
刷题场景看看哪些题型用堆：Top K问题、合并K个有序链表、数据流中位数。这些都需要“随时取全局最值”，是堆的长处。普通队列负责“按时间顺序依次处理”，优先队列负责“按权重顺序挑最值”。两者差别很大，做题前先想清楚题目想要哪种顺序，能省下大量返工时间。
4. 括号、表达式、递归转迭代：栈题的另外半壁江山
4.1 括号匹配为什么天然是栈
括号匹配几乎是每个人接触的第一道栈题。很多人背下了代码：左括号入栈，遇到右括号看栈顶是否匹配。但背后的原理值得再说清楚：匹配遵循“最近匹配原则”，一对括号之间不允许存在未闭合的其它类型括号。
拿“([)]”这个字符串举例，为什么它不合法？因为右括号]出现时，最近的未匹配左括号是[，但栈顶实际是(，类型对不上。再看“([{}])”，每一步右括号都能和最近的左括号配对。把“最近配对”翻译成数据结构，栈就是最直接的选择。
4.2 后缀表达式：把括号彻底去掉的栈式计算
逆波兰表达式求值是最经典的栈题之一，规则很直接：遇到数字入栈，遇到运算符弹出两个数，计算结果再入栈。后缀表达式的价值在于它不需要括号和优先级，计算顺序完全由栈的后进先出决定。
如果题目要求“中缀转后缀”，就要用调度场算法：数字直接输出；运算符根据优先级决定压栈或弹出；左括号直接入栈；右括号负责把左括号前的运算符弹空。这个转换完成后，再按后缀表达式规则用栈求值，你就能体会表达式求值题的本质：用栈消解运算符的优先级，让计算顺序变得线性而确定。
4.3 递归改写成显式栈：三步通用做法
二叉树的三种遍历是练习“递归转栈”的绝佳素材，因为递归的底层本身就在用系统栈。改成显式栈时要从“后进先出”反推压栈顺序：先被处理的节点要后压栈，后处理的节点要早压栈。
先看前序遍历“根左右”，迭代时应该先压右子节点、再压左子节点。因为栈是后进先出，这样左子节点才会先弹出处理。很多人第一次写都写反，这我得多说一句。中序遍历要一路走到最左，再用栈记录回溯路径。后序遍历更复杂，有一种经典写法是双栈：第一个栈按根、右、左压入，第二个栈接收出栈结果，最后第二个栈弹出的顺序天然就是左、右、根。
碰到复杂的递归改写时，一个通用技巧是栈里同时存状态标记，比如存(node, visited)这样的组合。第一次遇到节点压入状态0，左右子树处理完再遇到状态1的节点时就可以安心输出。这套打法在迭代解决很多二叉树题目时都很实用。
5. 栈和队列刷题避坑：几次返工换来的经验
5.1 空栈操作：一切栈题的第一隐患
有朋友A某天写括号匹配，while循环里直接写if stack[-1] == '('，输入全是右括号时程序直接崩溃。这是几乎所有栈题的第一坑：访问栈顶之前必须先判空。
括号匹配的正确处理顺序是：遇到右括号，先看栈是否为空，为空说明没有可配对的左括号，可以直接判定不合法；不为空时才去看栈顶。在单调栈里同样如此，while循环的条件里天然包含了stack为空的判断，所以模板里才写“while stack and ...”。这个顺序写反，测试数据只要稍微极端一点就会出问题。
5.2 存下标还是存值，默认选下标
单调栈模板里强调存下标，这是经过对比后我认为最稳妥的做法。存下标能拿到索引距离、能区分相同值的不同位置，在任何需要定位的题目里都适用。只存值的问题在于，重复元素出现时你分不清“这个值对应的是哪个位置”。
即使是一眼只看值的题目，比如滑动窗口最大值，你仍然需要一个下标来判断窗口是否过期。所以我的建议是默认存下标，除非你特别清楚存值也不会出问题，否则不要在考场上临时切换思路。这个习惯能让你少踩很多隐形的坑。
5.3 比较方向：小于还是大于，别凭感觉写
单调栈的while条件到底写nums[stack[-1]] < nums[i]还是nums[stack[-1]] > nums[i]，取决于题目找的是下一个更大还是下一个更小元素。单调队列里是弹出队尾比当前小的还是比当前大的，取决于要最大还是最小。这类方向错误代码能编译、小数据能过、大数据就出错，特别难排查。
我自己的习惯是，写代码前先在注释里写清一句：“维护递减栈，弹出所有小于当前值的元素”。先写意图再写实现，方向错误基本就消失了一半。单独写模板时多花几秒，后面调bug能省回十几分钟。
5.4 循环队列的判空判满：预留一个坑位的必要性
设计循环队列的题目，好多人卡在判空判满。如果front指向队头，rear指向队尾的下一个位置，那么队空条件是front == rear，队满条件是(rear + 1) % capacity == front。
这意味着数组里始终要空出一个位置，这样空和满两种状态才不会混淆。如果不想浪费这个位置，就得用单独的size变量记录元素个数。我碰到这类设计题时更推荐带size的做法：逻辑直白，代码短，容错率高。无论哪种实现，容量为1、容量为2的小用例都要自己推一遍，边界条件基本就验证完了。
5.5 递归转栈的逆序问题：压栈顺序决定处理顺序
把递归改成迭代时，压栈顺序反了，结果就完全不对。如果递归里是先处理左子树再处理右子树，那么往栈里压入的顺序必须反过来：先右后左。栈是后进先出的，压栈顺序决定弹出顺序，所以先压的反而后处理。
对图的深度优先遍历也一样：如果按邻接表的顺序依次压入邻居，弹出的顺序和递归的先序访问方式会不一致。这也是为什么迭代DFS比递归DFS要更细致地管理访问状态。遇到这类题，建议先在纸上把递归的执行顺序画出来，再按逆序去压栈。
6. 栈和队列的刷题路线：按难度分层的执行清单
6.1 第一阶段：跑通基础操作
先做几个热身题：“用两个栈实现队列”“用两个队列实现栈”“有效括号”。
“用两个栈实现队列”尤其值得认真写，它不只是API调用，而是要求你理解出队时如何把后进先出的顺序翻转成先进先出。每次入队都往stack_in里塞，出队时如果stack_out为空，就把stack_in全部倒过来，再弹出。这个“倒过来”的动作，就是对栈性质的一次深入理解。这类题写顺了，两个结构的差异也会清楚很多。
6.2 第二阶段：吃透三类模板题
这个阶段建议只做三类题，做到能闭眼写出来：单调栈（每日温度、下一个更大元素）、单调队列（滑动窗口最大值）、二叉树BFS（层序遍历）。这三类覆盖了栈和队列最高频的应用场景。
做这些题时不求快。我习惯每道题先画一遍过程图，再对照模板检查细节，最后合上代码徒手重写。模板用的是下标还是值，while条件里是大于还是小于，这些细节在这个阶段就要变成肌肉记忆。画图中的过程看多了，之后遇到题目会很有帮助。
6.3 第三阶段：复合题型才是真正的分水岭
当模板吃透之后，可以碰“接雨水”“柱状图最大矩形”“最长有效括号”“数据流中位数”这类综合题。它们虽然用栈或堆，但往往混着双指针、贪心、动态规划等方法。到了这一步就要意识到：栈和队列不是终点，它们只是众多解法中的一种工具。
比如最长有效括号，可以用栈，也可以用动态规划。能掌握两种角度，说明不是背题，而是真正理解了结构的适用边界。我自己在这个阶段的最大收获是：遇到看起来“不太常规”的数据结构题，已经能习惯性地先问一句——我为什么在这里要用栈或队列，换一种结构会发生什么。
我个人体会是，栈和队列这个专题，集中练两周，效果好过一天刷十道然后丢在一边。每次做题多问自己一句“为什么这里自然选择它”，比多背一个模板更有意义。最后分享一个习惯：做栈和队列的题，一定要在纸上画元素进出的过程图。单调栈里谁把谁赶出去了，单调队列里谁在窗口滑出后被弹掉，画几遍比看十遍题解都管用。这两周把手画热了，后面很多算法题都会轻松不少。
