栈与队列这两个东西大概是算法题里最“说着都会写起来翻车”的类别了。无论是后端、客户端还是数据岗只要面试考算法几乎必有一道栈或队列的题。它看起来不过就是先进后出、先进先出可真到笔试环节空栈访问、队列边界、单调性维护随便一个坑都能让代码瞬间崩掉。这篇文章专门拆解这类面试题从高频考点、解题模板到现场避坑把自己刷题时反复用到的套路整理出来。新手可以先把它当字典面过几次再回头看一定会有新体会。1. 栈与队列在面试中的真正地位1.1 栈就是把“后发生的先处理”变成显式规则先聊栈。栈是一种限制只在表尾进行插入和删除的线性表这个表尾叫栈顶。很多人喜欢用一叠盘子来类比你总是先洗一个盘子放到最上面要用的时候又先取最上面那个。也就是说后放进去的先出来这就是后进先出。问题在于面试官不会直接问你“什么是后进先出”他们会把场景包装成函数调用、编辑撤销、路径转换、括号匹配等等。你要能识别出这些场景背后的栈模型。举个例子遇到“最近匹配”“回退”“撤销”“反转”这类关键词时第一反应就应该是栈。有一次我帮一位朋友看他代码他处理字符串去重用了一个双重循环复杂度 O(n²)实际上这类题用栈扫一遍就能 O(n) 解决。不要小看这种映射能力它才是面试真正的考察点。很多同学以为栈只会出现在括号题里其实表达式求值、二叉树遍历的迭代写法、模拟浏览器的前进后退全都是栈。面试官考栈本质是看你有没有“把递归过程改成显式过程”的能力。递归本身就是函数的调用栈你写的每一次 self 调用都会被压进系统栈换成一个你自己维护的栈思路会变得清晰很多也更容易规避深层递归的崩溃风险。1.2 队列不只是排队双端队列和优先队列才是区分度队列本身是先进先出先来的人先服务就像食堂打饭。面试中队列最经典的价值是配合 BFS广度优先搜索因为 BFS 天然要求逐层处理而队列的出队顺序恰好就是入队顺序。二叉树层序遍历、网格求最短路、拓扑排序几乎都是队列的“主场”。不过近年面试题更爱考队列的变体。第一个变体是双端队列也就是 Deque两头都能进能出。滑动窗口最大值、部分 BFS 最短路问题都靠它优化。第二个变体是优先队列也就是堆能动态维护最大值或最小值专门用来解决 TopK、合并 K 个有序序列、数据流中位数这类问题。第三个变体是循环队列它考察你能不能自己用数组实现一个有界队列并正确判断队空队满。如果你把“队列”只理解成排队就会漏掉后面这几种高频题型。面试官想看到的是你不仅会用现成的队列 API还能说清底层结构、时间复杂度和适用场景。比如双端队列为什么能替代普通队列做 BFS优先队列为什么是 log n 的插入代价这些都是现场追问的高频点。2. 栈类题型的高频套路拆解2.1 括号匹配固定模板与状态机思维括号匹配是栈类题里的“开胃菜”也是很多公司一面手写题。题目描述一般长这样给定一个只包含( ) { } [ ]的字符串判断它是否有效。有效是指左括号必须用相同类型的右括号闭合并且闭合顺序正确。这个题最直接的思路就是遇到左括号入栈遇到右括号去匹配栈顶匹配成功就弹出不匹配直接返回 false。我第一次写这个题时栽过一跤只记得左右括号要匹配却忘了最后还要检查栈是不是空的。输入(((时我的代码会返回 true因为它只看每个右括号是否都有栈顶可匹配可根本没有右括号来处理那三个左括号。所以一定要记住一个口诀左括号入栈右括号对栈顶全部扫描完栈空才算对。用 Python 写标准模板大概是这样def is_valid(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面试时可以顺手把复杂度说清楚每个字符最多入栈出栈一次时间 O(n)空间 O(n)。括号匹配这类题本质是“最近发生的左括号必须最先被匹配”也就是后进先出。你要是不用栈改用一个计数器只数左括号右括号数量遇到([)]这种交错情况就会误判因为数量对得上但顺序错了。这就是为什么栈是这道题的唯一最优结构。从括号匹配还能引申到“最长有效括号”和“括号生成”。最长有效括号不能只靠单调栈还需要用栈保存左括号下标并在匹配失败时更新起始起点括号生成则要用回溯生成所有合法组合属于栈思想与递归的结合。面试中如果遇到这些扩展题先默写基础版本再在基础框架上加状态变量。2.2 单调栈用空间换下一个更大/更小值单调栈是栈类题里区分度最高的一套模型。它解决的问题非常典型给你一个数组让你求每个元素左边或右边第一个比它大或比它小的元素。最典型的例子是“下一个更大元素”和“每日温度”。暴力解法是双重循环时间 O(n²)单调栈能做到 O(n)因为每个元素最多进栈一次、出栈一次。单调栈的基本思路是维护一个从栈底到栈顶单调递减或单调递增的栈。以“求右边第一个更大元素”为例我们需要一个栈底大、栈顶小的单调递减栈。遍历数组时每来一个新元素就把栈中所有比它小的元素依次弹出这些被弹出的元素它们的“下一个更大元素”就是当前新元素。也就是说单调栈用“延迟匹配”的方式把每个元素与它右侧更大的元素连起来def next_greater(nums): n len(nums) res [-1] * n stack [] # 存下标 for i in range(n): while stack and nums[stack[-1]] nums[i]: idx stack.pop() res[idx] nums[i] stack.append(i) return res这里有个关键细节栈里存的是下标还是值我强烈建议存下标。因为很多题不仅要你返回下一个更大元素本身还要你返回它们之间的距离比如“每日温度”要的是几天后温度升高。存下标可以同时拿到值和距离直接用值的话就得额外维护位置容易出错。另一个细节是重复元素时用还是。如果题目要求“严格大于”才算更大则遇到相等元素不要弹栈用如果要求“大于等于”则用。这个看似很小的判断结果会差很多。我见过不少候选人卡在这一步就是因为没有在写代码前明确“严格”两个字。单调栈真正的难点不是模板而是识别出能用单调栈。一旦题目里出现“左边第一个小于我的位置”“右边最近一个比它高的柱子”“数组中所有元素的左右最大区间”这类描述就可以往单调栈上靠。柱状图中最大的矩形、接雨水、股票价格跨度都会用到它。学单调栈的时候建议把“栈里存什么、什么时候弹栈、弹栈时能算什么答案”三个问题写下来形成肌肉记忆。2.3 双栈互相实现面得最多的基础题“用两个栈实现队列”和“用两个队列实现栈”是栈面试里的常客。第一道题非常经典要求实现的队列要支持 push、pop、peek、empty并且只能用两个栈。思路是准备两个栈一个inStack负责入队一个outStack负责出队。入队时直接 push 进inStack出队时先看outStack是否为空如果为空就把inStack里的所有元素依次弹出再压入outStack这样inStack底部的元素就跑到了outStack顶部实现先进先出。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x): self.in_stack.append(x) def pop(self): self.peek() return self.out_stack.pop() def peek(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self): return not self.in_stack and not self.out_stack这个解法的核心是“倒灌”时机只有outStack为空时才从inStack倒数据否则直接使用outStack。为什么不能每次出队都倒因为这样会把已有的顺序打乱而且平摊复杂度会变差。这里时间复杂度是均摊 O(1)每个元素最多被 push 两次、pop 两次。用两个队列实现栈则相反用普通队列的先进先出模拟后进先出。一个常见做法是入栈时把新元素放进queue1出栈时把queue1中的元素除最后一个外全部移入queue2最后一个元素出栈后交换两个队列的角色。这个解法简单但每次出栈需要 O(n) 移动元素整体不如用两个栈实现队列那么有效率。面试官更希望你先把两个栈实现队列写得干净利落再快速把另一个方向也完成。这类题之所以高频是因为它考察的是“用受限的数据结构组合出新的能力”。实际工程里跨进程通信、批量任务导入、缓存淘汰等场景经常需要你从底层结构开始设计而不是直接调高级 API。所以面试时不要只背代码要把“为什么能工作”讲明白。3. 队列类题型的高频套路拆解3.1 BFS层序遍历一遇到“层”就想到队列二叉树层序遍历大概是队列类面试题里最基础的。给你一棵二叉树要求按层输出每一层的节点值。解法就是用队列做 BFS但有一个非常容易踩的坑如果只是 while 循环里不断从队列中 pop你根本分不清哪些节点属于同一层。必须在一轮循环开始时先记录当前队列的长度size然后只处理size个节点这样刚好把这层的所有节点弹完下一层节点也已经全部入队。Python 模板长这样def level_order(root): if not root: return [] res [] q [root] while q: n len(q) cur [] for _ in range(n): node q.pop(0) cur.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(cur) return res注意这里我用的是pop(0)实际生产环境应该用collections.deque的popleft()因为 list 的pop(0)是 O(n)。我在面试时见过有人因为这里被扣分明明思路全对复杂度多写了一个 n。队列在 BFS 里的地位不只体现在二叉树。网格题里“从多个起点同时向外扩张”“求每个格子到最近敌人的距离”都是多源 BFS 的典型场景。只要题目要求“最短步数”“最少操作次数”“最近的某个状态”你基本可以立刻想到 BFS 加队列。BFS 之所以用队列是因为它天然按距离递增的顺序扩展节点先入队的节点一定离起点更近因此它出队时得到的距离就是最短距离。还有一个高频拓展是拓扑排序。对一个有向无环图做拓扑排序时我们需要维护入度为 0 的节点队列先把所有入度为 0 的节点入队然后不断弹出队首减少它所有邻居的入度一旦有邻居入度变为 0就继续入队。这个“入度减到 0 再入队”的过程本质上就是一个队列驱动的状态推进面试时经常和课程表、任务依赖订单一起出现。3.2 滑动窗口最大值单调队列的真实威力如果说单调栈是栈题的分水岭那单调队列就是队列题的分水岭。经典题“滑动窗口最大值”给定一个数组和一个窗口大小 k窗口从左往右移动要求输出每个窗口中的最大值。暴力做法每个窗口扫一遍时间是 O(nk)被问到复杂度瓶颈时候选人会想到用堆来维护可堆只能告诉你全局最大窗口移出去的元素没法方便地删除。真正的最优解法是单调队列也就是用双端队列维护窗口内从队头到队尾单调递减的下标。核心逻辑有三步每一步都要按顺序来第一清理队头把所有小于i - k 1的下标弹出第二维护单调性从队尾弹出所有值比当前元素小的下标再把当前下标压入队尾第三队头下标对应的值就是当前窗口最大值。为什么要把比当前元素小的全部弹出因为它们已经不可能再成为后续窗口的最大值了只要当前元素还在窗口内就会一直压着它们。这个“不可能再被需要”的思想是单调队列性能好的根因。from collections import deque def max_sliding_window(nums, k): dq deque() res [] for i, v in enumerate(nums): while dq and dq[0] i - k: dq.popleft() while dq and nums[dq[-1]] v: dq.pop() dq.append(i) if i k - 1: res.append(nums[dq[0]]) return res写这题时最容易错的就是过期下标判断。窗口范围是[i - k 1, i]所以队头下标如果小于等于i - k就应该弹出而不是小于i - k 1。另一个坑是队头清理和单调性维护的顺序必须先清理过期下标再检查单调性否则先弹出小值会误伤还在窗口内的元素。我刷题平台上看到很多人在评论里纠结“单调队列是不是一定要用双端队列”结论是必须的。因为你既要弹出队头过期元素又要从队尾弹出较小元素还需要在队尾加入新元素普通队列没法同时做到。这道题如果面试官问能不能优化到 O(n)你就要把“每个元素最多入队一次、出队一次”这个平摊分析说给他听。3.3 优先队列与TopK堆才是高频工具严格来说优先队列不是队列它底层是堆。但在算法面试分类上它和栈队列经常一起出现所以我把这块也放进来了。优先队列能解决的核心问题是动态维护一组元素中的最大或最小并支持快速插入和删除。面试题“前 K 个高频元素”“数据流中的第 K 大元素”“合并 K 个有序链表”都靠它。以“前 K 个高频元素”为例先用哈希表统计每个元素的频率然后维护一个大小为 K 的小顶堆。为什么是小顶堆因为小顶堆堆顶是当前 K 个候选里最小的那个每当遇到频率更大的候选就把堆顶替换掉最后堆里剩下的就是全局频率前 K 的元素。如果维护大顶堆你堆顶是最大却无法判断一个普通元素应不应该淘汰堆里哪个元素逻辑会一塌糊涂。Python 用heapq时默认就是小顶堆如果你需要大顶堆可以存负值模拟。Java 的PriorityQueue默认也是小顶堆自定义比较器时千万不要把比较写反。有一个坑是自定义 Comparator 的传递性如果你返回b - a在溢出风险非常大的 int 上会出诡异 bug最好使用Integer.compare(b, a)。优先队列的复杂度是插入 O(log n)、获取堆顶 O(1)。这决定了它适合“动态插入 反复取最值”的场景。比如实时排行榜、订单按优先级执行、任务调度都属于这个模型。如果题目里出现“前 K 大”“第 K 小”“最频繁”“最小的几个数”等词先想哈希统计再想堆基本不会跑偏。4. 实战代码模板与现场经验4.1 几个可以直接抄的栈模板面试时手写代码不比日常开发要尽可能减少多余的语法糖但也要结构清晰。通用的栈操作模板可以是stack [] # 入栈 stack.append(x) # 出栈 if stack: stack.pop() # 栈顶 if stack: stack[-1] # 判断空 if not stack: ...这套模板背下来之后所有括号匹配、路径解析、字符串去重题都能直接往上套。关键是在写任何pop()和stack[-1]之前先问自己一句栈空不空很多人就是省了if stack而引发空栈异常尤其在白板面试时这比写错算法本身更尴尬。单调栈模板也可以整理成固定格式栈内存下标while条件里先判断栈不空再比较数值弹出时更新答案循环结束后把当前下标入栈。如果你能在 30 秒内默写出这个框架留给“识别题型”的时间就会多很多。遇到“左边第一个比它大”这类镜像问题时只需要把遍历方向从右往左或者把比较符号反过来模板不变。4.2 Python/Java中队列与栈的实现差异很多刷题党一个很大的问题用的语言不同容器选型完全不一样。下面这个对照表是我自己做题时整理的分享给你。场景Python 推荐Java 推荐注意点栈listappend/popArrayDequepush/popJava 旧Stack有同步开销已不推荐普通队列collections.dequepopleftArrayDequepollPythonlist.pop(0)是 O(n)面试要避免双端队列collections.dequeArrayDeque两端操作都是 O(1)优先队列heapqPriorityQueuePython 默认小顶堆需要大顶堆存负值线程安全队列queue.QueueBlockingQueue面试题一般用不到提一句即可用 Java 写栈时很多人下意识写StackInteger但它继承自Vector每个方法都有同步锁性能不好而且它扫描无序。ArrayDeque是数组实现的双端队列既能当栈用也能当队列用所有操作都是 O(1)更符合现代 Java 的写法。Java 的LinkedList也能当栈或队列但它每个节点都要存前后指针空间开销更大性能也不如ArrayDeque。Python 里则要注意heapq是基于列表实现的但它不是线程安全的如果是多线程并发场景要用queue.PriorityQueue。面试手写时不用聊多线程但如果你能在复杂度分析完随口提一句“调用线程安全版本会给常数开销”很容易让面试官觉得你有工程意识。4.3 从暴力递归到显式栈的优化路径面试常常套路化地问一道二叉树遍历题先用递归三行写完然后追问“如果递归深度很大怎么办”这时候你要能改成显式栈的迭代写法。以前序遍历为例递归时代码是def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right)改成显式栈时因为栈是后进先出而前序遍历的顺序是“根、左、右”所以我们要先把右孩子压栈再把左孩子压栈。出栈顺序就会变成左孩子先出完成先左后右的遍历。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. 面试现场常见问题与排查技巧5.1 栈空/队列空的边界到底怎么防我在模拟面试中见过太多次这样的场景候选人思路完全正确代码跑到 return 前突然访问stack[-1]然后系统跳出一个空栈异常。现场顿时沉默。避免这个问题的最好方法不是想着“我这次记得判空”而是把判空嵌入每一处栈操作里。我自己的习惯是每次写完一个与栈相关的循环都手动跑一遍极简样例。比如括号匹配我必测、(、)三种输入单调栈我必测“数组长度为 1”和“所有元素都不满足弹出条件”的情况。这些边界值体积小一眼能看出问题。还有一个隐藏坑是“从队列中取元素前队列可能为空”的情况。BFS 层序遍历时如果 root 为空直接返回空列表这个问题很多人反而会忽略。优先队列则要小心heappop时堆已空。无论哪种容器我总结出的口诀是先判空再取值取完值再操作。5.2 使用递归还是使用栈拿不准时的判断标准面试时总有人纠结一个问题这道题该用递归还是用显式栈我给一个简单的判断流程。第一看问题的递归深度。如果输入规模可能是几万的链式二叉树递归深度很可能超系统栈此时毫不犹豫转显式栈。第二看问题是否需要“回溯”。如果既需要进入深层处理还需要回到上层恢复状态那么递归更直观用栈迭代需要手动维护状态栈容易出错。第三看面试官有没有追问复杂度。递归时间复杂度很多时候容易算错而显式栈模式的复杂度往往更清晰因为你能直接看出每个元素进出栈一次。实际操作中我建议先把自己最有把握的解法写出来再根据面试官反馈优化。面试不是笔试你完全可以在写代码前说一句“这个问题的处理顺序是后进先出我倾向于用栈模拟递归。”这句话本身就是加分项因为它证明你在有意识地选择数据结构而不是凭感觉。5.3 快速自测的十分钟检查清单每次写完栈或队列类代码在提交前我会用下面这个清单自查一遍。别小看这十分钟它能帮我避免大部分低级错误。检查所有pop()、peek()、top()调用之前是否已经确保容器非空。单调栈和单调队列里确认自己的比较符号是还是是否符合“严格”的要求。滑动窗口题确认过期下标判断是 i - k而不是其他。层序遍历确认size len(q)是在内层循环之前保存的而不是动态变化的。优先队列确认自定义比较器不会溢出且规则与题目要求一致。跑一遍极简用例空输入、单元素、全部相同元素、最大值位于窗口第一个或最后一个。复杂度口头算一遍栈/队列操作是否均摊 O(1)优先队列插入删除是否为 O(log n)。有时候算法思路全对最终却败在一个空指针或者一个边界条件。这套检查清单能让你在面试现场多一份从容至少提交之前你已经把这些最容易翻车的点全部过滤过。栈与队列类题目从数量上看不算多但它们覆盖的模型非常广括号匹配、表达式求值、单调栈、单调队列、BFS、拓扑排序、堆。我自己准备面试时常常把这几类经典题刷三遍。第一遍照着模板理解第二遍限时手写第三遍不看代码只口述思路和复杂度。三遍之后面试官再追问任何变体都不会慌了。唯一需要记住的是别把“会背题”当成“会算法”真正值钱的是你看到题目后能在三秒内判断出该用哪种数据结构以及为什么。