数据结构编程实践20讲(Python版)—04队列
本文目录
往期链接
01 数组 | 02 链表 | 03 栈 |
---|
04 队列 Queue
S1 说明
队列是一种先进先出(FIFO,First In First Out)的数据结构。数据在队列中的插入操作称为入队(enqueue),而删除操作称为出队(dequeue)。队列的特性和分类如下:
特征
- FIFO:最早进入队列的元素最先被移除。
- 动态大小:队列的大小可以根据需要动态扩展,具体取决于实现方式。
- 两端操作:通常只在队列的前端进行出队操作,在后端进行入队操作。
分类
- 普通队列:基本的FIFO队列。
- 循环队列:为了优化空间使用,使用循环数组实现的队列。
- 双端队列(Deque):可以在两端进行插入和删除操作。
- 优先队列:根据优先级进行出队的队列,出队的元素不一定是最早入队的元素。
S2 示例
普通队列
(1)基于collections包实现
from collections import deque
queue = 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 item
print("队列为空,无法出队")
return None
def is_empty(self):
return len(self.queue) == 0
def 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 = capacity
self.queue = [None] * capacity
self.front = -1
self.rear = -1
def is_empty(self):
return self.front == -1
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def enqueue(self, item):
if self.is_full():
print("队列已满,无法入队")
return
if self.is_empty():
self.front = 0
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
print(f"入队: {
item}")
def dequeue(self):
if self.is_empty():
print("队列为空,无法出队")
return None
item = self.queue[self.front]
if self.front == self.rear: # 队列只剩一个元素
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
print(f"出队: {
item}")
return item
def display(self):
if self.is_empty():
print("队列为空")
return
index = self.front
elements = []
while True:
elements.append(str(self.queue[<
原文地址:https://blog.csdn.net/qq_32882309/article/details/142602802
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!