如何使用两个栈实现操作均为摊销常数时间的队列

结论 #

可行，双栈实现队列的所有操作确实可以达到*摊销O(1)*的时间复杂度。

核心实现思路 #

核心逻辑是拆分队列的「入队」和「出队/读队首」操作到两个独立的栈上，利用栈的逆序特性模拟队列的先进先出规则：

• 第一个栈命名为in_stack，专门处理入队请求，所有新元素直接压入这个栈，单次操作时间复杂度为O(1)
• 第二个栈命名为out_stack，专门处理出队、读取队首的请求，只有当out_stack为空时，才会把in_stack的所有元素逐个弹出并压入out_stack，完成队列顺序的翻转。

具体操作逻辑 #

1. 入队（enqueue） #

直接把元素压入in_stack即可，不需要额外操作。
伪代码示例：

def enqueue(element):
    in_stack.push(element)

2. 出队（dequeue） #

• 如果out_stack不为空，直接弹出out_stack的栈顶元素，即为队列的队首元素，单次操作时间复杂度O(1)
• 如果out_stack为空，遍历in_stack的所有元素，逐个弹出压入out_stack，之后再弹出out_stack的栈顶元素即可
  伪代码示例：

def dequeue():
    if out_stack.is_empty():
        while not in_stack.is_empty():
            out_stack.push(in_stack.pop())
    return out_stack.pop()

3. 读取队首元素（peek） #

逻辑和出队完全一致，只是最后不弹出out_stack的栈顶元素，直接返回即可。
伪代码示例：

def peek():
    if out_stack.is_empty():
        while not in_stack.is_empty():
            out_stack.push(in_stack.pop())
    return out_stack.top()

4. 判断队列是否为空（isEmpty） #

只要in_stack和out_stack都为空，队列就为空，单次操作时间复杂度O(1)。
伪代码示例：

def is_empty():
    return in_stack.is_empty() and out_stack.is_empty()

摊销时间复杂度证明 #

每个元素最多只会经历4次操作：压入in_stack、弹出in_stack、压入out_stack、弹出out_stack，没有元素会被重复搬运。把N次入队+N次出队的总操作次数平摊到每个元素上，每个元素仅对应常数次操作，因此所有操作的摊销时间复杂度为O(1)。

内容的提问来源于stack exchange，提问作者SuperStar