Python数据结构与算法（3.3）——队列

1.3 队列的应用场景

队列具有广泛的应用场景，例如：

• 在作业具有相同优先级的前提下，操作系统会按照作业的到达顺序安排作业；
• 击键操作被放入一个类似于队列的缓冲区，以便对应的字符按正确的顺序显示；
• 模拟现实世界的队列；
• 多道程序设计；
• 异步数据传输；

除了以上应用外，我们在之后的学习中还将看到队列用作许多算法的辅助数据结构。

2. 队列的实现

和线性表一样，队列同样有顺序存储和链式存储两种存储表示方式。

2.1 顺序队列的实现

类似于顺序栈，队列的顺序存储结构利用一组地址连续的存储单元将元素从队列头到队列尾依次存放，同时需要用两个指针 front 和 rear 分别指示队列头元素和队列尾元素的位置。初始化空队列时，front=rear=0，当元素入队时，rear 加 1，而元素出队时，front 加 1，如下所示：

从以上示例中，可以很清楚地看到位于队头之前的空间被浪费了，为了解决这一问题，我们可以假设顺序队列为环状空间，将最后一个元素和第一个元素视为连续的，如下图所示：

从上图可以看出，当队列满时与队列空时，都有front=rear，因此无法通过 front==rear 来判断队列是否已满。针对这一问题，有两种解决方法：1) 设置标志来指示队列中是否还有空闲空间；2) 放弃一个元素空间，即当 front 指针在 rear 指针的下一位时 ((rear+1)%max_size=front) 队列为满。以下实现使用第二种方案。
同样顺序队列可以是固定长度和动态长度，当队列满时，定长顺序队列会抛出栈满异常，动态顺序队列则会动态申请空闲空间。

2.1.1 队列的初始化

顺序队列的初始化需要 4 部分信息：queue 列表用于存储数据元素，max_size 用于存储 queue 列表的最大长度，以及 front 和 rear 分别用于记录队头元素和队尾元素的索引：

class Queue:    def __init__(self, max_size=5): self.max_size = max_size self.queue = [None] * self.max_size self.front = 0 self.rear = 0

2.1.2 求队列长度

由于 front 和 rear 分别用于记录队头元素和队尾元素的索引，因此我们可以方便的计算出队列的长度；同时我们需要考虑队列为循环队列，front 可能大于 rear，不能直接通过 rear-front，我们需要利用公式计算解决此问题：
$$(rear-front+max\_size)\%max\_size$$

Python 实现如下：

    def size(self): return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 判队列空

根据 front 和 rear 的值可以方便的判断队列是否为空：

    def isempty(self): return self.rear==self.front

2.1.4 判队列满

根据 front 和 rear 的值可以方便的判断队列是否还有空余空间：

    def isfull(self): return ((self.rear+1) % self.max_size == self.front)

2.1.5 入队

入队时，需要首先判断队列中是否还有空闲空间，然后根据队列为定长顺序队列或动态顺序队列，入队操作稍有不同：
[定长顺序队列的入队操作] 如果队满，则引发异常：

    def enqueue(self, data): if not self.isfull():     self.queue[self.rear] = data     self.rear = (self.rear+1) % self.max_size else:     raise IndexError("Full Queue Exception")

[动态顺序队列的入队操作] 如果队列满，则首先申请新空间，然后再执行入队操作：

    def resize(self): new_size = 2 * self.max_size new_queue = [None] * new_size for i in range(self.max_size):     new_queue[i] = self.queue[i] self.queue = new_queue self.max_size = new_size    def enqueue(self, data): if self.isfull():     self.resize() self.queue[self.rear] = data self.rear = (self.rear+1) % self.max_size

入队的时间复杂度为 $O(1)$。这里需要注意的是，虽然当动态顺序队列满时，原队列中的元素需要首先复制到新队列中，然后添加新元素，但参考《顺序表及其操作实现》中顺序表追加操作的介绍，由于 n 次入队操作的总时间 $T(n)$ 与 $O(n)$ 成正比，因此队栈的摊销时间复杂度可以认为是 $O(1)$。

2.1.6 出队

若队列不空，则删除并返回队头元素：

    def dequeue(self): if not self.isempty():     result = self.queue[self.front]     self.front = (self.front+1) % self.max_size     return result else:     raise IndexError("Empty Queue Exception")

2.1.7 求队头元素

若队列不空，则返回队头元素：

    def head(self): if not self.isempty():     result = self.queue[self.front]     return result else:     raise IndexError("Empty Queue Exception")

2.2 链队列的实现

队列的另一种存储表示方式是使用链式存储结构，因此也常称为链队列，其中 enqueue 操作是通过在链表尾部插入元素来实现的，dequeue 操作是通过从头部删除节点来实现的。

2.2.1 队列结点

队列的结点实现与链表并无差别：

class Node:    def __init__(self, data=None): self.data = data self.next = None    def __str__(self): return str(self.data)

2.2.2 队列的初始化

队列的初始化函数中，使其队头指针 front 和 rear 均指向 None，并初始化队列长度：

class Queue:    def __init__(self): self.front = None self.rear = None self.num = 0

2.2.3 求队列长度

返回 size 的值用于求取队列的长度，如果没有 size 属性，则需要遍历整个链表才能得到队列长度：

    def size(self): return self.num

2.2.4 判队列空

根据队列的长度可以很容易的判断队列是否为空队列：

    def isempty(self): return self.num <= 0

2.2.5 入队

入队时，在队尾插入新元素，并且需要将队尾指针 rear 指向新元素，如果队列为空，需要将队头指针 front 也指向此元素：

    def enqueue(self, data): node = Node(data) if self.front is None:     self.rear = node     self.front = self.rear else:     self.rear.next = node     self.rear = node self.num += 1

2.2.6 出队

若队列不空，则删除并返回队头元素，并且需要更新队头指针 front 指向原队头结点的后继结点，若出队元素尾队中最后一个结点，则更新队尾指针 rear：

    def dequeue(self): if self.isempty():     raise IndexError("Empty Queue Exception") result = self.front.data self.front = self.front.next self.num -= 1 if self.isempty():     self.rear = self.front return result

2.2.7 求队头元素

若队列不空，则返回队头元素：

    def head(self): if self.isempty():     raise IndexError("Empty Queue Exception") result = self.front.data return result

2.3 队列的不同实现对比

队列的不同实现对比与栈的不同实现类似，可以参考《栈及其操作实现》。

3. 队列应用

接下来，我们首先测试上述实现的队列，以验证操作的有效性，然后利用实现的基本操作来解决实际算法问题。

3.1 顺序队列的应用

首先初始化一个顺序队列 queue，然后测试相关操作：

# 初始化一个最大长度为5的队列q = Queue(5)print('队列空?', q.isempty())for i in range(4):    print('入队元素：', i)    q.enqueue(i)print('队列满?', q.isfull())print('队头元素：', q.head())print('队列长度为：', q.size())while not q.isempty():    print('出队元素：', q.dequeue())

测试程序输出结果如下：

队列空? True入队元素： 0入队元素： 1入队元素： 2入队元素： 3# 队列中弃用一个空间，因此队列中有4个元素即满队列满? True队头元素： 0队列长度为： 4出队元素： 0出队元素： 1出队元素： 2出队元素： 3

3.2 链队列的应用

首先初始化一个链队列 queue，然后测试相关操作：

# 初始化新队列q = Queue()print('队列空?', q.isempty())for i in range(4):    print('入队元素：', i)    q.enqueue(i)print('队头元素：', q.head())print('队列长度为：', q.size())while not q.isempty():    print('出队元素：', q.dequeue())

测试程序输出结果如下：

队列空? True入队元素： 0入队元素： 1入队元素： 2入队元素： 3队头元素： 0队列长度为： 4出队元素： 0出队元素： 1出队元素： 2出队元素： 3

3.3 利用队列基本操作实现复杂算法

[1] 考虑经典的约瑟夫斯环问题，n 个人围成一圈，从第 1 个人开始报数，第 m 个将被淘汰，重复上述过程，直到只剩下一个人，其余人都将被淘汰。
我们使用队列来模拟一个环，如下图所示，从队列的头部开始，将位于队首的人移出队列并立刻将其插入队列的尾部，之后此人会一直等待，直到其再次到达队列的头部。在出列和入列 m-1 次之后，位于队列头部的人出局(即第 m 个人)，然后新一轮游戏开始；如此反复，直到队列中只剩下一个人(队列的大小为 1 )。

def Josephus(name_list, m):    queue = Queue()    for name in name_list: queue.enqueue(name)    while queue.size() > 1: for i in range(m-1):     queue.enqueue(queue.dequeue()) queue.dequeue()    return queue.head()# n=6, m=5result = Josephus(["A", "B", "C", "D", "E", "F"], 5)print('幸存的人为', result)

程序输出结果如下：

幸存的人为 A

相关链接

线性表基本概念
顺序表及其操作实现
单链表及其操作实现
栈及其操作实现