用两个堆栈实现一个队列

堆栈(Stack)和队列(Queue)是计算机中两种重要的基本数据结构。堆栈的主要特点是“先进后出”(First In Last Out, FILO)，即最早推入堆栈的数据将会被最后弹出栈。相反的，队列的特点则为“先进先出”(First In First Out, FIFO)，即最早被添加到队列的数据也会最先取出队列。

对于一个堆栈，不可缺少的是push和pop方法，前者将数据推入堆栈，后者将最后一个推入堆栈的元素弹出堆栈。然而对于队列，我们必须提供enqueue和dequeue方法，前者将数据添加到队列中，后者将最先被添加到队列的元素取出队列。

如下图1所示，我们可以通过两个堆栈的数据结构来实现一个队列。我们将这两个堆栈分别命名为inStack和outStack。当有数据enqueue时，我们将数据push进inStack。当调用dequeue时则有两种情况，若outStack为空，则我们将inStack中的数据转移到outStack中，此时数据的顺序将会被反转，然后我们从outStack中pop出一个数据。如果outStack不为空，则我们直接从outStack中pop出一个数据即可。

假设我们需要对这个队列执行$m$次函数调用(enqueue或者dequeue)，则这种方法的时间复杂度为$O(m)$。在Python中的实现如下：

class QueueTwoStacks:

    def __init__(self):
        self.in_stack = []
        self.out_stack = []

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

    def dequeue(self):
        if not self.out_stack:
            # Move items from in_stack to out_stack, reversing order
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
            # If out_stack is still empty, raise an error
            if not self.out_stack:
                raise IndexError("Can't dequeue from an empty queue")
        return self.out_stack.pop()

在手机上阅读或分享本文请扫描以下二维码：

用两个堆栈实现一个队列

Comments