LinkedIn 双栈实现队列：为什么单次 O(N) 仍可摊还 O(1)

题意与假设

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

• 训练接口 push/pop/peek/empty；空队列 pop/peek 抛 IndexError，push 可存任意值。题目是否只允许一个栈、能否用递归辅助空间未知，故明确为两个栈的练习契约。

解题路线

1. incoming 收所有新元素。需要 peek/pop 时若 outgoing 非空直接看/弹其栈顶；若空，则把 incoming 所有元素依次倒入 outgoing，此时最早入队者位于 outgoing 顶。
2. 只有 outgoing 为空才倒，避免每次查询全量搬移。每个元素一生最多被压入 incoming 一次、从 incoming 弹出并压入 outgoing 一次、最后从 outgoing 弹出一次，因此 Q 次操作总 O(Q)。
3. 单次 pop 触发倒入时可能 O(N)，所以准确说摊还 O(1)，不是每次最坏 O(1)。如果业务需要严格最坏 O(1)，需更复杂的实时队列结构。
4. 两个栈都空时 empty 为 true；先 refill 再判空，避免空队列 peek 误返回 None 与合法 None 值混淆。

手动走一遍

push 1、push 2 后 outgoing 空；pop 触发倒入，outgoing 依次入 2、1，弹出 1。再 push 3，outgoing 仍有 2，下一次 pop 先返回 2，之后才会倒入 3。

Python 参考实现

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

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

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

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

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

    def peek(self):
        self._refill()
        if not self.outgoing:
            raise IndexError("empty queue")
        return self.outgoing[-1]

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

    def empty(self):
        return not self.incoming and not self.outgoing

复杂度

push 最坏 O(1)，pop/peek 最坏 O(N)、摊还 O(1)，空间 O(N)。训练代码经 10,000 组随机操作序列与独立 deque oracle 对照。

易错点与追问

容易失分的边界

• 每次 pop 都把两栈来回倒，退化 O(N) 每次。
• incoming 有新元素时先倒入 outgoing，破坏已有 FIFO 次序。
• 把摊还 O(1) 宣称严格最坏 O(1)。
• 空队列行为未定义。
• 合法值为 None 时用 None 表示 miss。

继续深挖

• 如何用 potential method 证明摊还？
• 若只准一个显式栈但允许递归？
• 多线程 push/pop 怎样保持 FIFO 原子性？
• 若需要持久化队列该结构够用吗？