代码随想录训练营走到第10天经典的栈与队列part01来了。这两道题——232.用栈实现队列、225.用队列实现栈——几乎是所有算法面试绕不开的套娃题也是训练营打卡里争议最大的一组有人说这玩意有啥用有人刷完对数据结构彻底开窍。我属于后者。这篇文章不准备复述题解而是把我自己刷这两道题的完整思考过程、踩过的坑、以及和后来单调栈/单调队列的联系全部拆开讲一遍。核心目标就一个让你不仅会写代码还能在面试官追问为什么均摊O(1)为什么用ArrayDeque不用Stack时对答如流。无论你是训练营学员、准备春招秋招的应届生还是想补数据结构的在职开发这篇都适用。1. 为什么栈和队列要放在一起学1.1 从数据结构设计角度看两者是行为互逆的很多人刷题有个坏习惯看到用栈实现队列就急着搜题解背代码。但题目这么设计本质上是在考一个很底层的问题——你究竟理不理解后进先出和先进先出到底意味着什么。栈是LIFOLast In First Out队列是FIFOFirst In First Out在元素进出顺序上恰好相反。题目故意让你用一个实现另一个就是逼你抛开语言已经封装好的数据类型自己来控制元素的排列顺序和弹出时机。这有点像给你一摞盘子让你按后放先拿的方式摆放最后却要让别人按先放先拿的顺序取走——唯一的办法就是中间多一步倒腾。我在刷完这两题后的一个感受是数据结构不是存储容器而是行为约束。同样是线性表栈只允许从一端操作队列只允许一端进另一端出。这种约束不是限制反而是我们解题时能利用的最大规律。1.2 从面试考察角度看这是在考抽象拆解能力面试官问这道题真不是想让你表演我会调API。他们想看到的是当你不能直接使用某个数据结构时能不能用另外的基础结构模拟出目标行为。这个能力在实际工程里非常实用。比如你手头只有一个数组却要模拟一个队列比如你在设计缓存淘汰策略时需要自己维护访问顺序再比如JVM的栈帧、函数调用中的回溯全靠栈的后进先出语义在支撑。能把行为需求翻译成底层操作才是这类题目真正要训练的东西。我当时在训练营群里看到不少同学说这题太偏了但后来做到滑动窗口最大值、每日温度、接雨水时他们才反应过来——没把栈和队列的行为吃透后面寸步难行。1.3 从训练营刷题节奏看这是后续所有栈队列进阶题的地基代码随想录的刷题顺序不是随便排的。第10天安排栈与队列基础后面马上会碰到单调队列、单调栈这类的进阶题型。单调队列比如滑动窗口最大值本质上就是在普通队列的基础上加了一个维护单调性的操作——每次入队前把队尾不满足条件的元素弹掉。如果你连普通队列的offer/poll都搞不清那一步根本走不下去。单调栈也是同理每日温度那道题就是利用栈的后进先出特性配合保持单调递减来跳过无效比较。换句话说今天的这两道题不练透后面的题你会刷得极其痛苦。这也是为什么训练营一定要把栈和队列单独拎出来做一part01从最基础的行为模拟开始。2. 动手之前先搞清楚栈和队列底层到底是什么2.1 栈一摞盘子的后进先出栈的操作其实就三个核心动作push入栈、pop出栈并删除栈顶、peek查看栈顶但不删除。它的行为可以类比成一摞盘子——你总是把新盘子放到最上面拿盘子的时候也是先拿最上面的那个。我用一个最简单的例子帮助记忆依次push 1、push 2、push 3之后栈内从栈底到栈顶的顺序是1、2、3。此时执行pop返回的是3栈内变成1、2。只要记住我们永远只碰栈顶这一个位置栈的所有题目就都能推理出来。2.2 队列食堂排队打饭的先进先出队列的核心动作是offer入队、poll出队并删除队首、peek查看队首。它的行为就是食堂排队打饭先到的人先打饭走人后来的人排在队尾。同样用例子说明依次offer 1、offer 2、offer 3之后队列从队首到队尾的顺序是1、2、3。此时执行poll返回的是1队列变成2、3。队列的操作永远只发生在队首出、队尾进这两端中间的元素顺序是完全稳定的。2.3 Java里的细节Stack类已经过时请用ArrayDeque这是我在训练营里反复强调的一个点也直接甩开很多人Java中不要用StackInteger请用DequeInteger搭配ArrayDeque实现类。原因是Stack继承自Vector是一个遗留类所有方法都加了synchronized锁性能有额外的同步开销。更重要的是Java官方文档已经明确建议优先使用Deque来替代Stack。你在一面时如果直接new Stack()面试官大概率会追问为什么不用Deque——如果答不上来很减分。正确写法是这样的DequeInteger stack new ArrayDeque(); // 入栈 stack.push(1); // 出栈 int top stack.pop(); // 查看栈顶 int peek stack.peek();这里再补充一个选型细节ArrayDeque底层是循环数组通过头尾指针移动来实现双端操作访问快、缓存友好、不需要为每个元素创建额外节点。LinkedList虽然也实现了Deque接口但它是双向链表结构每个元素都要维护前后指针内存占用更大局部性更差。所以做题时优先ArrayDeque除非有明确的插入删除需求才考虑LinkedList。还有一个冷知识ArrayDeque不允许存null元素而LinkedList允许。刷题时基本用不到null但如果做工程封装请注意这个区别。3. 核心实操一用栈实现队列LeetCode 2323.1 解题思路两个栈倒腾输出栈负责翻面用栈实现队列的核心思路是准备两个栈一个inStack负责接收所有push进来的元素另一个outStack专门负责pop和peek。这里的关键动作叫倒腾当需要pop或peek时如果outStack是空的就把inStack里的所有元素逐一弹出再压入outStack。这一倒腾元素的顺序就翻面了。我用具体例子带你走一遍依次push 1、push 2、push 3。此时inStack从栈底到栈顶是1、2、3outStack为空。接下来执行pop。因为outStack为空触发倒腾先把3从inStack弹出压入outStack再把2压入outStack最后把1压入outStack。此时outStack从栈底到栈顶变成了3、2、1。栈顶是1pop返回1。你看最早进来的1被最先弹出完美的队列语义。3.2 完整代码与逐方法拆解直接给出可AC的代码语言是Javaclass MyQueue { DequeInteger inStack; 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(); } }逐个方法拆解一下push(int x)直接压入inStack不做任何其他操作。入队本来就是先后进来的排在后面栈后进先出也不影响因为后面还有倒腾这一步兜底。pop()先检查outStack是否为空。为空就把inStack全部倒腾过来再弹出outStack的栈顶。不为空就直接弹出因为outStack的栈顶已经是队首了。peek()逻辑和pop几乎一样区别只在最后用peek而不是pop也就是只看不动。empty()注意这里必须两个栈都为空才算空。只要inStack或outStack任何一个还有元素队列里就还有数据。这个判断容易漏后面避坑环节会详细说。3.3 关键优化peek()和pop()的代码复用很多人的第一版代码会把倒腾逻辑复制粘贴两遍——一遍写在pop里一遍写在peek里。功能没问题但代码丑而且面试官一眼就能看出你没有复用意识。我当时写的第二版做了个小优化提取了一个私有方法private void dumpInToOut() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } } public int pop() { dumpInToOut(); return outStack.pop(); } public int peek() { dumpInToOut(); return outStack.peek(); }这样pop和peek的主体逻辑就只剩一行调用非常干净。还有一个思路是用peek()去实现pop()——先peek拿到队首元素然后弹出outStack栈顶。但不推荐因为peek里已经做了倒腾pop再调一次等于多一层间接语义上绕。3.4 复杂度分析为什么是均摊O(1)这是面试官最爱追问的点。pop操作看起来最坏情况下要倒腾n个元素应该是O(n)为什么说它是O(1)答案是每个元素最多只会被倒腾一次。某个元素从push进来到pop离开它经历的路径是压入inStack一次从inStack弹出一次压入outStack一次从outStack弹出一次。总共四次操作平摊到它被弹出的那一次pop上就是常数级别。换句话说虽然某一次pop可能触发O(n)的倒腾但这一次倒腾把inStack里的n个元素全部准备好了后续n次pop都是O(1)。所以从整体来看n次push加n次pop的总复杂度是O(n)均摊到每次操作就是O(1)。这个均摊分析的角度和动态数组扩容时的复杂度分析是同一个套路。4. 核心实操二用队列实现栈LeetCode 2254.1 两种思路总览辅助缓冲区和自我旋转用队列实现栈思路比上一题更灵活。大体上有两种主流解法方法一两个队列。一个队列当主存储一个队列当缓冲区。每次push时先把新元素放到缓冲区再把主队列的元素全部搬过去最后交换两个队列的引用。方法二一个队列就够了。每次push时先把新元素放到队尾再把队列前面的所有元素依次弹出并重新入队让新元素转到队首。两种都能AC但思路差异很大。两个队列法更直观适合用来理解辅助结构的用途一个队列法更优雅代码量少一半面试时写出来很加分。4.2 方法一两个队列新元素先放缓冲区先看两个队列的完整代码class MyStack { QueueInteger queue1; QueueInteger queue2; public MyStack() { queue1 new LinkedList(); queue2 new LinkedList(); } public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } QueueInteger temp queue1; queue1 queue2; queue2 temp; } public int pop() { return queue1.poll(); } public int top() { return queue1.peek(); } public boolean empty() { return queue1.isEmpty(); } }这段代码的核心思路是把queue2当成一个临时缓冲区。每次push时新元素先进queue2然后把queue1里的所有元素依次弹出并塞进queue2。这一步做完queue2里的顺序是原queue1的所有元素顺序不变最后是刚进来的新元素x。此时新元素在队尾。但问题来了栈要求后进先出新元素应该在队首才对。怎么办答案在最后三行交换queue1和queue2的引用。交换之后queue1变成了刚才那个新元素在队尾的队列而pop是从队首弹。如果直接弹弹出的还是最老的元素那就错了。所以这个写法其实有一个关键前提每次push之后queue1中所有元素的顺序必须保证最新的在队首。怎么做到看push的顺序queue2先接收x再把queue1的全部元素接在x后面。这样queue2里x是在最前面队首老元素都在它后面。交换引用后queue1就是x在队首的队列。pop时从队首弹先弹x完美实现栈的LIFO语义。我画个具体例子连续push 1、2、3。push 1queue1空。queue2.offer(1)queue2现在是[1]交换后queue1[1]。push 2queue2.offer(2)queue2先是[2]然后把queue1的[1] poll出来offer进去queue2变成[2,1]交换后queue1[2,1]。push 3queue2.offer(3)然后queue1的[2,1]依次搬过去queue2变成[3,2,1]交换后queue1[3,2,1]。popqueue1.poll()返回3。符合栈先出3的预期。4.3 方法二一个队列就够了推荐两个队列法虽然直观但代码里引用交换那一步很容易让人绕晕。一个队列法则完全没有这个问题理解起来反而更清爽class MyStack { QueueInteger queue; public MyStack() { queue new LinkedList(); } public void push(int x) { int size queue.size(); queue.offer(x); for (int i 0; i size; i) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } public int top() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); } }这段代码的精髓在push方法先记录当前队列长度size然后将新元素x入队最后循环size次把队首元素依次弹出并重新放到队尾。这一操作相当于让队列转了一圈把刚入队的x顶到了队首。我用例子验证连续push 1、2、3。push 1size0queue.offer(1)队列[1]循环0次队列还是[1]。push 2size1queue.offer(2)队列[1,2]循环1次poll出1再offer进队尾队列变成[2,1]。push 3size2queue.offer(3)队列[2,1,3]循环2次poll出2再offer到队尾队列[1,3,2]poll出1再offer到队尾队列[3,2,1]。pop返回3。和两个队列法结果一致。这个方法每次push的时间复杂度是O(n)但胜在短小精悍而且不需要额外的第二个队列。我实测下来它也是LeetCode上跑得最快的一版因为省去了频繁交换引用的开销。4.4 两种解法的对比维度两个队列法一个队列法push时间复杂度O(n)O(n)pop时间复杂度O(1)O(1)空间复杂度O(n)需要两个队列O(n)只用一个队列代码量较短但含引用交换逻辑极短核心只有3行理解难度中swap引用是难点低旋转思路更直观面试加分点展示借用辅助结构的思维展示对队列操作的深刻理解我个人建议一刷用两个队列法理解原理二刷再写一个队列法提升编码熟练度。如果面试只能写一版务必是一个队列法——又短又不容易出错。5. 避坑指南这两道题最容易踩的四个坑5.1 坑一peek()和pop()漏判outStack是否为空这个坑几乎每个训练营学员都会踩一次。232题里如果你每次pop前都把inStack重新倒腾一遍而不是只在outStack为空时倒腾元素的顺序就会错乱。我见过一个很典型的错误写法public int pop() { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } return outStack.pop(); }这种写法第一次pop没问题但第二次pop时inStack是空的不会进入循环outStack.pop()返回的仍然是当前outStack的栈顶看似也对了。真正的隐患在于如果中间穿插了新的push操作比如push 4之后再次pop这段代码会把inStack里的4倒腾到outStack压在3、2、1上面结果pop出来的是4。这就不符合队列的FIFO了。所以判断条件必须是if (outStack.isEmpty())而不是无脑倒腾。这个if是整个算法的灵魂少它不可。5.2 坑二用Stack类实现导致面试被追问如果你在面试现场写出了StackInteger stack new Stack();且不说性能问题单是遗留类官方不推荐这一点就足够让面试官皱眉头了。我建议刷题时就养成习惯一律用DequeInteger stack new ArrayDeque();。这个习惯看起来不起眼但在面试中是一个很自然的亮点说明你对Java集合框架的演进是了解的。5.3 坑三两个队列法里pop之后忘了维持队首语义225题的两个队列解法中有一个不变量必须时刻维护队列queue1的队首永远应该是栈顶元素。这个不变量靠每次push后的搬移和交换来保证。如果你push之后忘了交换引用或者pop之后直接把queue2当成主队列用了那么下一次push时的搬移逻辑就全乱了。我建议在写代码时把push里的三步注释出来入缓冲区、搬主队列、交换引用。写清楚之后就不容易漏。5.4 坑四一个队列法里size没有先存下来这是我在训练营打卡群看到的最常见报错原因。错误的写法长这样public void push(int x) { queue.offer(x); for (int i 0; i queue.size() - 1; i) { queue.offer(queue.poll()); } }问题在于循环条件里的queue.size()是动态变化的。每执行一次queue.offer(queue.poll())队首元素被移到队尾队列长度本身不变——但如果你一开始没存size而是直接写循环for循环的条件表达式会随着队列状态一直重新计算。更要命的是size在入队后是n1循环次数应该固定为n一旦动态计算次数就错乱了。正确写法是把size先存下来int size queue.size();循环里用的就是这个固定值。这也算是我刷题以来的一个教训循环次数如果依赖一个会变化的集合状态一定先存成局部变量。5.5 常见问题速查表问题原因解决方案232题pop返回顺序错乱没有判断outStack是否为空就倒腾只在outStack为空时执行inStack到outStack的搬移232题empty()判断错误只看inStack是否为空必须同时检查inStack和outStackJava报ConcurrentModificationException用for-each遍历Stack/ArrayDeque时改动结构改用while循环配合isEmpty判断225题push后队首不是最新元素忘了交换两个队列的引用在push末尾交换queue1和queue2225题一个队列法push后顺序全乱循环次数用了动态的queue.size()先int size queue.size()存下来不知道pop和peek的区别概念混淆pop删除并返回peek只返回不删除6. 这两道题刷完后我的一些体会我到现在还记得第一次刷232题时的震撼。明明两个数据结构行为完全相反却能用两个栈严丝合缝地模拟出队列而且均摊复杂度还维持在O(1)。那一刻我对数据结构的本质是行为约束这句话有了很实在的理解。后面刷单调队列和单调栈的时候我越来越觉得这种底层的行为感特别重要。滑动窗口最大值那道题如果你不理解队列的FIFO特性就很难理解为什么窗口滑动时要把队首元素弹出每日温度那道题如果你不理解栈的LIFO特性就很难理解为什么要用单调递减栈来保存尚未找到答案的下标。栈和队列不是刷题玩具它们在JVM栈帧、函数调用回溯、消息队列、阻塞队列里无处不在。最后分享一个小技巧这类互相模拟的题不要光看题解一定自己拿纸笔画一遍。把push 1、2、3然后pop的过程画出来每执行一步就画一下当前栈/队列里的元素状态。画三遍比抄十遍代码管用得多。后续做单调栈相关题目时这个画图习惯能救你很多次。