用python写算法——队列笔记

1.队列定义

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列特征：

先进先出FIFO(frist-in, frist-out)

2.顺序队列

顺序队列：是一种用顺序表模拟实现的队列存储结构。
他的定义是用一组地址连续的存储单元，依次存放从队头到队尾的数据元素。

在这里插入图片描述
基本操作：

入队push
出队pop
队空
self.rear == self.front
队满
(self.rear + 1) % maxsize == self.front
如果用列表如何表示

class Queue():def __init__(self, size):#初始化一个空队列self.size = sizeself.front =0self.rear = 0self.queue = []def push(self, x):  # 入队操作if self.is_fulled():print("queue is full")return Falseelse:self.queue.append(x)self.rear = self.rear + 1return Truedef pop(self):  # 出队操作if self.is_empty():print("queue is empty")return Falseelse:# head = self.queue[self.front]# self.front = self.front + 1# return headreturn self.queue.pop(self.front)def is_fulled(self):return self.rear - self.front + 1 == self.sizedef is_empty(self):return self.front == self.reardef get_head(self):if self.is_empty():return Falseelse:return self.queue[self.front]def show(self):print(self.queue)q= Queue(10)
print("初始化队列为空",q.is_empty())for i in range(10):q.push(i)
q.show()
print("插入十个元素后，队满",q.is_fulled())
print(q.pop())
print(q.pop())

3.循环队列

将顺序队列的头尾相接。解决队列的空间浪费问题。
基本操作：

入队push
出队pop
队空
self.rear == self.front
队满
(self.rear + 1) % maxsize == self.front

在这里插入图片描述

class Queue:def __init__(self, size=100):self.queue = [0 for _ in range(size)]self.size = sizeself.rear = 0   # 队尾指针self.front = 0  # 队首指针# 入队def push(self, element):if not self.is_filled():self.rear = (self.rear + 1) % self.sizeself.queue[self.rear] = elementelse:raise IndexError("Queue is filled.")# 出队def pop(self):if not self.is_empty():self.front = (self.front + 1)% self.sizereturn self.queue[self.front]else:raise IndexError("Queue is empty.")# 判断队空def is_empty(self):return self.rear == self.front# 判断队满def is_filled(self):return (self.rear + 1) % self.size == self.frontdef show(self):print(self.queue)q = Queue(5)
for i in range(4):q.push(i)
print(q.show())
print(q.pop())