LeetCode232、用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。 队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x)将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty()如果队列为空，返回 True ；否则，返回 False

题目解析

题目在说什么

这道题想让我们用两个栈（Stack）来模拟一个队列（Queue）。栈和队列的区别在于：

• 栈：后进先出（LIFO），就像一叠盘子，你只能从最上面拿盘子。
• 队列：先进先出（FIFO），就像排队买奶茶，先到的人先买到。

题目要求我们实现队列的四个基本操作： 1. push(x)：把元素 x 放到队列的末尾（相当于排队时站到队伍最后）。 2. pop()：移除并返回队列开头的元素（相当于队伍最前面的人离开）。 3. peek()：只返回队列开头的元素，但不移除它（看一眼谁在第一个）。 4. empty()：检查队列是否为空（队伍里有没有人）。

但限制是：我们只能用栈来实现，不能直接用队列。所以需要想办法用两个栈“合作”来模拟队列的行为。

---

思路是怎么来的

生活比喻：两个桶倒来倒去

想象你有两个桶：

• 桶A（我们叫它 stackIn）：专门用来放新东西。
• 桶B（我们叫它 stackOut）：专门用来取东西。

栈的特点是“后进先出”，就像你往桶里放东西，只能从最上面拿出来。 队列的特点是“先进先出”，就像排队，先到的人先出来。

怎么用两个桶模拟排队呢？

• 当有人加入队伍（push）时，我们先把他们放进桶A。桶A里的顺序是反的：最后放的人在最上面。
• 当需要让队伍最前面的人离开（pop）时，我们不能直接从桶A拿，因为桶A最上面是最后进来的人。
• 解决办法：把桶A里的所有东西倒进桶B。倒的时候，桶A最上面的（最后进来的）会先倒进桶B，所以桶B最上面的反而是最早进来的。这样桶B就变成了“先进先出”的顺序。
• 之后，从桶B的顶部取元素，就相当于队列的 pop 或 peek。

关键点：什么时候倒？

• 如果桶B里还有东西（说明之前倒进去的还没取完），那就直接从桶B取，因为桶B顶部就是最早进来的。
• 如果桶B空了，但桶A还有新东西，那就再把桶A的所有东西倒进桶B，再取。

这样，每次取元素时，桶B里总是按“先进先出”的顺序排列的。

---

代码逐步拆解

1. 定义两个栈

Stack<Integer> stackIn;   // 负责“入队”的栈
Stack<Integer> stackOut;  // 负责“出队”的栈

• stackIn：专门用来接收新元素（push操作）。
• stackOut：专门用来提供出队元素（pop和peek操作）。

2. 初始化（构造函数）

public MyQueue() {
    stackIn = new Stack<>();
    stackOut = new Stack<>();
}

• 创建两个空栈，准备使用。

3. 入队操作：push(int x)

public void push(int x) {
    stackIn.push(x);
}

• 直接把元素 x 压入 stackIn。
• 为什么这么简单？因为入队就是“放到队伍末尾”，而 stackIn 只是暂时存放，顺序不重要，反正后面会倒到 stackOut 里调整顺序。

4. 出队操作：pop()

public int pop() {
    if (stackOut.isEmpty()) {
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
    return stackOut.pop();
}

• 第一步：检查 stackOut 是否为空。
• 如果 stackOut 不为空，说明里面已经有按正确顺序排好的元素，直接取顶部即可。
• 如果 stackOut 为空，就需要把 stackIn 里的所有元素“倒”进 stackOut。
• 倒的过程：用 while 循环，每次从 stackIn 弹出栈顶元素（stackIn.pop()），再压入 stackOut（stackOut.push(...)）。
• 注意：stackIn.pop() 会移除并返回栈顶元素，所以循环结束后 stackIn 变为空。
• 倒完后，stackOut 的顶部就是最早进入 stackIn 的元素（因为后进的元素被压在了 stackOut 底部）。
• 第二步：从 stackOut 弹出并返回顶部元素，这就是队列的“队首”元素。

5. 查看队首元素：peek()

public int peek() {
    if (stackOut.isEmpty()) {
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
    return stackOut.peek();
}

• 逻辑和 pop() 几乎一样，只是最后一步用 peek() 而不是 pop()。
• peek() 只返回栈顶元素，但不删除它，所以队列的队首元素还在 stackOut 里，下次 pop() 还能取到。