LeetCode 232. 用栈实现队列
目录
题目描述
题意分析
这是一道设计题：只允许使用栈的标准操作（压栈、弹栈顶、看栈顶、判空、取大小），实现队列的四个接口
push、pop、peek、empty。栈是后进先出，队列是先进先出，两者的出口顺序恰好相反，这就是全部矛盾所在。接口天然分成两个操作族：
push属于「入队族」，只关心把新元素收进来；pop、peek、empty属于「出队族」，都需要知道「最早进来的那个元素」现在在哪。设计的好坏就体现在这两族操作如何分工。约束信号：题目保证
pop和peek时队列非空，所以不必处理空队列取值；操作总数最多 100 次，暴力也能过，但进阶明确要求每个操作的摊还时间为 $O(1)$——允许某一次操作偶尔慢，但 $n$ 次操作的总代价必须是 $O(n)$，这才是本题的真正考点。
解法：双栈延迟搬运
核心思路
使用两个栈：
inStack负责入队，outStack负责出队。只有当outStack为空时，才把inStack的元素全部倒入其中；倒栈会反转顺序，使最早入队的元素位于栈顶。每个元素最多被倒栈一次，因此
pop和peek的摊还时间都是 $O(1)$。
解题步骤
push：将元素压入inStack。pop、peek：先确保outStack非空；需要时将inStack全部倒入。pop弹出outStack栈顶，peek只读取栈顶。empty：两个栈都为空时，队列才为空。
代码实现
class MyQueue {
private final Deque<Integer> inStack = new ArrayDeque<>();
private final Deque<Integer> outStack = new ArrayDeque<>();
public void push(int x) {
inStack.push(x);
}
public int pop() {
move();
return outStack.pop();
}
public int peek() {
move();
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void move() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}
type MyQueue struct {
inStack []int
outStack []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (q *MyQueue) Push(x int) {
q.inStack = append(q.inStack, x)
}
func (q *MyQueue) Pop() int {
q.move()
x := q.outStack[len(q.outStack)-1]
q.outStack = q.outStack[:len(q.outStack)-1]
return x
}
func (q *MyQueue) Peek() int {
q.move()
return q.outStack[len(q.outStack)-1]
}
func (q *MyQueue) Empty() bool {
return len(q.inStack) == 0 && len(q.outStack) == 0
}
func (q *MyQueue) move() {
if len(q.outStack) > 0 {
return
}
for len(q.inStack) > 0 {
i := len(q.inStack) - 1
q.outStack = append(q.outStack, q.inStack[i])
q.inStack = q.inStack[:i]
}
}
复杂度分析
- 时间复杂度：
push、empty为 $O(1)$；pop、peek摊还为 $O(1)$，单次最坏为 $O(n)$。- 空间复杂度：$O(n)$，两个栈合计保存队列中的元素。
关键点总结
- 只在输出栈为空时搬运，不能打乱其中已有元素。
- 倒栈一次即可把后进先出转换为先进先出。
- 摊还 $O(1)$ 的原因是每个元素最多从输入栈移动到输出栈一次。
易错点总结
- 每次出队都来回倒栈，会退化为 $O(n)$ 操作。
- 输出栈非空时仍搬运，会让新元素排到旧元素前面。
empty只检查一个栈，会误判队列状态。peek必须执行与pop相同的搬运，但不能删除队头。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 225. 用队列实现栈 | 简单 | 对偶问题：入队后旋转队列，无法延迟搬运 |
| 面试题 03.04. 化栈为队 | 简单 | 同一双栈模型的另一表述，可直接复用本题实现 |
| 155. 最小栈 | 中等 | 同为栈设计题：辅助栈同步维护前缀最小值 |