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可以是各种数据类型
今天的文章python队列_队列的定义及实现方法[通俗易懂]分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/77559.html