用两个栈实现一个队列。

核心回答

用一个输入栈接收入队元素，一个输出栈负责出队。输入栈中的后进先出顺序，经过一次整体倒入输出栈后，再反转成队列需要的先进先出顺序。只有输出栈为空时才搬运，输出栈还有旧元素时不能把新元素盖到它上面。

每个元素最多进入输入栈一次、转移一次、出队一次，因此一串操作的总成本与操作数成正比，入队与出队的摊还时间为 O(1)。单次触发整体搬运的出队仍可能是 O(n)，空间复杂度为 O(n)。

Python 实现

空队列的 pop() 和 peek() 抛出 IndexError；peek() 查看而不删除。这里使用 list 尾部作为栈顶，不能使用头部删除来假装栈操作。

class TwoStackQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []

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

    def _prepare(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

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

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

    def empty(self):
        return not self.inbox and not self.outbox

为什么只在输出栈为空时搬运

依次入队 1,2，输出栈搬成 [2,1]，第一次出队得到 1。此时再入队 3，队头仍是输出栈里的 2；等 2 出队后，才把输入栈里的 3 搬过来。

如果每次出队都把输入栈倒入已有输出栈，新元素会盖住尚未出队的旧元素，破坏先后顺序。队列为空则要求两个栈同时为空，不能只看其中一个。

该版本只定义单线程容器行为。多线程中需要把检查、搬运和取值作为同一临界区保护，两个栈各自线程安全并不能自动保证整个队列正确。

参考资料