使用两个堆栈创建队列，但入队时间复杂度为 O(1)

Question

有没有办法使用两个堆栈来实现队列，但使用 0(1) 入队？

我一直在学习如何创建队列，我一直试图找到答案的问题之一是如何使用两个堆栈来优化队列。我实现的代码似乎运行时间最差。

下面是我的代码，我可以采用不同的方法吗？

`类队列： def init（自身）： self.s1 = [] self.s2 = []

def enqueue(self, item):
    while len(self.s1) != 0:
        self.s2.append(self.s1.pop())
    self.s1.append(item)
    while len(self.s2) != 0:
        self.s1.append(self.s2.pop())

def dequeue(self):
    if len(self.s1) == 0:
        raise IndexError("Cannot pop from an empty queue")
    return self.s1.pop()

队列() `

Answer 1

实际上，您可以使用 2 个堆栈来实现队列，入队时间复杂度为 O(1)，出队时间复杂度为 O(n)。 这是一个使用您的代码的示例：

def enqueue(self, item):
    self.s1.append(item)

def dequeue(self):
    if len(self.s1) == 0:
        raise IndexError("Cannot pop from an empty queue")

    queue_head = None

    # Search for the first item put in queue
    while len(self.s1) != 1:
        self.s2.append(self.s1.pop())

    # Save the item while we restore s1's data
    queue_head = self.s1.pop()

    while len(self.s2) != 0:
        self.s1.append(self.s2.pop())
    
    return queue_head

如果你不能让入队和出队都变成O(1)，而必须选择一个复杂度更高的（通常是你最常用的）。