队列的实现方式—Python数据结构（三）

数据结构（三）"/>

队列的实现方式—Python数据结构（三）

队列

1. 定义

队列是一种常见的数据结构，用于按照先进先出（FIFO）的原则管理数据项。在Python中，有多种方法可以实现队列，其中最常见的包括使用列表（list）和使用标准库中的 queue 模块。队列通常用于解决需要按照特定顺序处理数据项的问题，例如任务调度、数据缓冲、事件处理等。
队列是限制在两端进行插入和删除操作操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”。
队列类似于一条管道，需要注意的是：队列都是在内存中操作，进程退出，队列清空，另外，队列也是一个阻塞的形态。

2. 特点

• 队列只能在队头和队尾进行数据操作

• 队列模型具有先进先出或者叫做后进后出的规律。

3. 队列的代码实现

队列的操作有入队，出队判断队列的空满等操作。

• 使用列表(顺序存储)实现队列：squeue.py
• 链式存储代码实现队列：lqueue.py
• 使用 queue实现队列：queuetest.py
• 使用 deque实现队列：dequetest.py

3.1 列表实现队列(顺序存储)

squeue.py

# @Author : Kql
# @Time : 2023/10/17 14:54
"""
squeue队列的顺序存储
思路分析：
1. 基于列表完成数据存储。
2. 通过封装规定数据操作。
"""# 自定义异常类
class QueueError(Exception):pass# 队列操作
class SQueue:def __init__(self):self._elems = []# 判定队列为空def is_empty(self):return self._elems == []# 入队,列表的尾部定义为队尾def enqueue(self, val):self._elems.append(val)# 出队,列表的第一个元素def dequeue(self):if not self._elems:raise QueueError("Queue is empty")return self._elems.pop(0)from sstack import *# 如何将出队的数据进行翻转,即先出队入栈，之后在出栈入队
def convert_queue():sqe = SQueue()for i in range(10):sqe.enqueue(i)st = SStack()# 出队入栈while not sqe.is_empty():st.push(sqe.dequeue())# 出栈入队while not st.is_empty():sqe.enqueue(st.pop())# 直接出队while not sqe.is_empty():print(sqe.dequeue())if __name__ == '__main__':# 如何将出队的数据进行翻转,即先出队入栈，之后在出栈入队convert_queue()#正常的队列顺序存储sq = SQueue()sq.enqueue(10)sq.enqueue(20)sq.enqueue(30)while not sq.is_empty():print(sq.dequeue())

3.2 链式存储代码实现队列

lqueue.py

# @Author : Kql
# @Time : 2023/10/17 16:05
"""
lqueue.py 链式队列
思路分析：
1. 基于链表构建队列模型
2. 链表的开端作为队头，结尾位置作为队尾。
3. 单独定义队尾标记，避免每次插入数据遍历。
4. 队头和队尾重叠时认为队列为空。
"""# 自定义异常类
class QueueError(Exception):pass# 节点类
class Node:def __init__(self, val, next=None):self.val = valself.next = nextclass LQueue:def __init__(self):# 定义队头和队尾的属性变量self.front = self.rear = Node(None)# 判定队列为空def is_empty(self):return self.front == self.rear# 入队def enqueue(self, val):self.rear.next = Node(val)self.rear = self.rear.next# 队列出队def dequeue(self):if self.front == self.rear:raise QueueError("Queue is empty")# 此时front节点已经将第一个节点出队了，只是明面上指向一个地址节点。self.front = self.front.nextreturn self.front.valif __name__ == '__main__':sq = LQueue()sq.enqueue(10)sq.enqueue(20)sq.enqueue(30)while sq.is_empty():print(sq.dequeue())

3.3 使用 queue实现队列

queuetest.py

import queue# 创建一个队列
q=queue.Queue(5)    #如果不设置长度,默认为无限长
print(q.maxsize)    #注意没有括号# 添加元素到队列
q.put(1)
q.put(2)
q.put(3)# 从队列中取出元素
item = q.get()
print(item)  
# 输出: 1

3.4 使用 deque实现队列

Deque 类实现了一个双端队列（double-ended queue），支持从队列两端添加和取出元素。
dequetest.py

from collections import deque
#创建一个 deque 对象：
my_deque = deque()#在队列头部添加元素：使用 appendleft() 方法。
my_deque.appendleft(1)
my_deque.appendleft(2)#在队列尾部添加元素：使用 append() 方法。
my_deque.append(3)
my_deque.append(4)#从队列头部取出元素：使用 popleft() 方法。
item = my_deque.popleft()  # 取出并移除队列头部的元素
print(item)  # 输出: 2#从队列尾部取出元素：使用 pop() 方法。
item = my_deque.pop()  # 取出并移除队列尾部的元素
print(item)  # 输出: 4

使用 deque 类可以使队列的两端操作非常高效，因为它是双向链表的实现，允许在常数时间内进行这些操作。这对于需要频繁从队列两端添加和删除元素的问题非常有用，如广度优先搜索、循环缓冲区等。