当前位置：首页 > news >正文

数据结构编程实践20讲(Python版)—04队列

news 来源：原创 2024/9/28 18:04:25

本文目录

- 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[<