232. 用栈实现队列

题目描述

只用「栈」的操作，实现一个队列(先进先出)。

思路解析

入队都压进「入栈」。出队时如果「出栈」空，就把入栈元素一个个倒进出栈——倒完顺序正好反过来，栈顶就是最先进的。

入队 1, 2, 3：依次入队 1、2、3，都压进「入栈」。此时栈顶是 3，可咱想先出 1。

倒栈 · 弹 3：出队发现出栈空，开始倒：先把入栈顶 3 弹出、压进出栈。

倒栈 · 弹 2：再把 2 弹出压入。最后把 1 也倒过去，顺序就反转了。

出队 · 倒栈：出队时发现出栈空，就把入栈倒过来：先弹 3 压入、再 2、再 1。顺序反转，现在出栈顶正好是最先进的 1。

出队：从出栈弹出 1——这就是队列该先出的元素！实现了「先进先出」。

再出队：只要出栈还有元素，就直接弹（得到 2），不用再倒。

出栈还有元素就直接弹，绝不能再倒（否则顺序乱）。只有出栈空时，才把入栈整个倒过来。

栈倒一次反序，再用另一个栈相当于「倒第二次」，顺序就正回来了。用队列实现栈是同款思路。

参考代码（Python）

1class MyQueue:
2    def __init__(self): self.In, self.Out = [], []
3    def push(self, x): self.In.append(x)        # 入队都进 In
4    def pop(self):
5        self.peek()                             # 确保 Out 有货
6        return self.Out.pop()
7    def peek(self):
8        if not self.Out:                        # 只在 Out 空时倒
9            while self.In: self.Out.append(self.In.pop())
10        return self.Out[-1]

复杂度分析

• 时间复杂度：均摊 O(1) —— 每个元素最多倒一次
• 空间复杂度：O(n) —— 两个栈共存 n 个

套路模板

记住骨架：In 只管收、Out 空了才把 In 整体倒过来、每个元素一生只倒一次（均摊 O(1)）。用队列实现栈是镜像版。

1# 用栈模拟先进先出 / 摊还反序都套
2In, Out = [], []
3def push(x): In.append(x)              # 进都进 In
4def pop():
5    if not Out:                         # 只在 Out 空时才倒
6        while In: Out.append(In.pop())  # 一次倒完 = 反序
7    return Out.pop()

易错点

• ❌ 每次出队都把 Out 倒回 In 再倒过去 → ✅ 只在 Out 为空时才倒一次（反复倒会打乱顺序、也变慢）
• ❌ Out 不空时还去倒 In → ✅ 先判 if not Out（会把新元素插到老元素前面）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。