1.队列

特征：
先进先出 FIFO（First in First out）
只能从队头离开队列
只能从队尾进入队列

缺点：
队列的查找慢，从头到尾一个一个查找

2.循环队列

手写队列一般采用循环队列，避免溢出
用一组连续的存储单元依次存放队列元素
head指示队列头元素；rear指向尾元素
当head和rear走到底时，下一步回到开始的位置，从而在这组连续空间内循环

3.python队列的三种实现

队列：Queue
列表：list
双端队列：deque
性能：list最慢，Queue较慢，deque比Queue快10倍以上

4.Queue的操作

q.put() 从队尾插入
q.get() 从队头删除，并返回
q.qsize() 队列大小
q.empty() 队列是否为空

#示例
from queue import *
n=10
q=Queue()    #定义一个新的队列
for i in range(n):
    q.put(i)
print(q.qsize())
print(q.empty())
for i in range(n):
    a=q.get()
    print(a,end=' ')
print()   #打印换行
print(q.qsize())
print(q.empty())

#输出结果：
10
False
0 1 2 3 4 5 6 7 8 9 
0
True

5.list模拟队列操作

q.append() 从队尾插入
del q[0] 删除队头
len(q) 队列大小
if not q 队列为空

n=10
q=[]
for i in range(n):
    q.append(i)
print(q)
print(len(q))
for i in range(n):
    print(q[0],end=' ')
    del q[0]        #删除队头
print()
print(len(q))
if not q:
    print('empty')

#输出结果：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
10
0 1 2 3 4 5 6 7 8 9 
0
empty

6.deque的操作

append 入队，从队列右端（队尾）插入
appendleft 入队，从队列左端（队头）插入
pop 出队，从队列右端（队尾）删除一个元素，并返回该元素
popleft 出队，从队列左端（队头）删除一个元素，并返回该元素
len() 队列大小
if q 判断空

from collections import *
n=10
q=deque()
for i in range(n):
    q.append(i)
print(len(q))
if q:
    print('not empty')
for i in range(n):
    a=q.popleft()
    print(a,end=' ')
print()
print(len(q))
if not q:
    print('empty')

#输出结果：
10
not empty
0 1 2 3 4 5 6 7 8 9 
0
empty

7.性能比较

queue：

from queue import *
from time import *
start=time()
n=100000
q=Queue()
for i in range(n):
    q.put(i)
for i in range(n):
    q.get()
end=time()
print("time=",end-start)

#输出：
time= 0.30121326446533203

list：

from time import *
start=time()
n=100000
q=[]
for i in range(n): q.append(i)
for i in range(n): del q[0]
end=time()
print("time=",end-start)

#输出：
time= 9.71581745147705

deque：

from collections import *
from time import *
start=time()
n=100000
q=deque()
for i in range(n):q.append(i)
for i in range(n):q.popleft()
end=time()
print("time=",end-start)

#输出：
time= 0.014119148254394531

比较结果显而易见啦！

8.优先队列

一种特殊的队列，特点是最优数据（最大值或最小值）始终位于队列头部。
效率高：
新数据插入队列后，计算新的最优队头，计算复杂度是O(logn);
弹出最优队头后，计算新的最优队头，计算复杂度也是O(logn).
二叉堆实现：
从堆顶弹出最小值，将堆底数移到堆顶，一层一层进行比较，如果下层数更小则交换，复杂度为O(log n)
新元素插入堆，先插入堆底，再逐层和上级比较，若小则交换，复杂度为O(logn)

python优先队列PriorityQueue
基本操作：

pq=queue.PriorityQueue() #定义
pq.put([priority,value]) #进队列
pq.get() #取出队首
pq.empty() #判断空
pq.qsize() #队列大小

注意：put()的第一个参数priority表示数据的优先级，第二个参数value是值，如果只有一个参数，同时表示优先级和值，值越小优先级越高，队首总是最小值

示例：

import queue
pq=queue.PriorityQueue()
pq.put(1)
pq.put(7)
pq.put(5)
print(pq.qsize())
while not pq.empty():
    print(pq.get(),end=' ')

#输出结果：
3
1 5 7 

只一个参数，同时代表优先级和值，依次输出队首，从小到大

import queue
pq=queue.PriorityQueue()
pq.put([1,'abc'])
pq.put([7,998])
pq.put([5,True])
print(pq.qsize())
while not pq.empty():
    print(pq.get(),end=' ')

#输出结果：
3
[1, 'abc'] [5, True] [7, 998] 

两个参数，value可以是各种数据类型