python列表数据结构,python队列的基本操作,Python数据结构之队列详解

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

0. 学习目标

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

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

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

1. 队列的基本概念

1.1 队列的基本概念

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

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

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

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

1.2 队列抽象数据类型

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

1.3 队列的应用场景

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

在作业具有相同优先级的前提下，操作系统会按照作业到达的顺序来安排作业；击键操作放入类似队列的缓冲区，使相应的字符按正确的顺序显示；模拟真实世界的队列；多频道节目；异步数据传输；

除了上述应用，我们将在下面的研究中看到队列被用作许多算法的辅助数据结构。

2. 队列的实现

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

2.1 顺序队列的实现

与顺序堆栈类似，队列的顺序存储结构使用一组具有连续地址的存储单元，从队列头到队列尾顺序存储它们。同时，需要前后两个指针分别指示队列的头和尾的位置。初始化空队列时，front=rear=0。当元素入队时，后方增加1，而当元素出队时，前方增加1，如下所示：

从上面的例子可以明显看出，队列头前面的空间被浪费了。为了解决这个问题，我们可以假设顺序队列是一个循环空间，并将最后一个元素和第一个元素视为连续的，如下图所示：

从上图可以看出，队列满的时候和队列空的时候都存在front=rear，所以不能用front==rear来判断队列是否满。要解决这个问题，有两种解决方案：1)设置一个标志来指示队列中是否有空闲空间；2)让出一个元素空间，即当前指针紧挨着后指针时((后1)%max_size=front)，队列已满。下面的实现使用第二种方案。

类似地，顺序队列可以是固定长度和动态长度。当队列满时，固定长度的顺序队列将抛出栈满异常，而动态顺序队列将动态地申请空闲空间。

2.1.1 队列的初始化

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

类别队列：

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分别用来记录队列头元素和队列尾元素的索引，所以我们很容易计算出队列的长度。同时需要考虑到队列是一个循环队列，前面可能比后面大，所以不能直接从后-前穿过。我们需要通过公式计算来解决这个问题：

Python的实现如下：

定义大小(自身):

return(self . rear-self . front self . max _ size)% self . max _ size

2.1.3 判队列空

根据前面和后面的值，可以方便地判断队列是否为空：

def isempty(self):

return self.rear==self.front

2.1.4 判队列满

根据前面和后面的值，可以方便地判断队列中是否有空闲空间：

def isfull(自身):

return((self . rear 1)% self . max _ size==self . front)

2.1.5 入队

加入队列时，需要先确定队列中是否有空闲空间，然后根据队列是定长顺序队列还是动态顺序队列，加入操作略有不同：

【定长顺序队列的队列操作】如果队列满了，会抛出异常：

定义入队(自身，数据):

如果不是self.isfull():

self.queue[self.rear]=数据

self . rear=(self . rear 1)% self . max _ size

否则：

引发IndexError(“队列已满异常”)

【动态顺序队列的入队操作】如果队列已满，首先申请新的空间，然后执行入队操作：

定义调整大小(自身):

新大小=2 *自我最大大小

新队列=[无] *新大小

对于范围内的I(self . max _ size):

新队列[i]=自我队列[i]

self.queue=新队列

self.max_size=new_size

定义入队(自身，数据):

if self.isfull():

self.resize()

self.queue[self.rear]=数据

self . rear=(self . rear 1)% self . max _ size

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

2.1.6 出队

如果队列不为空，删除并返回队列头元素：

定义出列(自身):

if not self.isempty():

result=self.queue[self.front]

self . front=(self . front 1)% self . max _ size

回送结果

否则：

引发IndexError(“空队列异常”)

2.1.7 求队头元素

如果队列不为空，将返回队列头元素：

定义头(自身):

if not self.isempty():

result=self.queue[self.front]

回送结果

否则：

引发IndexError(“空队列异常”)

2.2 链队列的实现

队列的另一种存储表示是链式存储结构，因此通常称为链式队列。入队操作通过在链表末尾插入元素来实现，出列操作通过从头删除节点来实现。

2.2.1 队列结点

队列和链表的节点实现没有区别：

类节点：

def __init__(self，data=None):

self.data=数据

self.next=无

def __str__(self):

返回字符串(self.data)

2.2.2 队列的初始化

在队列的初始化函数中，使其队列头指针前后指向None，并初始化队列长度：

类别队列：

def __init__(self):

self.front=无

self.rear=无

self.num=0

2.2.3 求队列长度

size的返回值用于计算队列长度。如果没有size属性，您需要遍历整个链表来获得队列长度：

定义大小(自身):

返回自我编号

2.2.4 判队列空

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

def isempty(self):

return self.num=0

2.2.5 入队

加入队列时，在队列末尾插入一个新元素，需要将尾指针向后指向新元素。如果队列是空的，您还需要将head指针指向这个元素：

定义入队(自身，数据):

节点=节点(数据)

如果self.front为None:

self.rear=node

self.front=self.rear

否则：

self.rear.next=node

self.rear=node

self.num=1

2.2.6 出队

如果队列不为空，则删除并返回队列头元素，需要更新队列头指针front以指向原队列头节点的后继节点。如果队列元素是队列中的最后一个节点，则队列尾指针rear被更新：

定义出列(自身):

if self.isempty():

引发IndexError(“空队列异常”)

result=self.front.data

self.front=self.front.next

self.num -=1

if self.isempty():

self.rear=self.front

回送结果

2.2.7 求队头元素

如果队列不为空，将返回队列头元素：

定义头(自身):

if self.isempty():

引发IndexError(“空队列异常”)

result=self.front.data

回送结果

2.3 队列的不同实现对比

队列不同实现的比较类似于堆栈。请参考《栈及其操作实现》。

3. 队列应用

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

3.1 顺序队列的应用

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

#初始化最大长度为5的队列

q=队列(5)

打印('队列为空？'，q.isempty())

对于范围(4)中的I:

Print ('enqueue元素：'，I)

q .排队(I)

打印(“队列已满？”，q.isfull())

Print ('queue head元素：'，q.head())

Print('队列长度为：'，q.size())

while not q.isempty():

Print ('dequeue element:'，q.dequeue())

测试程序输出结果如下：

队列空了？真实的

入队元素：0

注册要素：1

连接元素：2

连接元素：3

#队列中有一个空间被放弃，因此队列中有4个元素已满。

队列已满？真实的

团队头元素：0

队列长度为：4。

出队元素：0

出列元素：1

出列元素：2

出列元素：3

3.2 链队列的应用

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

#初始化新队列

q=队列()

打印('队列为空？'，q.isempty())

对于范围(4)中的I:

Print ('enqueue元素：'，I)

q .排队(I)

Print ('queue head元素：'，q.head())

Print('队列长度为：'，q.size())

while not q.isempty():

Print ('dequeue element:'，q.dequeue())

测试程序输出结果如下：

队列空了？真实的

入队元素：0

注册要素：1

连接元素：2

连接元素：3

团队头元素：0

队列长度为：4。

出队元素：0

出列元素：1

出列元素：2

出列元素：3

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

考虑经典的约瑟夫斯环问题。n个人围成一个圈，从第一个人开始数，M个就被淘汰了。重复以上过程，直到只剩下一个人，其余的都将被淘汰。

我们使用队列来模拟一个环，如下图所示。从队列的头部开始，队列头部的人被移出队列，并立即插入到队列的尾部。之后，这个人将再次等待，直到他到达队列的头部。出列，出列m-1次后，队列最前面的人出局(即第m个人)，然后开始新一轮游戏；重复此操作，直到队列中只剩下一个人(队列的大小为1)。

def约瑟夫斯(姓名列表，m):

queue=Queue()

对于名称列表中的名称：

queue.enqueue(名称)

while queue.size() 1:

对于范围内的I(m-1):

queue.enqueue(queue.dequeue())

queue.dequeue()

返回queue.head()

# n=6，m=5

结果=约瑟夫斯(['A '，' B '，' C '，' D '，' E '，' F']，5)

打印(“幸存者”，结果)

程序输出结果如下：

幸存者是a。

以上是Python数据结构的队列讲解细节。更多关于Python队列的信息，请关注我们的其他相关文章！

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

python列表数据结构,python队列的基本操作,Python数据结构之队列详解

目录

0. 学习目标

1. 队列的基本概念

1.1 队列的基本概念

1.2 队列抽象数据类型

1.3 队列的应用场景

2. 队列的实现

2.1 顺序队列的实现

2.2 链队列的实现

2.3 队列的不同实现对比

3. 队列应用

3.1 顺序队列的应用

3.2 链队列的应用

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

相关文章阅读