如何用两个栈实现一个队列？

简化版

用两个栈：入栈 in 负责入队，出栈 out 负责出队。入队就 push 到 in；出队时如果 out 空，就把 in 里的元素全部倒进 out（顺序正好反过来，变成先进先出），再从 out 弹出。每个元素最多被搬一次，出队均摊 O(1)。

详细版

class MyQueue {
    Deque<Integer> in = new ArrayDeque<>();
    Deque<Integer> out = new ArrayDeque<>();

    public void push(int x) { in.push(x); }   // 入队：压入 in

    public int pop() {                         // 出队
        transfer();
        return out.pop();
    }
    public int peek() {                        // 看队头
        transfer();
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }

    private void transfer() {                  // 只在 out 空时倒一次
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
    }
}

关键就一句：只有当 out 空时才把 in 倒过来。绝不能每次出队都倒，否则顺序会乱、复杂度也变差。

完整版教学

一、为什么「倒一次栈」就变成了 FIFO

栈是后进先出。假设依次入队 1、2、3，它们在 in 里从栈底到栈顶是 1,2,3（栈顶是 3）。现在把 in 全部 pop 再 push 到 out：弹出顺序是 3,2,1，压进 out 后，out 的栈顶变成了 1。于是从 out 弹出的顺序是 1,2,3——正好是入队顺序，实现了先进先出。一次「反转」把 LIFO 变成了 FIFO。

二、为什么必须等 `out` 空了再倒

如果 out 里还有元素（比如上一批倒过来还没出完），此时又把 in 的新元素倒进去，就会把「新来的」压在「老的」上面，破坏先进先出。所以规则是：out 非空时直接从 out 出；只有 out 空了，才一次性把 in 全倒过来。这样能保证 out 里始终是「比 in 里更早入队」的元素，顺序不乱。

三、复杂度：均摊 O(1)

单看某次出队，如果触发了搬运，是 O(n)。但每个元素一生只会被搬一次（从 in 到 out），之后就一直待在 out 直到被弹出。把总搬运成本摊到每个元素上，入队 O(1)、出队均摊 O(1)。这是「均摊分析」的经典例子——不能只看最坏单次，要看长期平均。

四、对称问题：两个队列实现栈

反过来「两个队列实现栈」也常一起问。一种做法是：入栈时把新元素放进空队列，再把另一个队列的所有元素依次搬过来接在它后面，使新元素永远在队头——这样出队列就等于出栈（后进先出）。它的入栈是 O(n)，不如「两栈实现队列」优雅，但思路值得知道。

五、面试怎么答才完整

说清两个栈的分工（in 入、out 出）；
强调「out 空才倒」这个关键条件；
主动给出均摊 O(1) 的复杂度分析（体现你懂均摊）；
有余力提一句对称的「两队列实现栈」。

六、常见误区与追问

操作	`in` 栈	`out` 栈	说明
enqueue(x)	push x	不动	新元素先进入输入栈
dequeue() 且 out 非空	不动	pop	直接弹出最早元素
dequeue() 且 out 为空	全部倒入 out	pop	只在 out 空时倒

易错点：两个栈实现队列的关键是“批量倒一次”。不能每次出队都来回倒，否则均摊 O(1) 会被写成 O(n)。

数字例子：依次入队 1,2,3 后，in=[1,2,3]、out=[]。第一次出队时把 in 全部倒到 out，得到 out=[3,2,1]，弹出 1；第二次出队直接弹 2；第三次弹 3。三个元素各自最多经历一次进入 in、一次从 in 到 out、一次从 out 弹出，总成本线性，均摊到每次操作就是 O(1)。

误区：每次 dequeue 都要把 in 倒到 out。 只有 out 为空时才倒，否则会破坏已有顺序并增加成本。
误区：两个栈实现队列最坏时间也是 O(1)。 单次倒栈可能是 O(n)，但一系列操作的均摊复杂度是 O(1)。
误区：peek 可以直接看 in 的栈底。 栈不支持 O(1) 看栈底；peek 应优先看 out，out 空时再倒栈。
追问：为什么倒栈后变成 FIFO？ in 的栈顶是最新元素，倒入 out 后顺序反转，最早元素来到 out 栈顶。
追问：empty 怎么判断？ 两个栈都为空才是真空队列。
追问：和两个队列实现栈的核心差别是什么？ 队列实现栈要把新元素或旧元素重新排队，让最新元素先出；这里是用两次 LIFO 抵消成 FIFO。

七、加强记忆

两个栈实现队列：in 管入队、out 管出队；out 空时把 in 整体倒过来（一次反转把 LIFO 变 FIFO），out 非空就直接弹。每个元素只搬一次，出队均摊 O(1)。

简化版

详细版