解析 LeetCode 225. 用队列实现栈：单队列的巧妙运用

一、题目分析

（一）功能需求

实现 MyStack 类，支持栈的四种操作：

• push(int x)：将元素压入栈顶。
• pop()：移除并返回栈顶元素。
• top()：返回栈顶元素。
• empty()：判断栈是否为空。
  需用队列（本题代码用单队列 ）模拟栈的 LIFO 特性。

（二）核心挑战

队列是先进先出（FIFO ）结构，而栈是后入先出（LIFO ）结构，如何通过队列操作模拟栈的“栈顶操作”是关键。

二、算法思想：单队列的反转操作

（一）核心思路

利用单队列，在每次 push 操作时，通过“将新元素入队后，把队列中之前的所有元素依次出队再入队”，让新元素移动到队列头部，从而模拟栈的“栈顶”位置。这样，队列的头部始终对应栈的栈顶，后续 pop、top 操作可直接操作队列头部。

（二）操作逻辑

• push 操作：
  1. 新元素入队。
  2. 将队列中除新元素外的所有元素依次出队并重新入队。这样，新元素会被“移到”队列头部，成为栈顶。
• pop 操作：直接弹出队列头部元素（对应栈顶 ）。
• top 操作：返回队列头部元素（对应栈顶 ）。
• empty 操作：判断队列是否为空。

三、代码实现与详细解析

class MyStack {// 用于模拟栈的队列，选择 LinkedList 实现队列（支持高效的入队、出队）Queue<Integer> queue; public MyStack() {// 初始化队列queue = new LinkedList<>(); }public void push(int x) {// 新元素入队queue.offer(x); int size = 0;// 遍历队列中除新元素外的所有元素（新元素是最后入队的，所以循环 size < 队列长度 - 1 次）while (size < queue.size() - 1) { // 队首元素出队，重新入队到队尾queue.offer(queue.poll()); size++;}}public int pop() {// 队列头部是栈顶，直接弹出return queue.poll(); }public int top() {// 队列头部是栈顶，直接返回return queue.peek(); }public boolean empty() {// 判断队列是否为空return queue.isEmpty(); }
}

（一）代码流程拆解

1. 初始化：queue 用 LinkedList 实现（因 LinkedList 是 Queue 接口的常用实现，支持高效的 offer、poll、peek 操作 ）。
2. push 操作：
   • 新元素 x 入队（queue.offer(x) ）。
   • 循环 size < queue.size() - 1 次（size 初始为 0 ）：每次将队首元素出队（queue.poll() ）并重新入队（queue.offer(...) ）。此操作让新元素前的所有元素“绕到”队列尾部，新元素成为队首，模拟栈顶。
3. pop 操作：调用 queue.poll() 弹出队首元素（即栈顶 ）。
4. top 操作：调用 queue.peek() 返回队首元素（即栈顶 ）。
5. empty 操作：调用 queue.isEmpty() 判断队列是否为空，即栈是否为空。

（二）关键逻辑解析

• push 操作的反转技巧：通过将新元素入队后，把之前的元素循环“出队再入队”，让新元素移动到队首。例如，队列原是 [a, b, c]，入队 d 后变为 [a, b, c, d]，循环 3 次（size < 4 - 1 ）：
  • 第一次：a 出队入队 → [b, c, d, a]
  • 第二次：b 出队入队 → [c, d, a, b]
  • 第三次：c 出队入队 → [d, a, b, c]
    最终新元素 d 成为队首，对应栈顶。
• 单队列的优势：相比双队列实现（一个队列存元素，一个队列辅助 ），单队列通过反转操作，减少了队列数量，代码更简洁，利用队列自身操作完成模拟。
• 时间复杂度分析：push 操作的时间复杂度为 O(n)（n 是当前队列长度，需循环 n - 1 次 ）；pop、top、empty 操作的时间复杂度为 O(1) 。

四、复杂度分析

（一）时间复杂度

• push：$O(n)$ ，n 是当前栈中元素个数（需移动 n - 1 个元素 ）。
• pop：$O(1)$ ，直接弹出队首。
• top：$O(1)$ ，直接访问队首。
• empty：$O(1)$ ，直接判断队列是否为空。

（二）空间复杂度

所有操作仅使用一个队列，空间复杂度为 $O(n)$（n 是栈中元素最大数量 ）。