用两个堆栈实现一个队列

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

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

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

Figure 1: 两个栈实现队列

假设我们需要对这个队列执行\(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()

在手机上阅读或分享本文请扫描以下二维码:
By @Zhengyi Yang in
Tags : #queue, #stack, #python,

Comments

评论功能已关闭。