队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（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)