本文目录
- 04 队列 Queue
- S1 说明
- S2 示例
- 普通队列
- 循环队列
- 双端队列
- 优先队列
- S3 问题：基于普通队列实现的打印机任务管理
- Python3程序
- S4 问题：使用循环队列管理玩家移动轨迹
- Python3程序
- S5 问题：使用双端队列来管理文档操作历史
- Python3程序
- S6 问题：使用优先队列管理车辆调度
- Python3程序
往期链接
| 01 数组 | 02 链表 | 03 栈 |
|---|
04 队列 Queue
S1 说明
队列是一种先进先出（FIFO，First In First Out）的数据结构。数据在队列中的插入操作称为入队（enqueue），而删除操作称为出队（dequeue）。队列的特性和分类如下：
特征
- FIFO：最早进入队列的元素最先被移除。
- 动态大小：队列的大小可以根据需要动态扩展，具体取决于实现方式。
- 两端操作：通常只在队列的前端进行出队操作，在后端进行入队操作。
分类
- 普通队列：基本的FIFO队列。
- 循环队列：为了优化空间使用，使用循环数组实现的队列。
- 双端队列（Deque）：可以在两端进行插入和删除操作。
- 优先队列：根据优先级进行出队的队列，出队的元素不一定是最早入队的元素。
S2 示例
普通队列
（1）基于collections包实现
from collections import dequequeue = deque()
queue.append('A') # 入队
queue.append('B') # 入队
print(queue.popleft()) # 出队
print(queue.popleft()) # 出队
结果
A
B
（2）基于python列表实现
class Queue:def __init__(self):self.queue = []def enqueue(self, item):self.queue.append(item)print(f"入队: {item}")def dequeue(self):if not self.is_empty():item = self.queue.pop(0)print(f"出队: {item}")return itemprint("队列为空，无法出队")return Nonedef is_empty(self):return len(self.queue) == 0def display(self):print("队列内容:", " <- ".join(map(str, self.queue)))# 示例
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.dequeue()
q.display()
结果
入队: 1
入队: 2
出队: 1
队列内容: 2
循环队列
使用固定大小的数组实现循环队列
class CircularQueue:def __init__(self, capacity):self.capacity = capacityself.queue = [None] * capacityself.front = -1self.rear = -1def is_empty(self):return self.front == -1def is_full(self):return (self.rear + 1) % self.capacity == self.frontdef enqueue(self, item):if self.is_full():print("队列已满，无法入队")returnif self.is_empty():self.front = 0self.rear = (self.rear + 1) % self.capacityself.queue[self.rear] = itemprint(f"入队: {item}")def dequeue(self):if self.is_empty():print("队列为空，无法出队")return Noneitem = self.queue[self.front]if self.front == self.rear: # 队列只剩一个元素self.front = self.rear = -1else:self.front = (self.front + 1) % self.capacityprint(f"出队: {item}")return itemdef display(self):if self.is_empty():print("队列为空")returnindex = self.frontelements = []while True:elements.append(str(self.queue[<