当前位置：首页 > news >正文

力扣（用队列实现栈）

news 2025/8/26 14:18:45

解析 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(); }
}

（一）代码流程拆解

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