LeetCode 面试题 03.04. 化栈为队
目录
题目描述
题意分析
要求只用栈这一种容器（只能做压栈、弹栈、看栈顶、判空），实现一个先进先出的队列，支持
push（队尾入队）、pop（队首出队并返回）、peek（看队首）、empty（判空）。
约束里最重要的信号有两条。第一，只允许用栈的标准操作，不能去索引栈的中间元素、不能遍历——这排除了"用一个栈加下标模拟数组"的取巧写法。第二，题目明确提示"你所使用的语言也许不支持栈，但可以用 list 或 deque 模拟，只要仅使用栈的标准操作即可"，并且通常还会追问均摊 $O(1)$ 的实现，这就否掉了"每次操作都把元素倒来倒去"的朴素方案。
边界上要覆盖：题目保证
pop/peek只在队列非空时调用，但内部实现仍要保证两个栈都空时不会误操作；连续push后连续pop；pop到一半又push新元素（这是最容易写错的场景，新元素绝不能插到还没出队的老元素前面）。
解法：栈处理
核心思路
单个栈显然不够：栈的出口在"最后压入"的那一端，而队列要的是"最先压入"的那一端，方向天然相反。所以至少要两个栈，用一次"倒栈"把顺序翻过来。
最朴素的双栈做法是：
push时把stk1全部倒进stk2，压入新元素，再全部倒回stk1，让stk1的栈顶永远是队首。这样pop是 $O(1)$，但每次push都是 $O(n)$，n次入队总代价 $O(n^2)$。瓶颈在于每来一个新元素就要把整个历史翻一遍，而这次翻转的结果马上又被下一次 push 推翻，做的全是无用功。
关键观察是：翻转这件事只需要在真正要出队的时候做，而且一次翻转可以服务后续所有的出队请求。由此把两个栈拆成明确的职责：
stk1是入口栈，只接收新元素，栈顶是队尾（最新的元素）。stk2是出口栈，只吐出元素，栈顶是队首（最老的元素）。
不变量是：把
stk2从栈顶到栈底、再接上stk1从栈底到栈顶，拼起来恰好就是队列从队首到队尾的完整序列。也就是说stk2里存的永远是"比stk1里所有元素都更早入队"的那一批。
维持这个不变量的规则只有一条：只有当
stk2为空时，才把stk1的元素整体倒进stk2。这个条件是整题的命脉。如果stk2还有元素时就去倒，stk1里较新的元素会被压到stk2里较老元素的上面，队首直接变成新元素，先进先出彻底失效。而只在stk2空时倒，stk2里没有任何老元素会被"盖住"，不变量得以保持。
复杂度上，每个元素一生只会经历"进
stk1→ 出stk1→ 进stk2→ 出stk2"这四次操作，总共 $O(1)$ 次栈操作，因此n次操作总代价 $O(n)$，均摊 $O(1)$。单次pop最坏是 $O(n)$（触发一次整体搬运），但这次昂贵的搬运会让紧随其后的n-1次pop都变成 $O(1)$，摊下来是常数——这正是面试官想听的均摊分析。
解题步骤
- 构造函数建立两个空栈
stk1、stk2。不预先做任何搬运，因为空结构下两个栈都空就已经满足不变量。
push(x)只做一件事：压进stk1。刻意不在 push 时搬运，是把开销推迟到真正需要顺序的时刻；这也保证了push是严格的 $O(1)$，不存在最坏情况。
- 抽出一个私有方法
move()：若stk2为空，就把stk1逐个弹出并压入stk2。判断条件用if (stk2 为空)而不是while：stk2非空时必须什么都不做，否则会破坏不变量；stk2为空时一次循环就能把stk1搬空，不需要重复判断。把它抽成方法，是为了让pop和peek共用同一份搬运逻辑，避免两处写法不一致。
pop()先调move()再弹stk2栈顶。调用顺序不能反：必须先保证stk2里有元素（或者说保证队首已经落到stk2顶上），才能去取。
peek()同样先调move()，再读stk2栈顶但不弹出。peek也要搬运，否则在"只 push 过、还没 pop 过"的状态下stk2是空的，直接读会崩溃。
empty()判断两个栈是否都为空。只查其中一个都不对：只 push 没 pop 时stk2空但队列非空；pop 到一半时stk1可能空而stk2还有元素。
以操作序列
push(1) → push(2) → peek() → pop() → push(3) → pop() → pop() → empty()走一遍（栈的表示从左到右为栈底到栈顶）：
push(1)：stk1 = [1]，stk2 = []。push(2)：stk1 = [1, 2]，stk2 = []。
peek()：stk2为空，触发搬运——弹出stk1顶2压入stk2，再弹出1压入stk2，得到stk1 = []，stk2 = [2, 1]。stk2栈顶是1，返回1，正确（1 最先入队）。
pop()：stk2非空，不搬运，弹出栈顶1，stk2 = [2]，返回1。
push(3)：只压stk1，stk1 = [3]，stk2 = [2]。这一步是关键：如果此时错误地把stk1倒进stk2，stk2会变成[2, 3]，栈顶是3，下一次pop就会返回3而不是2，顺序全乱。
pop()：stk2非空（有2），不搬运，弹出2返回，stk2 = []，stk1 = [3]。
pop()：stk2为空，触发搬运，3从stk1移到stk2，stk1 = []，stk2 = [3]；弹出返回3。
empty()：两个栈都空，返回true。整个序列的出队顺序是1, 2, 3，与入队顺序一致。
代码实现
class MyQueue {
private Deque<Integer> stk1 = new ArrayDeque<>();
private Deque<Integer> stk2 = new ArrayDeque<>();
public MyQueue() {
}
public void push(int x) {
stk1.push(x);
}
public int pop() {
move();
return stk2.pop();
}
public int peek() {
move();
return stk2.peek();
}
public boolean empty() {
return stk1.isEmpty() && stk2.isEmpty();
}
private void move() {
if (stk2.isEmpty()) {
while (!stk1.isEmpty()) {
stk2.push(stk1.pop());
}
}
}
}
type MyQueue struct {
stk1 []int
stk2 []int
}
func Constructor() MyQueue {
return MyQueue{[]int{}, []int{}}
}
func (this *MyQueue) Push(x int) {
this.stk1 = append(this.stk1, x)
}
func (this *MyQueue) Pop() int {
this.move()
answer := this.stk2[len(this.stk2)-1]
this.stk2 = this.stk2[:len(this.stk2)-1]
return answer
}
func (this *MyQueue) Peek() int {
this.move()
return this.stk2[len(this.stk2)-1]
}
func (this *MyQueue) Empty() bool {
return len(this.stk1) == 0 && len(this.stk2) == 0
}
func (this *MyQueue) move() {
if len(this.stk2) == 0 {
for len(this.stk1) > 0 {
this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
this.stk1 = this.stk1[:len(this.stk1)-1]
}
}
}
复杂度分析
- 时间复杂度：
push与empty是最坏 $O(1)$；pop与peek是均摊 $O(1)$，最坏单次 $O(n)$。依据是每个元素在整个生命周期里只会被压入/弹出各两次（一次进出stk1，一次进出stk2），m次操作的总栈操作数不超过 $4m$。- 空间复杂度：$O(n)$，
n为队列中当前元素个数。任意时刻每个元素只存在于stk1或stk2之一，两个栈的元素总数恰好等于队列长度，没有重复存储。
关键点总结
- "把开销推迟到必要时刻"是均摊 $O(1)$ 的通用手法。不要在每次写入时维持完美状态，而是让状态临时"欠账"，等到读取真正需要它时再一次性还清。动态数组扩容、并查集路径压缩、本题的倒栈，用的是同一个思想。
- 搬运的触发条件必须是"目标为空"，而不是"源非空"。这是本题唯一会真正做错的地方：条件写松一点，先进先出立刻失效。设计题里凡是有"两个容器之间搬运"的动作，都要先想清楚"什么条件下搬运是安全的"。
- 两个容器各自承担单一方向的职责。入口栈只进、出口栈只出，元素永远单向流动、绝不回头，这条规则让不变量非常好证：出口栈里的元素一定比入口栈里的更早入队。
- 判空要覆盖全部存储位置。状态被拆到多个容器里之后，"整体为空"必须是所有容器都空，只查一个是设计题里的经典漏洞。
- 面试视角：主动做均摊分析。写完代码后面试官几乎必问"
pop最坏是 $O(n)$，你怎么说它是 $O(1)$"。标准答法是聚合分析：每个元素总共只参与 4 次栈操作，因此m次操作总代价 $O(m)$。能主动把这句话说出来，比写对代码更能拉开区分度。
易错点总结
- 错误写法：
move()的条件写成while (!stk1.isEmpty())，即只要入口栈非空就搬 → 用例push(1), pop(), push(2), push(3), pop()：第二次pop时stk2已空没问题，但若在stk2非空时也搬，例如push(1), push(2), pop(), push(3), pop()，stk2里还剩2时把3压上去，stk2变成[2, 3]，下一次pop返回3，正确答案是2。- 错误写法：
move()写成while (stk2.isEmpty()) { while (!stk1.isEmpty()) {...} }→ 用例：两个栈都为空时调用pop()（例如某些追问场景允许对空队列pop并返回 -1）：外层条件永远成立、内层永远不执行，程序陷入死循环直到超时。外层必须是if而不是while。- 错误写法：
push(x)时就把stk1倒进stk2→ 用例push(1), push(2), pop()：push(1)后stk2 = [1]，push(2)时stk2非空却继续倒，stk2 = [1, 2]，pop()返回2，正确答案是1。- 错误写法：
peek()里不调move()，直接return stk2.peek()→ 用例push(1), peek()：stk2是空的，Java 的ArrayDeque.peek()返回null触发拆箱 NPE，Go 里则是切片下标-1越界 panic。- 错误写法：
empty()写成return stk1.isEmpty()→ 用例push(1), pop()之后再push(2), pop()前调用empty()：搬运后stk1为空但stk2里还有元素，empty()错误地返回true，调用方会以为队列已空而提前停止。- 错误写法：
empty()写成return stk1.isEmpty() || stk2.isEmpty()→ 用例push(1)：stk2为空导致返回true，但队列里明明有一个元素。判空必须用&&。- 错误写法：
pop()里写成move(); return stk2.peek();（peek 与 pop 混用） → 用例push(1), pop(), pop()：第一次pop没有真正移除元素，第二次pop又返回同一个1，队列永远清不空。- 错误写法：Java 里用
Deque的add/remove而不是push/pop→ 用例push(1), push(2), pop()：ArrayDeque.add加在尾部、push压在头部，两者混用会让"栈顶"在不同方法里指向不同端，搬运后顺序反而正确、不搬运时又错，表现为间歇性 WA，极难定位。同一个Deque上只能坚持一套语义。- 错误写法：Go 里方法用值接收者
func (this MyQueue) Push(x int)→ 用例push(1), empty()：Push修改的是副本，主对象的stk1始终为空，empty()返回true。凡修改字段的方法必须用指针接收者。- 错误写法：Go 的
move()里搬运时写成this.stk2 = append(this.stk2, this.stk1...)→ 用例push(1), push(2), pop()：这是保序追加，stk2变成[1, 2]，栈顶是2，pop返回2，正确答案是1。搬运的本质是逐个弹出再压入以实现逆序，不能用整体拼接代替。- 错误写法：只用一个栈加一个"队首下标"字段 → 用例
push(1), pop(), push(2), pop()：下标法需要访问栈的中间元素，已经违反了"仅使用栈的标准操作"这一约束；即使实现出来，pop后底部空间无法回收，连续 push/pop 会导致内存无限增长。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 232. 用栈实现队列 | 简单 | 完全同题的 LeetCode 主站版本，常被追问严格 $O(1)$ 的可行性 |
| 225. 用队列实现栈 | 简单 | 反向转换，单队列自旋 n-1 次即可，无法做到均摊 $O(1)$ |
| 剑指 Offer 09. 用两个栈实现队列 | 简单 | 同一模型，但要求空队列 deleteHead 返回 -1，多一层判空 |
| 622. 设计循环队列 | 中等 | 用定长数组加头尾指针取模实现队列，难点在"满"与"空"的区分 |
| 946. 验证栈序列 | 中等 | 不是设计题，而是用一个辅助栈模拟并校验给定的压入弹出序列合法性 |