LeetCode 剑指 Offer 09. 用两个栈实现队列

约 5 分钟
文章信息 19 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 旷视 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
栈 设计 队列
目录

题目描述

✅ 剑指 Offer 09. 用两个栈实现队列

image-20241107204404315

题意分析

要求设计一个类 CQueue，只借助两个栈实现队列的两个操作：appendTail(value) 在队尾插入元素，deleteHead() 删除并返回队首元素。

这是一道设计题，难点不在写代码而在选择「什么时候做搬运」。题面给出的两个信号必须抓住：

  • 性能要求是摊还复杂度：题目对操作次数的规模给到 $10^4$ 量级，并期望 appendTail 与 deleteHead 的摊还时间为 $O(1)$。注意是摊还而不是最坏——这句话本身就在暗示允许存在个别昂贵的操作，只要它们的代价能被分摊到大量廉价操作上。如果按最坏 $O(1)$ 去想，反而会觉得这题无解。
  • 空队列的返回值有明确约定：当队列中没有任何元素时，deleteHead 必须返回 -1，而不是抛异常、也不是返回 0。这个约定要落到代码里成为一个显式分支。

边界：删除操作可能在任何时刻到来，包括一次插入都没有做过的时候，以及把所有元素都删完之后又继续删；插入和删除可以任意交错，不能假设「先全插入再全删除」这种理想序列。

解法：双栈延迟搬运

核心思路

问题关键：栈是后进先出，队列是先进先出。元素从一个栈逐个弹出并压入另一个栈后，顺序会反转；需要决定的只是何时反转，才能既保证顺序又避免反复搬运。

为什么选择双栈：inStack 只接收新元素，outStack 只提供队首元素。只有当 outStack 为空且需要删除时，才把 inStack 全部倒入 outStack。这样最早进入 inStack 的元素会落到 outStack 栈顶。

状态与不变量：从 outStack 栈顶到栈底，再接上 inStack 栈底到栈顶，始终等于当前队列从头到尾的顺序。只要 outStack 非空，队首一定在它的栈顶；此时若搬入较新的元素，反而会让新元素压在旧元素上方，破坏先进先出。

正确性：入队只把新元素放到队尾对应的 inStack 栈顶，不变量保持。出队时，若 outStack 非空，直接弹出的就是最老元素；若为空，一次倒栈会反转 inStack，其最老元素来到栈顶。两个栈都空时队列才为空，按题意返回 -1。

延迟搬运还保证每个元素只会从 inStack 移到 outStack 一次，因此单次删除虽然最坏为 $O(n)$，连续操作的摊还代价是常数。

解题步骤

  1. appendTail(value)：直接把 value 压入 inStack。
  2. deleteHead()：若 outStack 为空，把 inStack 中的元素全部逐个搬过去。
  3. 搬运后若 outStack 仍为空，说明队列为空，返回 -1。
  4. 否则弹出并返回 outStack 栈顶。

例如依次执行“入队 1、入队 2、出队、入队 3、出队、出队”：第一次出队时倒栈并返回 1；此后 outStack 中的 2 必须先于新进入 inStack 的 3 返回，结果依次是 1、2、3。

代码实现

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
}

复杂度分析

  • appendTail：时间复杂度 $O(1)$。
  • deleteHead：单次最坏 $O(n)$，摊还时间复杂度 $O(1)$。每个元素至多压入、弹出两个栈各一次，$m$ 次操作的总成本是 $O(m)$。
  • 空间复杂度：$O(n)$。两个栈合计保存队列中的全部元素，每个元素只存在于一个栈中。

关键点总结

  • inStack 管新元素，outStack 管旧元素，职责不能混用。
  • 只有 outStack 为空时才能倒栈，这是正确性条件，也是摊还 $O(1)$ 的来源。
  • 倒栈必须一次搬完，才能让这一批元素恢复正确的先进先出顺序。
  • 复杂度应按元素整个生命周期记账，而不是只看某次搬运循环。

易错点总结

  • outStack 非空时仍倒栈：先入队 1、2，出队 1，再入队 3；若此时搬运，3 会压到 2 上面并被错误地先返回。
  • 只搬一个元素：入队 1、2、3 后会先搬出并返回最新的 3，而不是最早的 1。
  • 每次出队后把剩余元素倒回去：结果可能正确，但同一元素会反复搬运，最坏退化为 $O(n^2)$。
  • 搬运前只检查 outStack 就返回 -1：元素可能仍在 inStack；空队列必须在尝试搬运后判断。
  • Go 弹栈后不缩短切片：同一个栈顶会被重复返回，队列状态没有真正改变。

相似题目

题目 难度 考察点
155. 最小栈 中等 辅助栈同步维护历史最小值
173. 二叉搜索树迭代器 中等 用栈把中序遍历改写成惰性输出
225. 用队列实现栈 简单 反向模拟，靠队列旋转对齐顺序
232. 用栈实现队列 简单 本题同款双栈，另需实现 peek
341. 扁平化嵌套列表迭代器 中等 栈保存展开状态，延迟到取值时展开
622. 设计循环队列 中等 定长数组加双下标取模，容量受限
1188. 设计有限阻塞队列 中等 并发场景下的队列，需锁与条件变量
剑指 Offer 30. 包含min函数的栈 简单 栈上附加 $O(1)$ 查询，非结构转换
剑指 Offer 59 - I. 滑动窗口的最大值 困难 单调双端队列维护窗口最值
剑指 Offer 59 - II. 队列的最大值 中等 队列加单调辅助队列，同样摊还 $O(1)$