python队列_队列的定义及实现方法[通俗易懂]

python队列_队列的定义及实现方法[通俗易懂]队列_python队列

python队列_队列的定义及实现方法[通俗易懂]"

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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注