华为 OD 训练营 · 题解精讲
LeetCode225、用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意： 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例： 输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false]
解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
提示： 1 <= x <= 9 最多调用100 次 push、pop、top 和 empty 每次调用 pop 和 top 都保证栈不为空
题目解析
题目在说什么
这道题要求我们用“队列”这个工具，去模拟“栈”的行为。 队列的特点是“先进先出”，就像排队买奶茶，先来的人先买到。 栈的特点是“后进先出”，就像一摞盘子，最后放上去的盘子最先被拿走。
题目给了我们四个操作：
push(x)：往栈里放一个元素（相当于把盘子摞上去）。pop()：拿走栈顶的元素（拿走最上面的盘子）。top()：看一眼栈顶的元素是什么（但不拿走）。empty()：检查栈里有没有东西。
限制是：只能用队列的标准操作，比如从队尾加元素（offer）、从队头取元素（poll）、看队头元素（peek）、看队列大小（size）、判断是否为空（isEmpty）。
简单说：你手里只有队列，但你要让它表现得像栈一样。
---
思路是怎么来的
想象一个场景： 你面前有两个空盒子，每个盒子只能从一端放东西、从另一端拿东西（这就是队列）。 你想让这两个盒子模拟“后进先出”的效果。
关键问题： 队列是先进先出，栈是后进先出。怎么让队列“倒着”输出？
一个直观的想法： 每次放新东西的时候，把新东西放到一个空盒子里，然后把旧盒子里的所有东西按顺序倒进这个新盒子。这样，新东西就在最前面，旧东西在后面。 下次再取东西时，新东西就会先被拿出来——这不就是“后进先出”吗？
举个例子： 1. 先放一个1：空盒子A放1。 2. 再放一个2：
- 先把2放到空盒子B。
- 然后把盒子A里的1倒进盒子B（1排在2后面）。
- 现在盒子B里是 [2, 1]（2在队头，1在队尾）。
- 然后把盒子B当作主盒子，盒子A清空备用。
3. 取东西时，从主盒子（现在是B）的队头拿，拿到2。 4. 再放一个3：
- 把3放到空盒子A。
- 把主盒子B里的 [2, 1] 倒进盒子A，变成 [3, 2, 1]。
- 现在主盒子是A。
这样，每次新元素都在队头，旧元素都在后面。取的时候永远先取最新的——完美模拟栈。
所以思路的核心就是：用两个队列互相倒腾，保证新元素永远在队头。
---
代码逐步拆解
看参考代码（Java），它用了两个双端队列（Deque），但这里只用了队列的操作（offer、poll、peek），所以其实和普通队列一样。
1. 初始化
Deque<Integer> q1;
Deque<Integer> q2;
public MyStack() {
q1 = new ArrayDeque<>();
q2 = new ArrayDeque<>();
}q1是主队列，永远用来存当前栈里的所有元素（队头是栈顶）。q2是辅助队列，用来临时倒腾。- 初始两个都是空的。
2. push 操作
public void push(int x) {
q2.offer(x); // 1. 新元素先放到空队列 q2
while (!q1.isEmpty()) { // 2. 把 q1 里所有元素搬到 q2
int ele = q1.poll();
q2.offer(ele);
}
q1 = q2; // 3. 把 q2 变成新的主队列
q2 = new ArrayDeque<>(); // 4. 重置 q2 为空，下次用
}一步步拆：
- 第一步：新元素
x直接放到q2里。因为q2此时是空的，所以x就在q2的队头。 - 第二步：把
q1里所有元素（旧元素）按顺序一个一个取出来（从队头取），再一个一个放到q2的队尾。这样，旧元素就全部排在新元素x的后面了。 - 第三步：把
q1指向q2。现在q1就是新的主队列，队头是新元素x，后面跟着所有旧元素。 - 第四步：把
q2重置为一个新的空队列，准备下一次push时使用。
为什么这么做？ 因为我们要保证新元素永远在队头。用两个队列倒腾一次，就能让新元素跑到最前面。