python列表数据结构,数据结构中队列

　　和堆栈队列是编程中常见的数据类型。本节将详细介绍队列的定义及其不同的实现，并给出队列的一些实际应用。感兴趣的朋友可以看看。

　　00-1010 0.学习目标1。队列的基本概念1.1队列的基本概念1.2队列的抽象数据类型1.3队列的应用场景2.1顺序队列的实现2.2链式队列的实现2.3不同队列实现的比较3.1顺序队列的应用3.2链式队列的应用3.3通过队列的基本操作实现复杂算法

目录

　　堆栈和队列是编程中常见的数据类型。从数据结构的角度来看，栈和队列也是线性表，操作有限。它们的基本操作是线性表操作的子集，但从数据类型的角度来看，它们与线性表有很大的不同。本节将介绍队列的定义及其不同的实现，并给出队列的一些实际应用。

　　通过本节，您应掌握以下内容：

　　队列的基本概念及其不同的实现方法；队列基本操作的实现和时间复杂度；利用队列的基本操作实现复杂算法

0. 学习目标

1. 队列的基本概念

　　Queue是一个线性表，其中的插入和删除操作仅限于序列的两端(如果一个新元素从一段插入其中，现有元素只能从另一端删除)。对于一个队列来说，允许元素插入的那一端称为尾部，而允许元素取出的那一段称为前端。

　　在队列中，数据到达的顺序非常重要。新添加的元素必须在队列的末尾，队列中时间最长的元素排在最前面。这种排序原则被称为先进先出(FIFO)或后进先出(LILO)。

　　现实中排队的例子随处可见。我们生活中就餐所需的排队就是一个排队的真实例子。第一个进入队列的人可以先吃饭，后来者需要在队列的最后等待。假设队列是Q=(a0，a1，an)，队列头元素是A0，an是队列尾元素。队列中的元素按照a0，a1，an和dequeue只能按此顺序退出。队列头元素是第一个出列元素，但只有A0，下图是一个简单的队列示例：

　　通过观察添加和删除元素的顺序，可以快速理解队列中包含的思想。下图显示了队列元素的排队和出队过程。队列中元素的插入和移除顺序完全相同。

1.1 队列的基本概念

　　队列除了主操作(入队和出队)之外，还有初始化、队列清空、队列长度等辅助操作。具体来说，队列的抽象数据类型定义如下：

1.2 队列抽象数据类型

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

　　在作业具有相同优先级的前提下，操作系统会按照作业到达的顺序来安排作业；击键操作放入类似队列的缓冲区，使相应的字符按正确的顺序显示；模拟真实世界的队列；多频道节目；异步数据传输；除了上述应用，我们将在下面的研究中看到队列被用作许多算法的辅助数据结构。

1.3 队列的应用场景

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

2. 队列的实现

　　类似于顺序堆栈，队列的顺序存储结构利用一组地址。

　　连续的存储单元依次存放从队列头到队列尾依次存放，同时需要用两个指针 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，我们需要利用公式计算解决此问题：

　　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 利用队列基本操作实现复杂算法

　　考虑经典的约瑟夫斯环问题，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=5
　　result = Josephus(["A", "B", "C", "D", "E", "F"], 5)
　　print(幸存的人为, result)
　　

　　程序输出结果如下：

幸存的人为 A

　　

　　以上就是Python数据结构之队列详解的详细内容，更多关于Python队列的资料请关注盛行IT软件开发工作室其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。