LeetCode 剑指 Offer 09. 用两个栈实现队列
题目描述
题意分析
只用两个栈实现队列，支持
appendTail在队尾插入、deleteHead删除并返回队头；队列为空时删除返回-1。队列要求先进先出，而单个栈只能后进先出。将一个栈的元素逐个弹出并压入另一个空栈，会把这一批元素的顺序反转，最早压入的元素就会来到新栈顶部。需要确定什么时候倒栈，才能在持续插入、删除的过程中始终保持队列顺序，并避免重复搬运。
解法：双栈延迟搬运
核心思路
[!blue]
用
inStack接收新元素，栈顶是最近入队的值；用outStack提供出队元素，栈顶是当前最早入队的值。完整队列顺序可以表示为outStack从栈顶到底，再接上inStack从栈底到顶，因为输出栈中的这一批都早于后来进入输入栈的元素。入队只需压入
inStack。出队时，如果outStack还有元素，就直接弹出它的栈顶。这些旧元素必须先出队，不能把输入栈的新元素压到它们上面，否则新元素会插队。只有
outStack为空时，才把inStack的全部元素逐个弹出并压到输出栈中。输入栈原来的最底元素最后被搬运，恰好落在输出栈顶，因此这一批按照先入先出的顺序重新排列。必须整批搬完，只搬顶部的一部分无法拿到输入栈最早的元素。搬运后若输出栈仍为空，两个栈就都没有元素，返回
-1；否则弹出输出栈顶。出队后不把剩余元素倒回输入栈，它们已经处于正确顺序，继续留在输出栈等待后续删除即可。每个元素只会先进入输入栈，再最多搬到输出栈一次，最后被弹出。虽然某次删除可能搬运很多元素，但每个元素一生只发生固定次数的栈操作，分摊到连续操作上就是常数成本。
解题步骤
appendTail(value)直接把新值压入inStack。deleteHead()先检查outStack；非空时无需搬运。- 若输出栈为空，逐个弹出输入栈的全部元素并压入输出栈。
- 搬运后若输出栈仍为空，返回
-1；否则弹出并返回它的栈顶。
代码实现
class CQueue {
private final Deque<Integer> inStack = new ArrayDeque<>();
private final Deque<Integer> outStack = new ArrayDeque<>();
public CQueue() {}
public void appendTail(int value) {
inStack.push(value);
}
public int deleteHead() {
// 输出栈还有旧元素就不能搬运，清空后再整体反转输入顺序。
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.isEmpty() ? -1 : outStack.pop();
}
}
type CQueue struct {
inStack []int
outStack []int
}
func Constructor() CQueue {
return CQueue{}
}
func (q *CQueue) AppendTail(value int) {
q.inStack = append(q.inStack, value)
}
func (q *CQueue) DeleteHead() int {
if len(q.outStack) == 0 {
// 仅在输出栈已空时整体搬运，反转输入顺序后最早元素位于栈顶。
for len(q.inStack) > 0 {
last := len(q.inStack) - 1
q.outStack = append(q.outStack, q.inStack[last])
q.inStack = q.inStack[:last]
}
}
if len(q.outStack) == 0 {
return -1
}
last := len(q.outStack) - 1
value := q.outStack[last]
q.outStack = q.outStack[:last]
return value
}
复杂度分析
- 时间复杂度：入队为摊还 $O(1)$；出队单次最坏为 $O(n)$，摊还为 $O(1)$。每个元素至多进入、离开两个栈各一次，因此从空队列开始的
m次操作总成本为 $O(m)$，其中也包含底层动态数组扩容的摊还开销。- 空间复杂度：$O(n)$，
n为队列最多同时保存的元素数量，两个栈及其底层存储所需空间均为线性规模。
关键点总结
[!green]
inStack管新元素，outStack管旧元素，职责不能混用。- 只有
outStack为空时才能倒栈，这是正确性条件，也是摊还 $O(1)$ 的来源。- 倒栈必须一次搬完，才能让这一批元素恢复正确的先进先出顺序。
- 复杂度应按元素整个生命周期记账，而不是只看某次搬运循环。
易错点总结
[!yellow]
- 输出栈非空时继续倒栈：新元素会压到旧元素上面，破坏先入先出的顺序。
- 只搬一个元素：输入栈顶是这批中最新的元素，必须整批反转后才能让最早元素来到栈顶。
- 出队后把剩余元素倒回去：没有必要，同一批元素会被反复搬运，增加后续操作开销。
- 输出栈为空就直接返回
-1：输入栈中可能还有元素，应先尝试搬运。- Go 读取栈顶后不缩短切片：只是读到了值，没有真正删除，后续会重复返回同一个元素。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 225. 用队列实现栈 | 简单 | 原题反过来用队列实现栈，本题利用两次倒序恢复FIFO。 |
| 622. 设计循环队列 | 中等 | 同样实现FIFO接口，原题用循环数组直接维护首尾，本题通过两栈批量转移。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！