企业官网建设流程全解析

代码随想录训练营走到第10天，经典的栈与队列part01来了。这两道题——232.用栈实现队列、225.用队列实现栈——几乎是所有算法面试绕不开的"套娃题"，也是训练营打卡里争议最大的一组：有人说"这玩意有啥用"，有人刷完对数据结构彻底开窍。我属于后者。

这篇文章不准备复述题解，而是把我自己刷这两道题的完整思考过程、踩过的坑、以及和后来单调栈/单调队列的联系全部拆开讲一遍。核心目标就一个：让你不仅会写代码，还能在面试官追问"为什么均摊O(1)""为什么用ArrayDeque不用Stack"时对答如流。无论你是训练营学员、准备春招秋招的应届生，还是想补数据结构的在职开发，这篇都适用。

1. 为什么栈和队列要放在一起学

1.1 从数据结构设计角度看：两者是"行为互逆"的

很多人刷题有个坏习惯：看到"用栈实现队列"就急着搜题解，背代码。但题目这么设计，本质上是在考一个很底层的问题——你究竟理不理解"后进先出"和"先进先出"到底意味着什么。

栈是LIFO（Last In First Out），队列是FIFO（First 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中不要用Stack<Integer>，请用Deque<Integer>搭配ArrayDeque实现类。

原因是Stack继承自Vector，是一个"遗留类"，所有方法都加了synchronized锁，性能有额外的同步开销。更重要的是，Java官方文档已经明确建议优先使用Deque来替代Stack。你在一面时如果直接new Stack()，面试官大概率会追问"为什么不用Deque"——如果答不上来，很减分。

正确写法是这样的：

Deque<Integer> 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 232）

3.1 解题思路：两个栈倒腾，输出栈负责"翻面"

用栈实现队列的核心思路，是准备两个栈：一个inStack负责接收所有push进来的元素，另一个outStack专门负责pop和peek。

这里的关键动作叫"倒腾"：当需要pop或peek时，如果outStack是空的，就把inStack里的所有元素逐一弹出，再压入outStack。这一倒腾，元素的顺序就"翻面"了。

我用具体例子带你走一遍：依次push 1、push 2、push 3。此时inStack从栈底到栈顶是1、2、3，outStack为空。接下来执行pop。因为outStack为空，触发倒腾：先把3从inStack弹出压入outStack，再把2压入outStack，最后把1压入outStack。此时outStack从栈底到栈顶变成了3、2、1。栈顶是1，pop返回1。你看，最早进来的1被最先弹出，完美的队列语义。

3.2 完整代码与逐方法拆解

直接给出可AC的代码，语言是Java：

class MyQueue { Deque<Integer> inStack; Deque<Integer> 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 225）

4.1 两种思路总览：辅助缓冲区和自我旋转

用队列实现栈，思路比上一题更灵活。大体上有两种主流解法：

• 方法一：两个队列。一个队列当"主存储"，一个队列当"缓冲区"。每次push时先把新元素放到缓冲区，再把主队列的元素全部搬过去，最后交换两个队列的引用。
• 方法二：一个队列就够了。每次push时先把新元素放到队尾，再把队列前面的所有元素依次弹出并重新入队，让新元素"转"到队首。

两种都能AC，但思路差异很大。两个队列法更直观，适合用来理解"辅助结构"的用途；一个队列法更优雅，代码量少一半，面试时写出来很加分。

4.2 方法一：两个队列，新元素先放缓冲区

先看两个队列的完整代码：

class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } Queue<Integer> 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 1：queue1空。queue2.offer(1)，queue2现在是[1]，交换后queue1=[1]。
• push 2：queue2.offer(2)，queue2先是[2]，然后把queue1的[1] poll出来offer进去，queue2变成[2,1]，交换后queue1=[2,1]。
• push 3：queue2.offer(3)，然后queue1的[2,1]依次搬过去，queue2变成[3,2,1]，交换后queue1=[3,2,1]。
• pop：queue1.poll()返回3。符合栈先出3的预期。

4.3 方法二：一个队列就够了（推荐）

两个队列法虽然直观，但代码里引用交换那一步很容易让人绕晕。一个队列法则完全没有这个问题，理解起来反而更清爽：

class MyStack { Queue<Integer> 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 1：size=0，queue.offer(1)，队列[1]，循环0次，队列还是[1]。
• push 2：size=1，queue.offer(2)，队列[1,2]，循环1次：poll出1再offer进队尾，队列变成[2,1]。
• push 3：size=2，queue.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 两种解法的对比

我个人建议：一刷用两个队列法理解原理，二刷再写一个队列法提升编码熟练度。如果面试只能写一版，务必是一个队列法——又短又不容易出错。

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类实现导致面试被追问

如果你在面试现场写出了Stack<Integer> stack = new Stack<>();，且不说性能问题，单是"遗留类""官方不推荐"这一点，就足够让面试官皱眉头了。

我建议刷题时就养成习惯，一律用Deque<Integer> 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在入队后是n+1，循环次数应该固定为n，一旦动态计算，次数就错乱了。

正确写法是把size先存下来：int size = queue.size();，循环里用的就是这个固定值。这也算是我刷题以来的一个教训：循环次数如果依赖一个会变化的集合状态，一定先存成局部变量。

5.5 常见问题速查表

6. 这两道题刷完后，我的一些体会

我到现在还记得第一次刷232题时的震撼。明明两个数据结构行为完全相反，却能用两个栈严丝合缝地模拟出队列，而且均摊复杂度还维持在O(1)。那一刻我对"数据结构的本质是行为约束"这句话有了很实在的理解。

后面刷单调队列和单调栈的时候，我越来越觉得这种底层的"行为感"特别重要。滑动窗口最大值那道题，如果你不理解队列的FIFO特性，就很难理解为什么窗口滑动时要把队首元素弹出；每日温度那道题，如果你不理解栈的LIFO特性，就很难理解为什么要用"单调递减栈"来保存尚未找到答案的下标。栈和队列不是刷题玩具，它们在JVM栈帧、函数调用回溯、消息队列、阻塞队列里无处不在。

最后分享一个小技巧：这类"互相模拟"的题不要光看题解，一定自己拿纸笔画一遍。把push 1、2、3然后pop的过程画出来，每执行一步就画一下当前栈/队列里的元素状态。画三遍，比抄十遍代码管用得多。后续做单调栈相关题目时，这个画图习惯能救你很多次。