LeetCode 225. 用队列实现栈
目录
题目描述
题意分析
题目要求实现一个具备后进先出语义的栈，支持
push、pop、top、empty四个操作，但底层只允许使用队列这一种数据结构。「只能用队列的标准操作」是本题最硬的约束，必须理解到位：可用的动作只有「从队尾入队」「从队头出队」「查看队头」「取得队列大小」「判断是否为空」。不允许按下标随机访问队列中间的元素，不允许反向遍历，也不允许调用语言库里那些队列本不该有的方法。用 Java 的
LinkedList时尤其容易越界，因为它同时暴露了getLast、get(i)这类栈或列表才有的接口，一旦用上就等于绕过了考点。Go 用切片模拟队列时同理，只能在尾部append、在头部切掉，不能随手索引中间位置。冲突点很清楚：队列是先进先出，栈是后进先出，两者的取出顺序恰好相反。要用前者模拟后者，必然要在某个操作里付出额外代价，把顺序「掰」过来。设计的自由度就在于把这份代价放在
push还是pop上。约束方面，调用次数不超过 100，元素个数很小，所以线性代价的单次操作完全可以接受，不必追求摊还 $O(1)$ 的花哨做法。
边界情况：题目保证
pop和top只会在栈非空时被调用，所以不必处理空栈取值；但empty会在任意时刻被调用，需要正确返回。另外要注意只有一个元素时的行为，此时push后无需任何调整。
解法：单队列旋转
核心思路
问题关键： 队列只能先进先出，栈却要求后进先出。与其在每次
pop时临时寻找最后入队的元素，不如在push时就调整顺序，让队头始终是栈顶。为什么选择单队列： 新元素入队后，把它前面的旧元素依次移到队尾，就能让新元素来到队头。这样只需要一个队列，
pop、top都可直接使用队列原生操作；双队列也能完成同样的调整，但复杂度相同、状态更多。不变量： 每次操作结束后，队列从队头到队尾的顺序，等于栈从栈顶到栈底的顺序。
正确性： 假设入栈前队列为
[s1, s2, ..., sk]，其中s1是栈顶。新元素x入队后为[s1, ..., sk, x]，再把前k个旧元素移到队尾，得到[x, s1, ..., sk]，恰好对应新的栈顺序。之后pop删除队头、top读取队头，都不会破坏剩余元素的顺序，因此不变量始终成立。
解题步骤
push(x)时，先记录入队前的长度size。- 把
x放入队尾，再执行size次“队头出队并重新入队”，让x转到队头。pop()直接弹出队头，top()直接读取队头，empty()直接判断队列是否为空。口述示例： 依次压入 1、2。压入 1 后队列为
[1]；压入 2 后先得到[1, 2]，轮转一次变成[2, 1]，所以top和pop都先得到 2。边界与反例： 第一个元素入队前长度为 0，不需要轮转；题目保证不会对空栈调用
pop和top。长度必须在入队前记录，如果入队后再取长度，会把新元素也轮转一次，push(1), push(2)后又错误地回到[1, 2]。
代码实现
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
}
复杂度分析
push的时间复杂度为 $O(n)$，需要轮转原有的 $n$ 个元素；pop、top、empty均为 $O(1)$。- 存储全部元素需要 $O(n)$ 空间，轮转过程只使用常数个辅助变量。
关键点总结
- 先确定“队头就是栈顶”的不变量，再实现四个接口，指针方向就不会混乱。
- 本质是把调整成本前置到
push，换取查询和弹出为 $O(1)$。- 轮转次数必须等于入队前的元素个数。
- 若面试官要求
push为 $O(1)$，可以把轮转推迟到pop，但此时pop会变成 $O(n)$，只是成本位置不同。
易错点总结
- 入队后才记录长度：会多轮转一次，新元素无法停在队头。
- 少转或多转一轮：都会破坏“队头到队尾等于栈顶到栈底”的顺序。
top误用出队操作：第一次查询会悄悄删除栈顶，连续两次top即可暴露问题。- 使用下标或
LinkedList.getLast()取元素：结果可能正确，但违反了只能使用队列标准操作的限制。- Go 中移动队头前没有先保存其值：切片缩短后再读取可能越界或读错元素。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 232. 用栈实现队列 | 简单 | 反方向模拟，双栈倒腾可做到摊还 $O(1)$，与本题的全量轮转形成对照 |
| 面试题 03.04. 化栈为队 | 简单 | 232 的同题异构，适合用来检验摊还分析是否真的讲得清 |
| 剑指 Offer 09. 用两个栈实现队列 | 简单 | 同为双栈模拟队列，额外要求队空时返回 -1 的边界处理 |
| 155. 最小栈 | 中等 | 不做结构互转，而是给栈附加 $O(1)$ 查询最小值的辅助信息 |
| 622. 设计循环队列 | 中等 | 用定长数组加双指针从零造队列，重点是取模与空满判别 |
| 946. 验证栈序列 | 中等 | 不设计结构，而是用栈模拟压入弹出过程校验序列合法性 |