博客

队列是线性的集合，对于队列来说，插入限制在一端（队尾），删除限制在另一端（队头）。队列支持先进先出（FIFO）的协议。

我们在后面会提到一种特殊的队列——

优先队列

，在优先队列中，具有较高优先级的项会在那些具有较低优先级的项之前弹出，而具有相同优先级的项，则会按照先进先出（FIFO）的顺序弹出。

队列的接口

Python队列可以来模拟队列，使用列表的append方法来把项添加到队列的队尾，并且使用列表的pop(0)方法从列表的前面删除项并返回它。这种选择的主要缺点是：所有其它的列表操作也都可以操作队列。这包括在任何的位置插入、替换和删除一项。这些额外的操作违反了队列作为一种抽象数据类型的本意。这里，我们将为队列实现一个更加严格的接口。

队列的实现

队列的链表实现

栈和队列的链表实现表现大体上相同，LinkedStack和LinkedQueue这两个类，都使用了一个单链表Node类来实现节点，pop操作在两个集合的序列中都是删除第一个节点。然而，LinkedQueue.add和LinkedStack.push有所不同。

栈的push操作在序列的头部添加一个节点，而add会在尾部添加一个节点。

为了提供对队列的链表结构两端的快速访问，队列还有指向两端的外部指针。下图是一个包含了4个项的链表队列。

LinkedQueue类的实例变量front和rear的初始值都为None，集合框架中定义了一个名为size的变量，它记录了队列中当前的元素的数目。

add操作

在add操作的过程中，程序创建了一个新的节点，并将最后一个节点的next指针设置为这个新的节点，并且将变量rear设置为这个新节点。

    def add(self, item):
        """Adds item to the rear of the queue."""
        newNode = Node(item, None)
        if self.isEmpty():
            self._front = newNode
        else:
            self._rear.next = newNode
        self._rear = newNode
        self._size += 1

pop操作

正如前面所说，LinkedQueue.pop和LinkedStack.pop类似，然而，

如果在一次弹出操作之后，队列变为空，那么必须将front和rear指针都设置为None

。

    def pop(self):
        """
        Removes and returns the item at the front of the queue.
        Precondition: the queue is not empty.
        Raises: KeyError if the queue is empty.
        Postcondition: the front item is removed from the queue."""
        if self.isEmpty():
            raise KeyError("The queue is empty.")
        oldItem = self._front.data
        self._front = self._front.next
        if self._front is None:
            self._rear = None
        self._size -= 1
        return oldItem

数组实现

栈的数组实现和队列的数组实现，不像是链表实现那么相似了。栈的数组实现只需要访问数组的逻辑末尾的项。然而，

队列的数组实现必须访问逻辑开头位置和逻辑末尾的项

。这个过程比较复杂，所以我们一次进行三次尝试：

1.第一次尝试

实现一个队列的第一次尝试是，将队列的队头固定在索引位置0，并且维护一个名为rear的索引变量，它指向了位置为n-1的最后一项，其中n就是队列中的项的数目。

对于这个实现，add操作是很高效的。然而，pop操作需要将数组的第一项以外的所有项都向左移动，这是一个O(n)的过程。

2.第二次尝试

可以在pop操作后，

不向左迁移项，避免这个线性行为

。修改后的实现维护了另外一个索引，名为front，它指向了队列的队头。front指针从0开始，并且随着项的弹出，该指针向后移动。

3.第三次尝试

这里通过使用一个循环数组实现，可以同时实现add和pop的较好的运行时间。这个实现在某个方面和前面的实现类似，即front和rear指针都从数组的开始位置开始。

然而，front指针现在在整个数组中都“追逐”着rear指针，在add操作中，rear指针进一步移动到了front指针之前，而在pop操作中，front指针移动一个位置。

当任何一个指针将要达到数组的末尾的时候，就将该指针重置为0。这就达到了将队列折返到数组的开始处而不需要移动任何项的效果

。

rear指针现在似乎在追逐着front指针了，知道front指针到达了数组的末尾，此时，将front重置为0，你可以看到，add和pop现在的最大运行时间都是O(1)。

我们可以通过保持队列中的项的一个计数来确定队列是满的还是空的。

当这个计数等于数组的大小的时候，我们知道，应该调整数组的大小了

。

在调整数组大小之后，你可能想要让队列占据最初的数据段

，通过将front指针设置为0来做到这一点。为了做到这一点，考虑开始调整大小时候的两种情况：

（1）front指针小于rear指针，在这种情况下，我们在最初的数组中从front到rear遍历循环，并且将其

复制到新的数组的

0到size-1中。

（2）rear指针小于front指针。在这种情况下，在最初的数组中从front到size-1循环遍历，复制到新数组的0到size-front中，然后在最初的数组中从0到rear循环遍历，将其复制到新数组size-front+1到size-1中。

两种实现的时间和空间复杂度分析

两个队列类的时间和空间复杂度，与其对应的栈的类是相似的。

先来考虑队列的链表实现，__str__、__add__、__eq__方法的运行时间都是O(n)，所有其它方法的最大运行时间都是O(1)，由于队列的链表结构中，有指向头节点和尾节点的外部链接，我们可以从常数时间访问这些节点，

总的空间需求是2n+3

，其中n是队列的大小，3个单元格是队列的逻辑大小、头指针、尾指针。

对于队列的循环数组实现来说，

如果数组是静态的，除了__str__、__add__、__eq__之外的所有方法，其运行的最大时间都是O(1)

，特别的，add和pop操作不会移动数组中的项，如果数组是动态的，在需要调整数组大小的时候，add和pop都会增加到O(n)，但是平均运行时间保持为O(1)。数组实现的空间利用取决于装载因子，

对于大于二分之一的装载因子，数组实现对内存的利用效率比链表实现要高

。

优先队列

优先队列是一种特殊的队列类型，当向一个优先队列中添加项的时候，它们都被赋予了一个排列顺序，当删除项的时候，较高优先级的项会在那些较低优先级的项之前删除。相同优先级的项，按照通常的FIFO的顺序删除。因此，整数、字符串或识别比较运算符的任何其他对象，都可以在优先队列中排序，

如果一个对象不识别这些运算符，那么可以通过能够识别这些运算符的另一个对象中的优先级编号来包装（或绑定）它。

然后，队列会通过将该对象识别为其他可以进行比较的对象类型。

当一个对象本身是不可比较的时候，可以使用另一个可比较的对象的优先级来包装它，这个包装器叫Comparable。

这个类包含了一个构造方法，该方法接收一个项及其优先级作为参数。

当创建了包装器对象之后，getItem、getPriority、__str__、__eq__、__le__和__lt__方法被用来提取该项或者其优先级、返回其字符串表示。

class Comparable(object):

    def __init__(self, data, priority = 1):
        self._data = data
        self._priority = priority

    def __str__(self):
        """Returns the string rep of the contained datum."""
        return str(self._data)

    def __eq__(self, other):
        """Returns True if the contained priorities are equal
        or False otherwise."""
        if self is other: return True
        if type(self) != type(other): return False
        return self._priority == other._priority

    def __lt__(self, other):
        """Returns True if self's priority < other's priority,
        or False otherwise."""
        return self._priority < other._priority

    def __le__(self, other):
        """Returns True if self's priority <= other's priority,
        or False otherwise."""
        return self._priority <= other._priority

    def getItem(self):
        """Returns the contained datum."""
        return self._data 

    def getPriority(self):
        """Returns the contained priority."""
        return self._priority 

在插入的过程中，优先级队列并不知道是比较包装器中的项还是只是比较项。当在for循环中使用peek或pop方法访问一个包装的项的时候，

必须先用getItem方法来为其解包，然后才能对其进行处理

。

例如，假设标签为a、b和c的项是不能比较的，但是它们在队列中的优先级分别为1、2和3，然后，如下的代码实现了将其添加到一个名为queue的优先队列中去，并访问它们的功能。

queue.add(Comparable(a,1))
queue.add(Comparable(b,2))
queue.add(Comparable(c,3))
while not queue.isEmpty():
    item = queue.pop().getItem()
    <do something with item>

本书介绍了优先队列的两种实现，

一种实现使用了堆这个数据结构

。另一种实现扩展了前面介绍的LinkedQueue类，这就是所谓的有序列表的实现。

有序的列表是以一种自然的顺序维护的可比较项的一个列表。优先队列列表应该按照这样的顺序排列，总是只能够从列表的一端访问或删除最小的元素。

元素按照顺序插入其正确的位置

。

如果总是从结构的头部删除最小的元素的话，单链表结构可以很好地表示这种类型的列表，如果这个结构继承自LinkedQueue类中使用的单链表结构，我们可以通过运行该类的pop方法来继续删除一个元素，只有add方法需要做出修改，在新的LinkedPriorityQueue子类中，需要覆盖其定义。

LinkedPriorityQueue类的代码如下：

from node import Node
from linkedqueue import LinkedQueue

class LinkedPriorityQueue(LinkedQueue):
    """A link-based priority queue implementation."""


    def __init__(self, sourceCollection = None):
        """Sets the initial state of self, which includes the
        contents of sourceCollection, if it's present."""
        LinkedQueue.__init__(self, sourceCollection)

    def add(self, item):
        """Adds item to its proper place in the queue."""
        if self.isEmpty() or item >= self._rear.data:
            LinkedQueue.add(self, item)
        else:
            probe = self._front
            trailer = None
            while item >= probe.data:
                trailer = probe
                probe = probe.next
            newNode = Node(item, probe)
            if trailer is None:
                self._front = newNode
            else:
                trailer.next = newNode
            self._size += 1

LinkPriorityQueue的时间和空间复杂度的分析和LinkedQueue的分析是相同的，只有add方法是例外的。这个方法现在必须搜索要插入项的正确位置，一旦找到这个位置就重新排列链接，这是一个常数时间的操作，但是，搜索本身是线性的，因此，

add方法的时间复杂度是O(n)

。

本文是数据结构（用Python实现）这本书的读书笔记！