如何用两个栈实现队列并保证入队操作时间复杂度为O(1)？

你当前的实现里，每次入队都要把s1的所有元素先移到s2，添加新元素后再移回s1，这导致入队操作的时间复杂度是O(n)，这就是你遇到的最坏运行时问题——每次入队都要遍历所有已有元素，数据量大的时候性能会很差。

换一种分工方式，让两个栈分别承担「入队」和「出队」的职责，就能实现入队O(1)的需求：

• in_stack：专门用来接收入队的元素，所有入队操作直接往这个栈里添加
• out_stack：专门用来处理出队操作，只有当这个栈为空时，才把in_stack里的所有元素一次性倒过来（此时元素顺序就和队列的先进先出一致了）

以下是具体实现代码：

class Queue:
    def __init__(self):
        self.in_stack = []  # 负责入队的栈
        self.out_stack = [] # 负责出队的栈

    def enqueue(self, item):
        # 入队直接追加到in_stack，时间复杂度稳定O(1)
        self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            # 如果out_stack为空，把in_stack的所有元素倒过来
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        # 如果out_stack还是空，说明整个队列是空的
        if not self.out_stack:
            raise IndexError("无法从空队列中弹出元素")
        # 直接从out_stack弹出，时间复杂度O(1)
        return self.out_stack.pop()

这个实现的优势：

• 入队操作：不管队列里有多少元素，都是直接往in_stack末尾追加，时间复杂度稳定O(1)，完全符合你的需求。
• 出队操作：只有当out_stack为空时，才需要把in_stack的元素全部移动过来，这个操作的时间复杂度是O(n)，但每个元素只会被移动一次——从in_stack到out_stack后，后续出队都直接从out_stack弹出，不需要再移动。所以摊还时间复杂度是O(1)，整体性能比你原来的实现高效得多。

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