队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,是一种操作受限制的线性表。
进行插入操作的端称为队尾,进行删除操作的端称为队头,核心概念是先进先出
Queue的安装
import queue #python内部自带直接导入即可
单端队列(LILO)的基本使用
from queue import Queue
q = Queue() # 创建队列对象
q.put(1) # 队列尾部插入元素
q.put(2)
q.put(3)
print(q.queue) # 查看队列中的所有元素
a = q.get() # 返回并删除队列头部元素
print(a)
print(q.queue) # 运行结果deque([2,3])
#遍历队列,先删除再遍历。
q1 = q
while not q1.empty():
print(q1.get())
常用基本方法:
方法 | 作用 |
---|---|
Queue.qsize() | 返回队列的大小 |
Queue.empty() | 如果队列为空,返回True,反之False |
Queue.full() | 如果队列满了,返回True,反之False,Queue.full 与 maxsize 大小对应 |
Queue.get([block[, timeout]]) | 获取队列,timeout等待时间 |
Queue.get_nowait() | 相当于Queue.get(False),非阻塞方法 |
Queue.put(item) | 写入队列,timeout等待时间 |
Queue.task_done() | 在完成一项工作之后,Queue.task_done()函数向任务已经完成的队列发送一个信号。每个get()调用得到一个任务,接下来task_done()调用告诉队列该任务已经处理完毕。 |
Queue.join() | 实际上意味着等到队列为空,再执行别的操作 |
时间复杂度:
- 访问O(N)
- 查找O(N)
- 插入O(1)
- 删除O(1)
Python双端队列常用操作
1.创建队列
from collections import deque
#创建队列
queue=deque() #这里创建的是双端的
2.添加元素
#append()方法 O(1)
queue.append(1)
queue.append(2)
queue.append(3)
print(queue) #[1,2,3]
3.获取即将出队的元素
# O(1)
temp1=queue[0] #因为队列先进先出的性质 这里即将出队的也就是第一个元素 即索引为0的元素
print(temp1) #1
#peek()方法也可获得队头元素
4.删除即将出队的元素
#O(1)
temp2=queue.popleft() #因为先进来的是在左边 后进来的是在右边 由此使用popleft()
#另外由于deque()是双端队列 由此其实在左右两边都可以删除 如果要删除右边进来的话 使用popright() 但我们一般默认单端队列 这样的话就考虑右进左出
print(temp2) #1 popleft除了删掉了队列里这个值之外 还把这个值传递了出来
print(queue) #[2,3]
5.判断队列是否为空、队列的长度
# O(1)
len(queue)==0
6.遍历队列
#O(N) 之前提到了popleft的用法 因此这里遍历其实是边遍历边删除的操作 通过输出值来遍历队列的
while len(queue)!=0:
temp=queue.popleft()
print(temp)