Python中的队列结构及其用法

Python标准库queue提供了LILO队列类Queue、LIFO队列类LifoQueue、优先级队列类PriorityQueue，标准库collections提供了双端队列。

>>> from queue import Queue    #LILO队列

>>> q = Queue()  #创建队列对象

>>> q.put(0)  #在队列尾部插入元素

>>> q.put(1)

>>> q.put(2)

>>> print(q.queue)  #查看队列中所有元素

deque([0, 1, 2])

>>> q.get() #返回并删除队列头部元素

0

>>> q.get()

1

>>> q.queue

deque([2])

>>> q.get()

2

>>> from queue import LifoQueue #LIFO队列

>>> q = LifoQueue()  #创建LIFO队列对象

>>> q.put(1)   #在队列尾部插入元素

>>> q.put(2)

>>> q.put(3)

>>> q.queue  #查看队列中所有元素

[1, 2, 3]

>>> q.get() #返回并删除队列尾部元素

3

>>> q.queue

[1, 2]

>>> q.get()

2

>>> q.queue

[1]

>>> from queue import PriorityQueue   #优先级队列

>>> q = PriorityQueue() #创建优先级队列对象

>>> q.put(3)  #插入元素

>>> q.put(8)  #插入元素

>>> q.put(100)

>>> q.queue  #查看优先级队列中所有元素

[3, 8, 100]

>>> q.put(1)  #插入元素，自动调整优先级队列

>>> q.put(2)

>>> q.queue

[1, 2, 100, 8, 3]

>>> q.get() #返回并删除优先级最低的元素

1

>>> q.get()

2

>>> q.get()

3

>>> q.get()

8

>>> q.get()

100

>>> from collections import deque

>>> q = deque(maxlen=5)  #创建双端队列

>>> for item in [3, 5, 7, 9, 11]: #添加元素

q.append(item)

>>> q.append(13)  #队列满，自动溢出

>>> q

deque([5, 7, 9, 11, 13], maxlen=5)

>>> q.append(15)

>>> q

deque([7, 9, 11, 13, 15], maxlen=5)

>>> q.appendleft(5)  #从左侧添加元素，右侧自动溢出

>>> q

deque([5, 7, 9, 11, 13], maxlen=5)

>>> q.popleft()  #弹出并返回最左端元素

5

>>> q

deque([7, 9, 11, 13], maxlen=5)

>>> q.pop() #弹出并返回最右端元素

13

>>> q

deque([7, 9, 11], maxlen=5)

>>> q.insert(2,10)  #在中间位置插入元素

>>> q

deque([7, 9, 10, 11], maxlen=5)

>>> q

deque([7, 9, 10, 11], maxlen=5)

>>> q += [1, 2]  #追加多个元素

>>> q

deque([9, 10, 11, 1, 2], maxlen=5)

>>> q.pop()

2

>>> q.pop()

1

>>> q

deque([9, 10, 11], maxlen=5)

>>> q *= 2  #序列重复

>>> q

deque([10, 11, 9, 10, 11], maxlen=5)

>>> q.count(10) #返回元素出现次数

2

>>> q.rotate(2)  #循环右移2个元素

>>> q

deque([10, 11, 10, 11, 9], maxlen=5)

>>> q.rotate(-2)  #循环左移2个元素

>>> q

deque([10, 11, 9, 10, 11], maxlen=5)