python学习笔记（14）算法（7）队列
队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。
我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。
一、队列的常用操作
一、入队（Enqueue）
- 操作含义
将元素添加到队列的末尾。
2.示例（以Python为例，使用列表来简单模拟队列）
-
queue = [] element = 10 queue.append(element) print(queue) # [10]
二、出队（Dequeue）
- 操作含义
- 移除队列头部的元素，并返回该元素的值。
- 示例（以Python为例）
-
queue = [10, 20, 30] front_element = queue.pop(0) print(front_element) # 10 print(queue) # [20, 30]
-
三、查看队首元素（Peek）
- 操作含义
- 返回队列头部的元素，但不移除它。
- 示例（以Python为例）
-
queue = [10, 20, 30] front_element = queue print(front_element) # 10 print(queue) # [10, 20, 30]
-
四、判断队列是否为空（Is Empty）
- 操作含义
- 检查队列中是否有元素，如果没有元素则返回True，否则返回False。
- 示例（以Python为例）
-
queue = [] is_empty = len(queue)==0 print(is_empty) # True queue = [10] is_empty = len(queue)==0 print(is_empty) # False
-
五、获取队列大小（Size）
- 操作含义
- 返回队列中元素的数量。
- 示例（以Python为例）
-
queue = [10, 20, 30] size = len(queue) print(size) # 3
-
二、具体实现
1.基于链表的实现
# 首先定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedListQueue:
""" 基于链表实现的队列"""
def __init__(self):
""" 构造方法"""
self._front = None # 头节点front
self._rear = None # 尾节点rear
self._size = 0
def size(self) -> int:
""" 获取队列的长度"""
return self._size
def is_empty(self) -> bool:
""" 判断队列是否为空"""
return self._size == 0
def push(self, num: int):
""" 入队"""
# 在尾节点后添加num
node = ListNode(num)
# 如果队列为空，则令头、尾节点都指向该节点
if self._front is None:
self._front = node
self._rear = node
else:
self._rear.next = node
self._rear = node
self._size += 1
def pop(self) -> int:
""" 出队"""
if self.is_empty():
raise IndexError("队列为空")
num = self._front.val
# 删除头节点
self._front = self._front.next
self._size -= 1
if self._front is None:
self._rear = None
return num
def peek(self) -> int:
""" 访问队首元素"""
if self.is_empty():
raise IndexError("队列为空")
return self._front.val
def to_list(self) -> list[int]:
""" 转化为列表用于打印"""
queue = []
temp = self._front
while temp:
queue.append(temp.val)
temp = temp.next
return queue2.基于数组的实现
在数组中删除首元素的时间复杂度为 𝑂(𝑖) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。
我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义
rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。
class ArrayQueue:
""" 基于环形数组实现的队列"""
def __init__(self, size: int):
""" 构造方法"""
self._nums = * size
# 用于存储队列元素的数组
self._front = 0
# 队首指针，指向队首元素
self._size = 0
# 队列长度
def capacity(self) -> int:
""" 获取队列的容量"""
return len(self._nums)
def size(self) -> int:
""" 获取队列的长度"""
return self._size
def is_empty(self) -> bool:
""" 判断队列是否为空"""
return self._size == 0
def push(self, num: int):
""" 入队"""
if self._size == self.capacity():
raise IndexError("队列已满")
# 计算队尾指针，指向队尾索引 + 1
# 通过取余操作实现 rear 越过数组尾部后回到头部
rear = (self._front + self._size) % self.capacity()
# 将 num 添加至队尾
self._nums[rear] = num
self._size += 1
def pop(self) -> int:
""" 出队"""
if self.is_empty():
raise IndexError("队列为空")
num = self.peek()
# 队首指针向后移动一位，若越过尾部，则返回到数组头部
self._front = (self._front + 1) % self.capacity()
self._size -= 1
return num
def peek(self) -> int:
""" 访问队首元素"""
if self.is_empty():
raise IndexError("队列为空")
return self._nums[self._front]
def to_list(self) -> list[int]:
""" 返回列表用于打印"""
res = []
index = self._front
for _ in range(self._size):
res.append(self._nums[index])
index = (index + 1) % self.capacity()
return res原文地址：https://blog.csdn.net/m0_74370400/article/details/144093099
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！