1、对列
队列（Queue） 是一种线性数据结构，遵循先进先出（FIFO）的原则。可以将队列想象成排队的场景，最先排队的人最先被服务。
2、队列的特点
先进先出（FIFO）： 队列遵循先进先出的原则，第一个进入队列的元素最先被移除。
两个操作端： 队列在队尾插入元素，在队首移除元素，两个操作端分别负责不同的操作。
顺序访问： 队列只能访问队首的元素，不能直接访问其他元素。
队列有两个主要操作：入队（enqueue） 和 出队（dequeue）。入队是将元素添加到队尾，出队是从队首移除元素
虽然可以用列表来实现队列，但由于列表在队首插入和删除元素的效率较低（时间复杂度为O(n)），不推荐在生产环境中使用列表来实现队列。
3、对列分类
- 单向对列：一端进，另一端出；
单向对列代码实现
import queue
q = queue.Queue()
q.put('a')
q.put('b')
print(q.get())
- 环形队列：
环形队列也是队列的一种数据结构, 也是在队头出队, 队尾入队;
只是环形队列的大小是确定的, 不能进行一个长度的增加, 当你把一个环形队列创建好之后, 它能存放的元素个数是确定的;
一般我们实现这个环形队列是通过一个连续的结构来实现的;
虽然环形队列在逻辑上是环形的, 但在物理上是一个定长的数组;
那如何在逻辑上形成一个环形的变化, 主要是在头尾指针当走到连续空间的末尾的时候, 它会做一个重置的操作
环形对列代码实现
class Queue:
def __init__(self,size=100):
self.queue = [0 for _ in range(size)]
self.size=size
self.rear = 0 #队尾指针
self.front = 0 #队首指针
def push(self,element):
if not self.is_filed():
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is empty.")
def pop(self):
if not self.is_empty():
self.front = (self.front + 1) % self.size
return self.queue[self.front]
else:
raise IndexError("Queue is empty.")
def is_empty(self): #判断队空
return self.rear == self.front
def is_filed(self): #判断队满
return (self.rear+1)%self.size == self.front
q=Queue(5)
for i in range(4):
q.push(i)
print(q.pop())
q.push(4)
- 双向队列：双向队列的两端都支持进队和出队操作
双向对列代码实现
from collections import deque
q = deque([1,2,3], 5) #第二个参数，最大长度，队满自动出队
q.append(1) #队尾进队
q.popleft() #队首进队
q.appendleft(1) #队首进队
q.pop() #队尾出队
4、队列的应用场景
任务调度： 队列常用于任务调度器中，将任务按顺序排队执行。
广度优先搜索（BFS）： 在图或树的广度优先搜索算法中，队列被用作辅助数据结构。
缓存系统： 队列可以用于实现缓存系统中的 FIFO 缓存策略。
多线程编程： 在多线程环境中，队列用于在线程间传递数据或任务
参考：
https://blog.csdn.net/weixin_44752186/article/details/141955190
https://blog.csdn.net/qq_48711800/article/details/118962516
https://www.cnblogs.com/ranzhong/p/12438841.html