栈与队列这两个数据结构在力扣上被单拎出来作为面试题分类本身就说明了很多问题。我面试过不少候选人也刷过几百道题回头再看这个专题发现它其实就是考察两个底层能力抽象建模能力和边界处理能力。栈和队列的代码实现很简单复杂的是你怎么用它们去解决实际问题以及你在处理边界条件时够不够细心。这篇内容我会从面试官视角和刷题者视角两个方向去拆解把栈与队列相关的经典题型、核心套路、常见坑点都过一遍最后附上我自己的刷题顺序建议。无论你是准备春招秋招还是工作几年想补补基础这篇应该都能帮你在“栈与队列”这个专题上省下不少时间。1. 为什么面试总爱考栈与队列先回答一个很多人心里都有的疑问栈和队列这么基础的东西有什么好考的链表树图不是更能区分水平吗1.1 栈与队列真正的考察点栈与队列的题目表面考的是数据结构实际考的是三件事。第一你懂不懂“操作受限”这个设计思想。栈只允许在一端插入和删除队列一端进另一端出这种限制不是累赘而是为了在某些场景下简化问题模型。函数调用要用栈因为需要后调用的先返回操作系统里的任务调度用队列因为要保证先来先服务。面试官通过一道栈的题能看出你是否理解这种“通过限制操作换取逻辑清晰”的工程权衡。第二你能不能把陌生的场景抽象成熟悉的数据结构。括号匹配、表达式求值、浏览器后退、函数递归这些场景看起来八竿子打不着但核心逻辑都是“最近出现的元素最先被处理”这时候栈就是最自然的模型。很多候选人卡住不是不会写栈而是看不出这道题该用栈。第三你对边界条件的敏感度。栈空的时候能不能pop队列空的时候能不能peek单调栈遇到相等元素是弹出还是保留这些细节决定了你的代码能不能一次通过。1.2 效率与正确性的权衡除了上面三点栈与队列的题目还顺带考察了复杂度分析能力。比如“用栈实现队列”最直观的思路是两个栈倒腾但很多人写出来之后push是O(1)pop却是O(n)——这没问题但如果连续pop n次每次都是O(n)总复杂度就成了O(n²)。优秀解法会把“倒腾”的时机推迟到必要的时候做到均摊O(1)。这个优化过程能看出候选人是否养成了分析复杂度的习惯。我在面试中经常让候选人做“设计一个最小栈”这道题收到的答案五花八门有些人会用额外数组存历史最小值有些人会用两个栈但很少有人能说清楚“为什么辅助栈里要存的是当前最小值而不是每个元素对应的状态”。同样是AC的代码对原理的理解深度天差地别。这个专题刷透之后你的代码能力不一定有质的飞跃但对“为什么这么写”的理解会上一个台阶。2. 先搞清楚栈和队列的底层差异这一节先做个基础扫盲虽然简单但真的有很多人会在细节上翻车。2.1 易混淆的基础概念栈是后进先出LIFO队列是先进先出FIFO。这句话谁都会背但落到代码里有几个细节值得注意。栈的入栈叫push出栈叫pop看栈顶叫peek。队列的入队叫offer或add出队叫poll或remove看队头叫peek。Java的Stack类继承了Vector所以它是有索引的、可以随机访问的这在某种程度上破坏了栈的“操作受限”特性。我建议刷题时用Deque接口来实现栈而不是用Stack类因为Stack加锁导致性能较差而且继承Vector带来的随机访问能力会让代码逻辑不够纯粹。// 推荐用法用Deque模拟栈 DequeInteger stack new ArrayDeque(); stack.push(1); stack.push(2); int top stack.peek(); // 2 int popped stack.pop(); // 2队列的实现刷题时我一般用ArrayDeque或LinkedList。ArrayDeque底层是循环数组在头尾两端的操作都是O(1)而且省内存LinkedList是双向链表每个节点有额外的指针开销。如果只是用队列的FIFO功能ArrayDeque几乎总是更好的选择。2.2 两者在工程中的典型应用栈和队列不只是面试题它们的应用场景比你想的广得多。栈最经典的应用是函数调用。每次进入一个函数系统会把局部变量、返回地址等信息压入调用栈函数返回时再弹出。递归之所以容易栈溢出就是因为递归深度太大把系统调用栈撑爆了。你在力扣上做题时如果递归写法爆栈可以考虑改成显式栈模拟本质上就是自己维护一个栈来替代系统调用栈。另一个常见应用是表达式求值。编译原理里表达式转换成后缀表达式靠的就是栈。力扣上有一道“逆波兰表达式求值”就是直接给你后缀表达式让你算结果这也是栈的典型场景。队列在工程中更多是用于解耦和缓冲。消息队列是分布式系统里最基础的组件削峰填谷、异步解耦都靠它。操作系统里的进程调度也常用就绪队列。面试如果深挖你从“用队列实现栈”这道题延展到消息队列的选型考量会是一个非常加分的回答。3. 经典题型拆解从括号匹配到单调栈热身之后进入正题。这一节我挑了几道最有代表性的题目从思路到代码一步步拆给你看。3.1 括号匹配栈的“Hello World”题目给定一个只包含(、)、{、}、[、]的字符串判断字符串是否有效。这道题是栈的入门级题目思路很简单遍历字符串遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配则弹出不匹配则直接返回false。最后还要检查栈是否为空。public boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); MapCharacter, Character map new HashMap() {{ put(), (); put(}, {); put(], [); }}; for (char c : s.toCharArray()) { if (map.containsKey(c)) { // 右括号检查栈顶 if (stack.isEmpty() || stack.pop() ! map.get(c)) { return false; } } else { // 左括号入栈 stack.push(c); } } return stack.isEmpty(); }这里有两个易错点。易错点一遍历结束后忘了检查栈是否为空。如果字符串是((()前面三个左括号都入栈了遍历结束后栈不为空说明有左括号没被匹配应该返回false。易错点二右括号出现时栈已经为空。比如字符串是]遍历到第一个字符就发现栈为空此时应该直接返回false调用pop()会抛异常。3.2 最小栈空间换时间的经典题目设计一个支持push、pop、top操作并能在常数时间内检索到最小元素的栈。这道题的难点在于常数时间检索最小值。普通的栈只能拿到栈顶元素最小值可能需要遍历整个栈才能找到那就是O(n)了。核心思路是空间换时间用一个辅助栈同步记录每个状态下的最小值。push时如果新元素比辅助栈栈顶小就push新元素否则push辅助栈栈顶元素。这样辅助栈栈顶永远是当前栈的最小值。class MinStack { private DequeInteger stack; private DequeInteger minStack; public MinStack() { stack new ArrayDeque(); minStack new ArrayDeque(); } public void push(int val) { stack.push(val); if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } else { minStack.push(minStack.peek()); } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }这里的关键在于辅助栈的push策略。我见过很多候选人把更新逻辑写成“只要val小于辅助栈栈顶就push”这样当pop时辅助栈需要回退但你可能已经丢失了上一个最小值。所以更稳妥的做法是辅助栈每个位置都记录“当前栈顶状态下的最小值”pop时两个栈同步pop永远不会出错。这道题面试官接下来经常会问能不能把这个辅助栈省掉答案是可以用一个栈每个元素存两个值当前值和当前栈里的最小值。Java里可以new一个数组或者用一个内部类。空间复杂度是一样的只是实现上省了一个栈。3.3 用栈实现队列最经典的“双栈倒腾”题目使用两个栈实现先入先出队列。队列支持push、pop、peek、empty操作。这道题我在面试中出得最多。它的核心思路是“两个栈一个负责入队一个负责出队”。入队时直接push到输入栈出队时如果输出栈为空就把输入栈的所有元素倒腾到输出栈再从输出栈pop。因为栈是后进先出倒腾一次之后元素的顺序正好反过来了从输出栈pop出来的顺序就是入队顺序。class MyQueue { private DequeInteger inStack; private DequeInteger outStack; public MyQueue() { inStack new ArrayDeque(); outStack new ArrayDeque(); } public void push(int x) { inStack.push(x); } public int pop() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() outStack.isEmpty(); } }这个解法的精妙之处在于倒腾的时机。如果每次pop都把输入栈全倒腾到输出栈没倒腾完之前新的push只需要进输入栈不用管输出栈因为输出栈栈顶依然是对头直接pop就行。这样每个元素最多被移动两次均摊时间复杂度就是O(1)。我在面试中见过最典型的错误写法是每次pop之前先把输入栈全部倒入输出栈pop之后再全部倒回去。这样每个元素被移动了多次复杂度退化成O(n)。这种写法虽然结果对但考察复杂度时很容易暴露问题。提示面试时不要急着写代码先跟面试官说清楚思路。就说“我用两个栈一个专门入队一个专门出队出队时如果输出栈为空再把输入栈的元素倒过来”这是最容易让面试官点头的方案。3.4 单调栈栈中暗藏玄机如果说前面几道题是栈的基础应用那单调栈就是栈的进阶用法。单调栈不是什么新的数据结构它的本质是栈只不过你push元素的时候会做一些额外的处理保证栈内元素从栈底到栈顶是单调递增或递减的。单调栈的典型应用是解决“下一个更大元素”“前一个更小元素”这类问题。力扣的“每日温度”是单调栈的入门题题目是给你一个每日温度列表让你返回一个列表每个位置表示需要等多少天温度才会升高如果之后都不会升高就填0。public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] ans new int[n]; DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { // 当前温度比栈顶下标对应的温度高说明找到了栈顶的下一个更大值 while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) { int prev stack.pop(); ans[prev] i - prev; } stack.push(i); } return ans; }核心思路是维护一个栈栈里存的是下标从栈底到栈顶对应的温度是递减的。当新温度比栈顶温度高时说明栈顶元素等到了升温的一天两者的下标之差就是答案然后弹出栈顶继续比较新的栈顶。这样每个元素最多入栈一次、出栈一次时间复杂度O(n)空间复杂度O(n)。这种思路之所以叫“单调栈”是因为你保证了栈里的元素是单调的。你可能会问为什么存下标而不是直接存温度因为答案要求的是天数差值存下标才能方便计算间隔。3.5 接雨水从二维理解到代码实现“接雨水”是单调栈类题目里难度较高的一道也是面试中区分度比较大的一道题。题目给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。这题的解决方案不止一种可以用动态规划、双指针、单调栈。用单调栈的解法比较巧妙对理解栈在二维空间上的应用很有帮助。public int trap(int[] height) { int n height.length; int ans 0; DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { // 当前柱子比栈顶高说明可能形成凹槽 while (!stack.isEmpty() height[i] height[stack.peek()]) { int top stack.pop(); if (stack.isEmpty()) { break; // 栈空说明左边没有柱子了不能接水 } int left stack.peek(); int width i - left - 1; int boundedHeight Math.min(height[left], height[i]) - height[top]; ans width * boundedHeight; } stack.push(i); } return ans; }理解这个解法的关键是“按层接水”。弹出栈顶top之后新的栈顶left就是top左边最近的比它高的柱子当前遍历到的i是右边最近的比它高的柱子left和i之间形成了一个凹槽。凹槽的高度取决于两边较低的那根柱子减去top的高度宽度是i - left - 1。累加每个凹槽的水量就是总水量。注意很多人在这道题里卡住的点是“为什么弹出top后还要看left”。因为top只是局部的最低点它上面能接多少水还要看左边的墙有多高。如果没有left了说明这个“凹槽”的左边没有墙水会从左边流走不能接。4. 从题到面双端队列与其他变种栈和队列的面试题不只是上面那些还有双端队列、循环队列等变种。我把它们归到这个章节因为它们都是对“操作受限”的进一步拓展。4.1 双端队列既是栈又是队列双端队列Deque指的是可以在两端都进行插入和删除的队列。它在Java里是一个接口ArrayDeque和LinkedList都实现了它。它既能当栈用调用push/pop又能当队列用调用offer/poll。在做“滑动窗口最大值”这道题时双端队列是标准解法。题目是给一个整数数组和一个大小为k的滑动窗口每次窗口向右移动一位返回每个窗口中的最大值。public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 弹出窗口外的元素 while (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 弹出队尾所有比当前元素小的元素 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); if (i k - 1) { ans[i - k 1] nums[deque.peekFirst()]; } } return ans; }这个思路的核心是队头永远是滑动窗口内最大元素的下标。每次新元素进来先清理队头那些已经滑出窗口的下标然后把队尾所有比新元素小的下标弹出因为它们在新元素面前永远不可能成为最大值了。最后把新元素下标放到队尾。为什么用Deque而不是普通队列因为我们需要在队尾也能执行删除操作去弹出那些“不够大”的元素。普通队列只能在队头出队满足不了这个需求。这也是面试中的加分点能说出来“为什么选Deque”比直接背代码强得多。4.2 循环队列数组实现中的环形思维循环队列的题目在面试中出现频率不低它考察的是你用数组实现队列时对环形结构的理解。普通数组实现队列pop之后队头前移前面空出来的位置就浪费了。循环队列通过取模运算让队尾绕回数组开头充分利用空间。力扣上有一道“设计循环队列”要求设计一个循环队列支持enQueue、deQueue、Front、Rear、isEmpty、isFull操作。核心点是区分队空和队满的状态通常有两种做法一是额外记录size二是牺牲一个存储单元。class MyCircularQueue { private int[] data; private int head; private int tail; private int size; private int capacity; public MyCircularQueue(int k) { this.capacity k; data new int[k]; head 0; tail 0; size 0; } public boolean enQueue(int value) { if (isFull()) return false; data[tail] value; tail (tail 1) % capacity; size; return true; } public boolean deQueue() { if (isEmpty()) return false; head (head 1) % capacity; size--; return true; } public int Front() { if (isEmpty()) return -1; return data[head]; } public int Rear() { if (isEmpty()) return -1; return data[(tail - 1 capacity) % capacity]; } public boolean isEmpty() { return size 0; } public boolean isFull() { return size capacity; } }这里用size来区分队空和队满是最省心的方案。如果不用size单纯靠head和tail的位置关系判断会有一个“最后一个位置不能用”的尴尬局面而且代码容易出错。在面试中我会更推荐带size的写法思路清晰不容易出bug。需要注意的细节是Rear()方法里(tail - 1 capacity) % capacity这个表达式tail可能是0减1之后变成-1加上capacity再取模才能正确回到数组末尾。5. 我踩过的坑与刷题建议这一节是我个人经验的沉淀。栈与队列的题虽然不难但坑是真不少我把这些坑集中整理一下再给出刷题路线。5.1 常见的错误与调试第一个坑是空栈操作。检查栈是否为空这件事怎么强调都不过分。尤其是while (!stack.isEmpty() ...)这种循环条件里一定把isEmpty放在前面否则栈空时访问栈顶会直接抛异常。第二个坑是单调栈的边界条件。在“接雨水”那道题里弹出top之后要检查栈是否为空如果为空就break因为左边没有更高的柱子了算不出水量。这个检查特别容易漏漏了之后要么数组越界要么计算结果错误。第三个坑是栈与队列混用。写“用队列实现栈”时如果用Deque代替Queue推入元素时用push还是offer要想清楚。Java的Deque提供了两套方法一套是栈语义push/pop/peek一套是队列语义offer/poll/peek混用会造成逻辑混乱。我见过候选人用Deque实现队列入队时用push出队时用poll结果顺序完全不对。第四个坑是元素比较时的包装类型问题。如果栈里存的是Integer而不是int用比较两个Integer会有问题因为超过127的Integer对象用比较的是引用。要么用intValue()要么用equals()。这个问题在“最小栈”等题里很容易出现。调试这类题目时我有个习惯如果代码不对就手动模拟一个简单的例子走一遍流程。比如用栈实现队列输入[1,2,3]手动走一遍push、push、pop、push、pop看输出是不是符合预期。这个方法效率很高因为栈与队列的状态变化比较直观画几个箭头就能找到问题。5.2 推荐的刷题路径关于刷题顺序我建议从易到难分三轮推进。第一轮先把栈和队列的基础API用熟。做“有效的括号”、“用队列实现栈”、“用栈实现队列”这三道题目标是熟悉Deque的push/pop/peek和offer/poll/peek的用法。这三道题做完基础知识就没问题了。第二轮攻单调栈。按这个顺序刷每日温度、下一个更大元素I、下一个更大元素II、柱状图中最大的矩形、接雨水。做完后你会对单调栈的适用场景有很深的理解。这个过程中不要求快每道题都自己推一遍画一下栈的变化过程。第三轮做设计题和综合应用。设计循环队列、设计双端队列、滑动窗口最大值、字符串解码、逆波兰表达式求值、基本计算器。这些题综合考察了栈和队列与其他数据结构的配合。5.3 面试中的现场表现面试和刷题有个很大的不同面试更看重交流过程。我建议你在写代码之前用一两句话跟面试官对齐思路然后再动手。比如“这题我想用辅助栈来记录最小值辅助栈的栈顶存储的是当前状态下栈内元素的最小值这样每次pop之后辅助栈也弹出最小值依然正确。”这段话一说完面试官就知道你理解了题目。还有一点如果你的代码写错了不要慌张。力扣上的运行结果直接告诉你答案错误你可以打日志分析面试中没有运行环境只能靠肉眼排查。这时候最忌讳的是盯着代码发呆。手动模拟一个简单用例一步步写出栈的变化十有八九能找到问题。这个能力在面试中很加分因为它展现的是你调试问题时的系统化思路。最后想说一下栈与队列这个专题真正刷透之后你收获的不只是几十道题目的AC记录而是一种“看到某些结构就联想到栈或队列”的直觉。比如看到成对匹配想到栈看到先来后到想到队列看到需要倒序想到栈看到循环覆盖想到队列。这种直觉会在你后面学树、图、动态规划时反复用到因为它实际上是一种抽象建模的思维方式而这正是这个专题在面试中始终保持高出现率的根本原因。