Oracle 双栈实现队列：惰性搬移与均摊 O(1)

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练接口 enqueue、front、dequeue；空队列查询抛 IndexError，元素类型任意。
• 只使用两个 Python 列表模拟 stack；不使用 deque 作为实现底层。

解题路线

1. enqueue 总是压 incoming。front/dequeue 若 outgoing 非空，直接读或弹其栈顶。
2. 只有 outgoing 为空时，才把 incoming 的全部元素逐个弹出压入 outgoing；顺序翻转后最早入队的元素处于 outgoing 栈顶。
3. 当 outgoing 仍有元素时，新增元素继续留在 incoming，不提前搬移；否则会把较新的元素放到较旧元素前面。
4. 势能或总次数证明：每个元素进 incoming 一次、从 incoming 搬出一次、进 outgoing 一次、从 outgoing 弹出一次，总操作数 O(N)，故均摊每操作 O(1)。

手动走一遍

enqueue(1)、enqueue(2)、dequeue() 返回 1；此时 outgoing 仍有 2。enqueue(3) 进入 incoming，front 仍为 2；再 dequeue 返回 2，下次才搬移 3。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Queue with amortized O(1) operations using only two stacks."""


class TwoStackQueue:
    def __init__(self):
        self.incoming = []
        self.outgoing = []

    def enqueue(self, value):
        self.incoming.append(value)

    def _prepare(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())

    def front(self):
        self._prepare()
        if not self.outgoing:
            raise IndexError("queue is empty")
        return self.outgoing[-1]

    def dequeue(self):
        self._prepare()
        if not self.outgoing:
            raise IndexError("queue is empty")
        return self.outgoing.pop()

复杂度

enqueue O(1)；front/dequeue 单次最坏 O(N)，N 次操作均摊 O(1)；空间 O(N)。不要把均摊界误称每次最坏 O(1)。

易错点与追问

容易失分的边界

• 每次入队都搬移两个栈，导致单次 O(N) 且实现复杂。
• outgoing 尚非空时把 incoming 倒进去，破坏 FIFO。
• 空队列时从空列表直接弹出，未定义错误语义。

继续深挖

• 若要求每次操作最坏 O(1)，双栈简单版为何不满足？
• 如何只用两个队列实现栈，哪种操作需要 O(N)？