题目重点：用入栈与出栈两层维护 FIFO；证明每个元素最多倒栈一次，覆盖交错入队出队和空队列操作。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练 API 为 push、pop、peek、empty；元素可为任意 Python 对象。
- 空队列 pop/peek 抛 IndexError；题目只给题名，具体语言和错误契约须现场确认。
解题路线
- 新元素只压入 inbox。要读队首时，如果 outbox 非空，栈顶就是最早尚未出队元素。
- 若 outbox 为空，将 inbox 元素全部逐个弹出压到 outbox；顺序反转一次，最早入队元素来到 outbox 栈顶。
- 只有 outbox 清空时才倒栈；在它尚有旧元素时把新元素倒进来会破坏 FIFO。
- 每元素 push 入 inbox 一次、倒到 outbox 一次、最终弹出一次，所以虽然单次 pop 可能 O(n)，长期均摊每次 O(1)。
手动走一遍
依次 push 1、2，首次 pop 触发倒栈，outbox 从底到顶是 2、1，弹得 1。此时再 push 3，peek 仍应看到 outbox 的 2；待 2 出队后才倒入 3。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class TwoStackQueue:
def __init__(self) -> None:
self.inbox: list[object] = []
self.outbox: list[object] = []
def push(self, value: object) -> None:
self.inbox.append(value)
def _refill(self) -> None:
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def peek(self) -> object:
self._refill()
if not self.outbox:
raise IndexError("peek from empty queue")
return self.outbox[-1]
def pop(self) -> object:
self._refill()
if not self.outbox:
raise IndexError("pop from empty queue")
return self.outbox.pop()
def empty(self) -> bool:
return not self.inbox and not self.outbox
if __name__ == "__main__":
queue = TwoStackQueue()
queue.push(1)
queue.push(2)
assert queue.pop() == 1 and queue.peek() == 2
复杂度
push 最坏 O(1)，pop/peek 最坏 O(n)、均摊 O(1)；empty O(1)。两栈总共保存每个未出队元素一次，空间 O(n)。均摊可用势函数 2×|inbox| 形式化说明。
易错点与追问
容易失分的边界
- 每次 pop 都把两个栈来回倒，虽正确但可能 O(n) 每次。
- outbox 未空就把 inbox 新元素转入，队序错乱。
- 把 empty 只写成 inbox 为空，漏看 outbox。
- 声称所有单次 pop 均 O(1)，忽略触发转移的那次。
继续深挖
- 如果多线程并发 push/pop，哪些状态转移要加锁？
- 如何用一个队列实现栈？
- 若要求 pop 最坏 O(1)，两栈懒倒方案能否满足？
