1.队列存储结构

1.1队列基本介绍

• 队列的两端都"开口"，要求数据只能从一端进，从另一端出，如图 1 所示：

• 进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。
• 队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。
• 拿图1中的队列来说，从数据在队列中的存储状态可以分析出，元素1 最先进队，其次是元素2，最后是元素3。此时如果将元素3出队，根据队列 “先进先出” 的特点，元素1 要先出队列，元素2 再出队列，最后才轮到元素3 出队列。
• 因此，数据从表的一端进，从另一端出，且遵循 “先进先出” 原则的线性存储结构就是队列。
• 实际生活中，队列的应用随处可见，比如排队买XXX、医院的挂号系统等，采用的都是队列结构。

1.2队列的实现方式

队列存储结构的实现有以下两种方式：

• 顺序队列：在顺序表的基础上实现的队列结构
• 链队列：在链表的基础上实现的队列结构

2.顺序队列

2.1顺序队列的介绍

顺序队列，即采用顺序表模拟实现的队列结构。

• 我们知道，队列具有以下两个特点：
  • 数据从队列的一端进，另一端出
  • 数据的入队和出队遵循"先进先出"的原则

因此，只要使用顺序表按以上两个要求操作数据，即可实现顺序队列。首先来学习一种最简单的实现方法

2.2顺序队列的简单实现

• 由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素，如图 1 所示：

• 由于顺序队列初始状态没有存储任何元素，因此 top指针和 rear指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。
• 在图1 的基础上，当有数据元素进队列时，对应的实现操作是将其存储在指针rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。

例如，在图1 基础上将 {1,2,3,4} 用顺序队列存储的实现操作如图2 所示：

在图2 基础上，顺序队列中数据出队列的实现过程如图3所示：

2.3代码实现

实现基本功能：

• 初始化队列
• 判断队列是否为空
• 返回队头元素
• 返回队列的长度
• 入队 : 添加元素到队尾
• 出队 : 删除队头元素
• 遍历队列
• 清空队列

# 本次顺序队列定义及相关函数较多使用python自身所带的列表和函数
class Queue:#队列初始化def __init__(self):self.items = []#判断队列是否为空def is_empty(self):return self.items == []#元素入队def enter_queue(self, item):self.items.insert(0, item)#队首元素出队def go_queue(self):return self.items.pop()#返回队列长度def size(self):return len(self.items)#清空队列def clear(self):self.items.clear()#获取队首元素def getTop(self):return self.items[self.size()-1]#遍历队列def display(self):return self.itemsif __name__ == '__main__':q = Queue()print("---------------------")print("初始化后的队列：", q)print("---------------------")print("当前队列是否为空：", q.is_empty())print("---------------------")print("入队前队内元素为：", q.display())q.enter_queue(5)q.enter_queue(10)q.enter_queue(11)print("入队后队内元素为：", q.display())print("---------------------")print("当前队首元素为：", q.getTop())print("---------------------")print("出队前队内元素为：", q.display())q.go_queue()print("出队后队内元素为：", q.display())print("---------------------")print("当前队列长度为：", q.size())print("---------------------")print("清空前队内元素为：", q.display())q.clear()print("清空后队内元素为：", q.display())

---------------------
初始化后的队列： <__main__.Queue object at 0x0000017D90EB8460>
---------------------
当前队列是否为空： True
---------------------
入队前队内元素为： []
入队后队内元素为： [11, 10, 5]
---------------------
当前队首元素为： 5
---------------------
出队前队内元素为： [11, 10, 5]
出队后队内元素为： [11, 10]
---------------------
当前队列长度为： 2
---------------------
清空前队内元素为： [11, 10]
清空后队内元素为： []

3.链式队列和基本操作

• 使用链表实现的队列存储结构
• 需要创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如图 1 所示：

• 图1 所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。
• 在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。

3.1链式队列数据入队

链队队列中，当有新的数据元素入队，只需进行以下 3步操作：

• 将该数据元素用节点包裹，例如新节点名称为 elem；
• 与 rear指针指向的节点建立逻辑关系，即执行 rear->next=elem；
• 最后移动 rear指针指向该新节点，即 rear=elem；

由此，新节点就入队成功了。

例如，在图1 的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如图2 所示:

3.2链式队列数据出队

当链式队列中，有数据元素需要出队时，按照 “先进先出” 的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里，我们先学习如何将队头元素出队。

链式队列中队头元素出队，需要做以下 3 步操作：

• 通过 top 指针直接找到队头节点，创建一个新指针p 指向此即将出队的节点；
• 将 p 节点（即要出队的队头节点）从链表中摘除；
• 释放节点p，回收其所占的内存空间；

例如，在图 2)的基础上，我们将元素 1 和 2 出队，则操作过程如图 3 所示：

3.3队列的链式表示和实现

实现基本功能：

• 初始化队列
• 判断队列是否为空
• 返回队头元素
• 返回队列的长度
• 入队: 添加元素到队尾
• 出队: 删除队头元素
• 遍历队列
• 清空队列

'''
1. 队列特点：先进先出，队尾入队操作，队头出队操作
2. 使用单链表实现：尾部添加节点(入队),头部删除节点(出队)操作
3. 这是一个带有头节点的队列，front指针始终指向头节点
'''#定义链式队列节点
class Node:def __init__(self, value):self.data = valueself.next = None# 定义队列函数
class Queue:#队列初始化def __init__(self):self.front = Node(None)self.rear = self.front#判断队列是否为空def is_empty(self):return self.rear == self.front# 元素入队def enQueue(self, element):n = Node(element)self.rear.next = nself.rear = n# 队列元素出队def deQueue(self):if self.is_empty():print("队列为空")returntemp = self.front.nextself.front.next = self.front.next.nextif self.rear == temp:self.rear = self.frontdel temp# 获取队首元素def gettop(self):if self.is_empty():print("队列为空")returnreturn self.front.next.data# 遍历队列def display(self):if self.is_empty():print("队列为空")returncur = self.front.nextwhile cur != None:print(cur.data, end=" ")cur = cur.nextprint()# 清空队列def clear(self):while self.front.next != None:temp = self.front.nextself.front.next = temp.nextself.rear = self.front# 返回队列长度def size(self):cur = self.front.nextcount = 0while cur != None:count += 1cur = cur.nextreturn countqueue = Queue()
print("-----------------------------")
print("初始化的链式队列：", queue)
print("-----------------------------")
print("当前队列是否为空：", queue.is_empty())
print("-----------------------------")
print("入队前队列元素为：", end="")
queue.display()
queue.enQueue(1)
queue.enQueue(47)
queue.enQueue("tr")
print("入队后队列元素为：", end="")
queue.display()
print("-----------------------------")
print("当前队列长度为：", queue.size())
print("-----------------------------")
print("当前队列头部元素为：", queue.gettop())
print("-----------------------------")
print("出队前队列元素为：", end="")
queue.display()
queue.deQueue()
print("出队后队列元素为：", end="")
queue.display()
print("-----------------------------")
print("当前队列是否为空：", queue.is_empty())
print("-----------------------------")
print("清空后队列元素为：", end="")
queue.display()
queue.clear()
print("出队后队列元素为：", end="")
queue.display()
print("-----------------------------")

-----------------------------
初始化的链式队列： <__main__.Queue object at 0x000001BA943A9A00>
-----------------------------
当前队列是否为空： True
-----------------------------
入队前队列元素为：队列为空
入队后队列元素为：1 47 tr 
-----------------------------
当前队列长度为： 3
-----------------------------
当前队列头部元素为： 1
-----------------------------
出队前队列元素为：1 47 tr 
出队后队列元素为：47 tr 
-----------------------------
当前队列是否为空： False
-----------------------------
清空后队列元素为：47 tr 
出队后队列元素为：队列为空
-----------------------------