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

简化版

栈是后进先出、队列是先进先出，用队列模拟栈的关键是「让最后进来的元素排到队头」。常用做法：入栈时把新元素放进空队列，再把另一个队列的所有元素依次搬到它后面，这样新元素永远在队头，出队就等于出栈。这种做法入栈 O(n)、出栈 O(1)。其实用一个队列也能实现。

详细版

两个队列法（入栈 O(n)）：始终保持一个队列有数据、一个为空。

class MyStack {
    Queue<Integer> q1 = new LinkedList<>();  // 主队列，队头=栈顶
    Queue<Integer> q2 = new LinkedList<>();  // 辅助空队列

    public void push(int x) {
        q2.offer(x);                         // 新元素先进空队列
        while (!q1.isEmpty()) q2.offer(q1.poll());  // 旧元素全搬到它后面
        Queue<Integer> t = q1; q1 = q2; q2 = t;     // 交换，保持 q1 有数据
    }
    public int pop()  { return q1.poll(); }  // 队头就是最后进的，O(1)
    public int top()  { return q1.peek(); }
    public boolean empty() { return q1.isEmpty(); }
}

每次 push 都重排，使队头永远是「最近入栈」的元素，于是 poll（出队头）就是 pop（出栈顶）。

一个队列法：push 后把它前面的所有元素重新入队到自己后面（旋转 n-1 次），同样让新元素转到队头。省一个队列，逻辑等价。

完整版教学

一、难点：FIFO 怎么装出 LIFO

队列先进先出，栈后进先出，方向相反。要用队列模拟栈，必须想办法在某个操作时把顺序「翻」过来。有两个位置可以付出这个代价：要么让 push 变重（每次入栈就把顺序理成栈序），要么让 pop 变重（出栈时才把最后一个捞出来）。这决定了两种实现风格。

二、方案 A：让 push 变重（推荐）

思路：每次 push 后，立刻把队列调整成「队头 = 栈顶」。做法是新元素先进一个空队列，再把老队列的元素全部接到它屁股后面。这样队列里的顺序就是「后进的在前、先进的在后」，正好是栈的出栈顺序。

push：O(n)（要搬 n-1 个元素）。
pop / top：O(1)（直接出队头）。

适合「读多写少」——出栈频繁、入栈不频繁的场景。

三、方案 B：让 pop 变重

push 就正常入队 O(1)。pop 时，把队列前 n-1 个元素搬到另一个队列，剩下最后一个（就是最后入队的、即栈顶）弹出，然后两队列角色互换。

push：O(1)。
pop / top：O(n)。

适合入栈频繁、出栈少的场景。两种方案是「把 O(n) 的代价放在 push 还是 pop」的取舍。

四、一个队列也能搞定

其实不需要两个队列。push 一个元素后，把它前面的 n-1 个元素依次出队再入队（相当于把队列旋转），新元素就转到了队头：

public void push(int x) {
    q.offer(x);
    for (int i = 1; i < q.size(); i++) q.offer(q.poll()); // 旋转 n-1 次
}

之后 pop 直接出队头。一个队列更省空间，面试说出这个是加分项。

五、对比「两个栈实现队列」

两栈实现队列：出队时把 in 栈整体倒进 out 栈，均摊 O(1)，比较优雅。
两队列实现栈：无论把代价放 push 还是 pop，总有一个操作是 O(n)，做不到均摊 O(1)。

原因是：栈倒进栈能「一次反转」摊平成本；而队列之间搬运无法累积收益，每次都要重排。所以「两队列实现栈」不如「两栈实现队列」高效，这也是面试爱对比着问的点。

六、常见误区与追问

方案	push	pop/top	思路
push 重	O(n)	O(1)	新元素入队后旋转到队头
pop 重	O(1)	O(n)	出栈前把前 n-1 个元素搬走
一个队列	O(n)	O(1)	入队后原地旋转旧元素

记忆钩子：队列天生 FIFO，要模拟栈的 LIFO，就必须让“最新元素”站到队头，或者在弹出时把旧元素都让开。

数字例子：用 push 重方案依次 push 1,2,3。push 1 后队列 [1]；push 2 后先入队成 [1,2]，旋转 1 次变 [2,1]；push 3 后成 [2,1,3]，旋转 2 次变 [3,2,1]。此后 pop 直接出队就是 3，符合栈的后进先出。

误区：两个队列实现栈一定需要两个非空队列长期配合。 push 重方案中也可以只用一个队列旋转，核心是重排顺序。
误区：push 和 pop 都能轻松 O(1)。 只用队列模拟栈时，至少要在 push 或 pop 的一侧付出搬移成本。
误区：top 可以随便取队尾。 普通队列不能 O(1) 访问队尾并删除，应该按所选方案让栈顶位于队头或通过搬移得到。
追问：为什么 push 重方案常被推荐？ 它让 pop/top 都是 O(1)，更符合栈被频繁弹出和查看栈顶的使用习惯。
追问：两个栈实现队列和两个队列实现栈有什么对称性？ 前者用两次反转恢复 FIFO，后者要主动重排让最新元素先出。
追问：如何判断 empty？ 所有用于模拟的队列都为空时，栈才为空。

七、加强记忆

两个队列实现栈：核心是让最后入队的元素排到队头。常用「push 变重」——新元素进空队列，旧元素全搬到它后面，使队头=栈顶，push O(n)、pop O(1)；也可「pop 变重」。一个队列旋转 n-1 次同样可行、更省空间。不同于「两栈实现队列」的均摊 O(1)，两队列实现栈总有一个操作是 O(n)。

简化版

详细版