LeetCode 225. 用队列实现栈
题目描述
题意分析
用队列实现栈的四个操作：
push压入新元素，pop移除并返回最近压入的元素，top只返回栈顶而不删除，empty判断是否为空。目标是模拟后进先出的访问顺序。队列只允许尾部入队、头部读取或出队，以及查询长度和是否为空，不能直接从队尾弹出。题目允许用列表或双端队列作为底层存储，但使用方式仍要遵守这些限制；进阶要求只用一个队列。题目保证调用
pop、top时栈非空。
解法：单队列旋转
核心思路
[!blue]
让每次操作结束后，队列从头到尾的顺序都对应栈从顶到底的顺序。只要维持这个约定，弹栈就是从队头出队，查看栈顶就是读取队头，判空也直接沿用队列的判空操作。需要调整顺序的只有入栈。
假设入栈前队列有
size个旧元素，且已经按栈顶到栈底排列。新元素只能先放到队尾，但它应该成为新的队头。因此将原有的size个元素依次从队头取出，再放回队尾；当这些旧元素都被移动过，新元素自然来到最前面，旧元素之间的相对顺序没有改变，仍保持原来的栈顺序。必须提前记录旧长度，并恰好轮转这么多次。少转会让旧元素挡在新元素前面，多转会把新元素也移走。空队列压入第一个元素时，旧长度为零，不需要轮转，约定同样成立。
Java 通过队列接口执行这些操作；Go 虽然使用切片，也只读取下标
0、从头缩短切片和向尾部追加。轮转时先保存队头值，再出队并追加，整个过程没有使用随机下标去模拟栈尾操作。
解题步骤
- 构造时准备一个空队列。
push(x)先保存入队前长度size，再把x加入队尾，随后执行size次队头出队并重新入队。pop()从队头移除一个元素并返回它；top()读取同一位置，但不修改队列。empty()根据队列当前是否为空返回结果。
代码实现
class MyStack {
private final Queue<Integer> queue = new ArrayDeque<>();
public MyStack() {}
public void push(int x) {
// 先保存旧元素数量，新元素入队后只把这些旧元素转到它后面。
int size = queue.size();
queue.offer(x);
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
type MyStack struct {
queue []int
}
func Constructor() MyStack {
return MyStack{}
}
func (this *MyStack) Push(x int) {
// 先保存旧元素数量，新元素入队后只把这些旧元素转到它后面。
size := len(this.queue)
this.queue = append(this.queue, x)
for i := 0; i < size; i++ {
front := this.queue[0]
this.queue = this.queue[1:]
this.queue = append(this.queue, front)
}
}
func (this *MyStack) Pop() int {
top := this.queue[0]
this.queue = this.queue[1:]
return top
}
func (this *MyStack) Top() int {
return this.queue[0]
}
func (this *MyStack) Empty() bool {
return len(this.queue) == 0
}
复杂度分析
- 时间复杂度：入栈前有
n个元素时，push为 $O(n)$，需要轮转全部旧元素；pop、top、empty为 $O(1)$。底层动态数组的追加按均摊代价计算。- 空间复杂度：$O(N)$，
N为执行过程中栈内的最大元素数，空间用于队列存储；每次轮转只需常数个临时变量。
关键点总结
[!green]
- 队头始终对应栈顶，把顺序调整集中在
push，其他操作直接复用队列能力。- 新元素前面的旧元素全部转到它后面，既把新值送到队头，又保留旧栈顺序。
- 轮转次数取入队前的长度，不能把新元素也算进去。
- 一个队列就满足进阶要求，无需再添加辅助栈。
易错点总结
[!yellow]
- 入队后才记录长度，会多轮转一次，把新栈顶又送回队尾。
- 轮转过程中每次重新读取长度来决定次数，容易混淆边界；应使用提前保存的旧长度。
top使用出队操作，会在查询时删除元素，改变后续操作结果。- 直接读取或删除队尾，虽然可能得到后进先出的效果，却绕过了题目限定的队列操作。
- Go 中先缩短切片再读取旧队头，会读到另一个元素或越界；需要先保存原值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 232. 用栈实现队列 | 简单 | 互为受限数据结构转换，本题用FIFO模拟LIFO，原题用两个LIFO结构模拟FIFO。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！