栈和队列是算法题里最基础也最容易被忽略的两个数据结构。我见过不少人上来就刷二叉树、动态规划回头做笔试题发现连单调栈都写不顺反而是这两个“简单结构”卡了半天。其实栈和队列承载了DFS、BFS、表达式求值、滑动窗口等一堆核心场景的底层逻辑把它们吃透后面很多题都是一通百通。这篇文章就围绕算法刷题中的栈和队列从原理、经典题型到刷题路线、调试经验一次性讲透。1. 栈和队列的本质两个反过来的容器1.1 用生活场景一眼看懂两种结构栈最典型的比喻是叠盘子。你只能从最上面拿盘子新盘子也只能放在最上面后放进去的先拿出来也就是后进先出LIFO, Last In First Out。我在给身边人讲的时候更喜欢用“一叠便签纸”你写下第一条备忘压在桌上第二条盖在上面等你要看的时候最先看到的是最后写的那条这其实就是函数调用栈的运行方式。队列的比喻则是排队。谁先来谁先服务新来的人排到队尾队头的人先走也就是先进先出FIFO, First In First Out。想想食堂打饭、银行取号规则非常直观。面试的时候我会直接用一句话概括栈是“先进后出”队列是“先进先出”代码题里你只要搞清楚“谁先被处理”就能判断该用哪个。两个结构的核心操作也非常简单栈push压入、pop弹出栈顶、peek/top查看栈顶、isEmpty判空队列enqueue入队、dequeue出队、front/peek查看队头、isEmpty判空别看操作少很多复杂题就是在这些操作上叠加业务逻辑。比如括号匹配就是“遇到左括号入栈遇到右括号出栈并检查匹配”单调栈就是在入栈前加一个大小判断滑动窗口最大值就是在队列两端做维护。结构是骨架规则才是灵魂。1.2 底层实现数组、链表与语言选型刷题时很多语言已经封装好了栈和队列但明白底层实现能帮你避开不少坑。用数组实现栈最直接一个数组加一个栈顶指针 toppush 就是 arr[top] xpop 就是 top--小心数组越界就行。数组实现的栈连续内存随机访问方便缺点是扩容时要搬数据但刷题场景基本不用担心这个。链表实现栈则用头插法每次 push 和 pop 都在链表头部操作不需要搬移数据也不怕扩容问题缺点是每个节点多存一个指针内存占用略高。队列用数组实现时需要多一个 head 和 tail 指针。一个容易踩坑的地方是如果反复入队出队tail 一直往后走前面却空着一大块这叫“假溢出”。解法是循环队列让 tail 走到末尾后回到开头继续用Java 里 ArrayDequeC 里 deque 在底层都有类似的思路。链表实现队列则维护 head 和 tail 两个指针入队在 tail 后面加节点出队从 head 取节点所有操作都是 O(1)。语言层面我建议刷题时这样选C直接用 STL 的 stack底层默认是 deque队列用 queue。竞赛和面试环境支持都很好。Java栈推荐 ArrayDeque注意尽量别用老的 Stack 类它继承 Vector线程同步带来的开销没有必要队列用 ArrayDeque 或 LinkedList。Python栈直接用 listappend 和 pop 都是 O(1)队列建议用 collections.deque不要用 list.pop(0)那是 O(n) 的。语言封装不是万能的有的题比如单调栈其实不需要真的存元素而是存下标这在写的时候要特别留意。2. 栈的经典应用从括号匹配到表达式计算2.1 括号匹配入栈出栈的入门第一课括号匹配是栈的“hello world”题目。给定一个只包含 ( ) [ ] { } 的字符串判断括号是否合法闭合。思路非常清楚遍历字符串遇到左括号就压栈遇到右括号就取出栈顶元素判断是否匹配不匹配直接返回 false遍历结束后栈必须为空否则说明有左括号没闭合。我第一次写这道题时犯过一个低级错误只判断了数量相等没判断括号类型结果是 ([)] 这样的错误组合也被我判成合法后来意识到必须用栈去配对而不能只计数。代码模板大致是这样的Pythondef 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这个模板一定要熟到闭着眼睛能写出来。后面很多题都是它的变体比如“括号生成”“最长有效括号”“删除无效括号”。其中“最长有效括号”是把下标也存进栈通过在栈底保留一个“最后一个未匹配右括号的位置”来计算长度这就开始从结构题向思维题进阶了。2.2 表达式求值中缀转后缀与双栈思想表达式求值我觉得是栈最能体现价值的地方因为它把“计算顺序”这种隐式规则用显式的数据结构表现了出来。正常情况下我们写的是中缀表达式比如 3 4 * 2但计算机处理起来很别扭因为有优先级和括号所以需要一个标准的转换思路。一个方案是先转后缀表达式逆波兰式再对后缀表达式求值。转后缀的规则是遇到数字直接输出遇到左括号入栈遇到右括号弹栈并输出直到遇到左括号遇到运算符弹栈并输出所有优先级大于等于它的栈顶运算符然后自己入栈遍历结束后弹出栈中剩余运算符举个具体的例子中缀 3 4 * 2读入 3 输出读入 入栈读入 4 输出读入 * 因为优先级高于栈顶 所以入栈读入 2 输出结束弹出 * 和 得到后缀 3 4 2 * 。求后缀时再开一个栈遇到数字压栈遇到运算符弹出两个数字计算结果再压回去最后栈顶就是答案。如果不想转后缀也可以双栈直接算一个数字栈、一个运算符栈遇到右括号就弹栈计算遇到运算符根据优先级决定是否先算栈里的。LeetCode 227 基本计算器 II 就是这个思路面试里出现频率还挺高的。实操中我最想提醒的一点是减法除法要注意出栈顺序。后缀求值里第一次弹出的是右操作数第二次弹出的才是左操作数很多人在这里写反导致结果错得莫名其妙。2.3 单调栈下一个更大元素的通用套路单调栈是栈的进阶应用也是面试高频重点。所谓单调栈就是栈内元素保持单调递增或递减核心用途是“找每个元素左边或右边第一个比它大/小的元素”。最经典的题是“每日温度”给你一个每日气温列表返回一个列表表示对于每一天要等多少天才能等到一个更高的温度如果没有就填 0。暴力解法是 O(n^2)但单调栈可以做到 O(n)。我在刷题时总结了一个很顺手的心法如果要找“右边第一个更大”就从右往左遍历维护一个单调递减栈栈底到栈顶从大到小遇到当前元素比栈顶大时一直弹出剩下的栈顶就是右边第一个比它大的如果要找“右边第一个更小”反过来维护单调递增栈。还有人喜欢从左往右遍历配合“当前位置元素作为出栈元素的下一个更大值”的视角两种写法都行关键是别混。我个人的习惯是统一用从右往左因为逻辑更直观只需要想“右边的信息我已经处理过存在栈里”。“柱状图中最大的矩形”是这道题的升级版利用了单调栈找左右边界很多人在这一题卡很久。我的建议是先不要急着做这个把“下一个更大元素”的变形题刷熟比如“下一个更大元素 II”循环数组、“股票价格跨度”“移掉 K 位数字”再做柱状图。移掉 K 位数字也是一个很有意思的变形维护一个单调递增栈遇到当前数字比栈顶小时弹出栈顶相当于删掉高位的较大数字使最终数字尽可能小。单调栈初学会觉得抽象我给个类比想象你在队伍里后面来了一个比你高的人那么对于你来说你看不到更后面的人了因为这个人已经挡住了视线。这个“遮挡”关系就是单调栈弹出的时机。3. 队列的经典应用从BFS到滑动窗口3.1 广度优先搜索层序遍历与最短路径队列最常见的应用是广度优先搜索BFS它天然符合“一层一层向外扩展”的特性。二叉树的层序遍历就是典型题从根节点开始入队每次处理一层的全部节点把它们的子节点入队就得到了按层输出的结果。面试里 BFS 的代码模板也比较固定def bfs(root): if not root: return [] queue deque([root]) result [] while queue: level [] for _ in range(len(queue)): # 这一层的节点 node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result注意这里用了一个关键操作在进入循环时先记录 len(queue)这样就能区分当前层和下一层否则循环会一口气走完所有节点。我第一次写层序遍历时就栽在这个上只写了 queue 不为空就 popleft结果合并成了一维输出。除了二叉树BFS 在网格题目里也大量出现比如“岛屿数量”“腐烂的橘子”“打开转盘锁”。网格 BFS 往往需要一个 visited 数组记录已经访问过的位置防止重复入队否则会有大量无效计算甚至死循环。我在刷“腐烂的橘子”时学到的一个技巧是可以在队列里同时存坐标和时间或者在每一层循环时累加时间这样天然得到传播轮数。BFS 的复杂度一般是 O(VE)V 是节点数E 是边数。网格题里每个格子就是节点、上下左右就是边所以只要每个格子的邻居枚举一遍整体就是 O(行×列)。3.2 单调队列与滑动窗口最大值单调队列是队列里的另一个高频考点和单调栈是同一个思想用在队头队尾两端的操作上一般基于双端队列实现。最典型的题目是“滑动窗口最大值”给你一个数组和一个长度为 k 的滑动窗口窗口每向右移动一格返回窗口内最大值。直观方法是每个窗口都扫一遍 k 个元素复杂度 O(nk)但如果用单调队列维护“窗口内可能成为最大值的候选下标”每个元素最多入队出队一次整体 O(n)。核心维护逻辑是这样的新元素进来时如果队尾元素比当前元素小那么这些队尾元素在窗口里永远不可能成为最大值因为有更大的新元素直接弹出队头元素如果已经滑出窗口范围下标小于 i-k1也要弹出每次窗口的队头就是当前窗口最大值。单调队列和单调栈的区别就是单调栈只在一端操作单调队列两边都要管一个管候选有效性一个管过期淘汰。我觉得理解了这个点两个知识点就无缝衔接了。代码模板Pythonfrom collections import deque def maxSlidingWindow(nums, k): dq deque() res [] for i, num in enumerate(nums): # 移除已经滑出窗口的队头 if dq and dq[0] i - k: dq.popleft() # 保持队列内单调递减 while dq and nums[dq[-1]] num: dq.pop() dq.append(i) if i k - 1: res.append(nums[dq[0]]) return res我第一次写单调队列时犯过两个错误一是忘了存下标只存了值导致无法判断过期二是比较大小用了 而不是 导致相等元素情况处理不对结果窗口里出现重复的“最大值”候选。经验是滑动窗口题里队列存下标几乎总是比存值更稳妥。3.3 优先队列与 Top K 问题优先队列本质上是一种特殊的队列出队顺序由优先级决定而不是单纯的先进先出。刷题时 Top K 问题、合并 K 个有序链表、任务调度、数据流中位数都会用到它。我在实际写题时对优先队列有一些心得Java 的 PriorityQueue 默认是小顶堆如果要大顶堆就传 Comparator.reverseOrder()Python 的 heapq 是小顶堆想要大顶堆就存负数C 的 priority_queue默认是 max-heap想要最小堆就传 greater 。Top K 高频元素这类题里主流方案是用小顶堆维护当前最大的 K 个元素新元素进堆如果堆大小超过 K 就弹出堆顶最小元素。这样堆里剩下的就是最大的 K 个。很多人误以为要维护大顶堆但大顶堆会把最大值弹出那就全错了。我曾经在面试题“数据流中的中位数”里用了两个优先队列一个大顶堆存左半部分一个小顶堆存右半部分始终保持两者元素个数差不超过 1中位数就是两个堆顶的均值或其中一个。这个方法思路不算难但写起来细节不少我建议自己完整手写一遍别光看题解。优先队列的复杂度是 O(log n) 的入队出队所以在数据规模大时比排序方案更优。4. 刷题路线与练习方法怎么把栈和队列刷出效果4.1 由浅入深的分阶段题目清单我把自己刷栈和队列的路径整理成了一个三阶段清单供参考。第一阶段是基础结构题目标是写熟模板、不卡壳第二阶段是核心高频题目标是理解思路并总结通用解法第三阶段是进阶综合题目标是能把这些结构叠加到复杂场景里。第一阶段基础有效的括号栈入门的必修课用队列实现栈 / 用栈实现队列考察两个结构的互相转换最小栈在栈基础上维护辅助信息设计循环队列熟悉数组实现队列的边界第二阶段核心应用每日温度单调栈入门下一个更大元素 I / II单调栈变体滑动窗口最大值单调队列二叉树的层序遍历队列BFS岛屿数量网格 BFS逆波兰表达式求值表达式栈的应用第三阶段进阶提升柱状图中最大的矩形单调栈求边界移掉 K 位数字单调栈的贪心玩法腐烂的橘子多源 BFS 和时间传播数据流中的中位数双优先队列合并 K 个有序链表优先队列做多路归并这个列表不是让你一遍刷过去就完事而是每个做完之后要回头看这个题考的是栈还是队列核心操作是什么如果换一种数据结构还能解吗比如“有效的括号”可以不用栈用数组模拟层序遍历也可以用递归来做。多换个角度考虑才能把一道题吃透。4.2 时间分配与刷题节奏新手最容易犯的错是“贪多”。一天刷 10 道题每道都是看题解半懂不懂过两天全忘了。我自己带人刷题的经验是三遍法第一遍拿到题目先想 15 分钟。别急着看答案。哪怕最后发现思路完全错了这 15 分钟的思考也会让“正确答案”在大脑里留下更深的印记。想不出来就去看题解但看完必须合上答案自己写一遍不能复制粘贴。第二遍当天晚上或第二天不看任何资料独立再写一遍。写不出就回去看题解然后隔两三天再写。这一步是真正把思路变成肌肉记忆的关键。第三遍一周后再做一次同类题验证自己是否掌握了通法而不仅仅是背下了那道题的答案。节奏上我建议栈和队列入门期每天 2~3 道基础题持续一周第二轮每天 1~2 道核心题持续两周第三轮开始搭配其他数据结构交叉练习。总题量不一定非要很大但每道都要按三遍法来这样核心题做 20 道左右就能覆盖绝大多数面试场景。答题顺序也有讲究。很多人一上来就做“柱状图中最大的矩形”结果被单调栈劝退。我建议先做“下一个更大元素 I”再做“每日温度”再回到“柱状图”梯度会平滑很多。4.3 一题多解与总结模板很多人刷题只看最短路我觉得有点浪费题目价值。一个好题往往有多种思路有的用栈、有的用队列、有的用双指针、有的用动态规划。比如“接雨水”这道题既可以用单调栈也可以用双指针还能用动态规划。如果你只会一种那面试时一旦被追问“还有没有别的做法”就会很被动。我习惯用一个表格来总结每个数据结构的经典模板比如题目类型核心数据结构关键操作适用信号括号匹配栈入栈出栈配对左右成对出现单调栈求边界单调栈弹出时结算找左右第一个更大/更小BFS 层序队列按层记录大小最短路径/逐层扩展滑动窗口最值单调队列队尾去冗余、队头去过期固定窗口最值Top K 问题优先队列维护 K 大小堆找最大/最小的K个表达式求值双栈/栈后缀优先级判断中缀表达式这个表格建议自己整理一遍效果远好于直接拿别人的。整理的过程中你会意识到单调栈和单调队列其实共享同一套思维BFS 和图的遍历本质上也是队列能力的外延。把“为什么用这个结构”想清楚了才算真正掌握。5. 常见错误与Debug技巧实录5.1 我在刷题中踩过的坑栈和队列看起来简单实际写起来容易在细节上翻车。我总结几个高频坑。空栈访问是我见过最多的错误。比如“有效的括号”里如果字符串以右括号开头直接弹出栈顶就会报错因为栈还是空的。先后顺序应该是先判断栈是否为空再取栈顶。我的习惯是每次 pop 前都问自己一句“这个栈此刻会不会是空的”如果可能就先判空。队列的 popleft 和 list.pop(0) 的差别也值得记一下。Python 里 deque.popleft() 是 O(1)list.pop(0) 是 O(n)。刷算法题时如果用 list 当队列数据量一大就会超时换了 deque 立刻通。同理Java 里用 LinkedList 实现队列有开销ArrayDeque 更轻量。单调栈/队列里的“等于”情况也常被忽略。找下一个更大元素时如果下一个元素和当前元素相等算不算比当前大要不要弹出这个直接决定结果。我在“每日温度”里一开始用的是 弹出结果相等元素也被替换答案就错了。所以这类题最好先在小样例上把边界推一遍。循环队列实现时的“空”和“满”判断同样容易错。数组实现循环队列时front tail 表示空(tail 1) % capacity front 表示满。这个“会浪费一个位置”的约定是很多教材的标准做法但自己写代码时容易搞混我建议直接画个图给数组画成圈标上 front 和 tail 的移动方向比死记公式靠谱得多。5.2 调试方法小样例与可视化算法题 Debug 有一个非常好用又常被忽略的方法构造一个足够小但不平凡的测试样例然后手工模拟每一步。拿“滑动窗口最大值”举例。数组 [1, 3, -1, -3, 5, 3, 6, 7]k3我会把每次窗口移动后的队列内容写在纸上初始窗口 [1, 3, -1]队列存 [1, 3] 的下标 1、2最大值 3窗口右移 [3, -1, -3]新元素 -3 入队队尾 -1 -3 所以保留队列 [1, 2, 3]最大值 3窗口右移 [-1, -3, 5]新元素 5 把队列里所有小于 5 的都弹出队列只剩 5 的下标最大值 5再右移 [-3, 5, 3]新元素 3 入队队列 [4, 5]最大值 5手工模拟几步之后你对“为什么队尾要弹出所有更小的”“什么时候队头过期”的理解会非常清晰。遇到递归类题目时我还会加临时打印把每次入栈出栈的元素打出来尤其适合排查表达式求值、括号生成这类顺序敏感的题。画图工具不必太高级纸笔或者白板就行。我现在做复杂题时还是习惯先在编辑器里画一棵树再写代码效率反而更高。5.3 关于模拟题和设计题的小心得“用栈实现队列”“用队列实现栈”“设计最小栈”这类题看起来是纯结构模拟其实很考验你对两个结构本质的理解。我分享一下我的思考方法。用两个栈实现队列思路是一个栈做入队一个栈做出队。入队时直接压入 inStack出队时如果 outStack 为空就把 inStack 的所有元素依次弹出并压入 outStack然后从 outStack 弹栈。这样负负得正反过来就是本来先进先出的顺序。这个操作有个懒加载的巧妙点不必每次出队都搬移只在 outStack 为空时搬移均摊复杂度是 O(1)。用两个队列实现栈相对绕一些。核心思路是入队时把新元素放到一个空队列再把另一个队列的所有元素搬过来这样新元素就在队头了出队时直接 popleft。这个操作每次入栈是 O(n)但要理解为什么这样才能改变队列先进先出的特性建议动笔画一下两个队列里元素的顺序变化。最小栈的经典做法是额外维护一个“单调不增”的辅助栈每当入栈元素小于等于当前最小值时也推入辅助栈否则辅助栈推入当前最小值。出栈时两个栈同步出。这样 getMin 始终是辅助栈栈顶。这个题的变体还有“用常数空间实现最小栈”在元素中存差值但我觉得先把辅助栈版本写透再谈优化也不迟。设计题还有一个通用的原则先确认所有操作的时间复杂度要求再选底层结构。比如“设计循环双端队列”要求头尾都能插入删除最好直接用数组维护首尾指针而不是每次搬移元素。而这些边界条件恰恰是面试官最爱追问的部分。6. 从刷题到面试几个临场技巧6.1 面试时怎么描述思路我在模拟面试里发现很多人代码写得出来但讲不清楚尤其讲不明白“为什么用栈而不用队列”。面试官通常想听的是三点这个结构的特性是什么、这道题需要什么特性、两者怎么匹配。以单调栈为例比较好的话术是“这道题要找每个元素右边第一个比它大的元素。如果暴力做每个元素都要往后扫描。我可以维护一个单调递减的栈从右往左遍历栈里存的是右边已经存在的候选。当前元素如果比栈顶大就弹出直到找到比它大的栈顶那个栈顶就是答案。每个元素最多入栈出栈一次所以总复杂度 O(n)。”这样描述比“这题用单调栈秒了”要好得多。面试官在意的不是你见过这道题而是你遇到新题时如何推理。6.2 时间复杂度与空间复杂度的瞬时判断栈和队列的题基本都是线性复杂度但面试官仍然可能追问极端情况。所以我习惯在写完代码后自己快速算一遍每个元素最多入栈/出栈一次操作数 O(n)均摊 O(1)总体 O(n)队列 BFS 每个节点入队出队一次总时间 O(VE)空间 O(V)最坏情况队里全是同一层节点单调栈空间最坏 O(n)当整个序列单调递增/递减时栈会存所有元素有一个细节是关于“均摊 O(1)”的解释。用两个栈模拟队列时虽然某一次出队可能触发整栈搬移看起来是 O(n)但每个元素最多被搬到 outStack 一次、再弹出一次所以整体均摊 O(1)。这种均摊分析是面试加分项值得专门练口头表述。6.3 刷题心态不要被难度标签吓住最后聊一点心态。栈和队列的题在 LeetCode 上很多标着 Easy 和 Medium但实际做起来可能比 Hard 还绕。我第一次接触“柱状图中最大的矩形”时看了三遍题解才明白单调栈为什么要弹到第一个小于当前高度的位置才结算面积。这很正常。不要因为一道题不会就自我怀疑更不要因为它是 Medium 就觉得自己基础差。算法学习本来就是一个反复相遇、反复加深的过程。今天没看懂隔两周再回来很可能就有种“原来如此”的感觉。另外我建议不要沉迷于题量。有人刷了 300 道题遇到新题照样懵有人只刷 80 道却把每道题的多种解法都嚼碎了面试反而不慌。关键不在于见过多少题而在于你能否把一个结构的本质特性抽象出来。栈和队列这两个东西结构简单到不能再简单但它们是一切递归、一切搜索、一切调度问题的基础。把基础打牢比盲目往上冲更划算。如果你现在刚开始刷算法题不妨就从“有效的括号”开始写第一道栈题从“层序遍历”写第一道队列题。写完后对照这篇文章里的模板整理自己的笔记。过了两周再回来重写一遍你会发现手感和思路完全不一样。这个过程就是刷题真正出效果的过程。