Python 队列（先进先出）|极客教程

Python 队列，本节将介绍仅使用Python标准库中的内置数据类型和类来实现FIFO队列数据结构，首先来回顾一下什么是队列。

队列是含有一组对象的容器，支持快速插入和删除的先进先出语义。插入和删除操作有时称为入队（enqueue）和出队（dequeue）。与列表或数组不同，队列通常不允许随机访问所包含的对象。
来看一个先进先出队列在现实中的类比。

想象在PyCon注册的第一天，一些Python高手等着领取会议徽章。新到的人依次进入会场并排队领取徽章，队列后面会有其他人继续排队。移除动作发生在队列前端，因为开发者领取徽章和会议礼品袋后就离开了。

另一种记住队列数据结构特征的方法是将其视为管道。

新元素（水分子、乒乓球等）从管道一端移向另一端并在那里被移除。当元素在队列中（想象成位于一根坚固的金属管中）时是无法接触的。唯一能够与队列中元素交互的方法是在管道后端添加新元素（入队）或在管道前端删除元素（出队）。

队列与栈类似，但删除元素的方式不同。
队列删除的是最先添加的项（先进先出），而栈删除的是最近添加的项（后进先出）。

在性能方面，实现合理的队列在插入和删除方面的操作预计耗时为。插入和删除是队列上的两个主要操作，在正确的实现中应该很快。

队列在算法中有广泛的应用，经常用于解决调度和并行编程问题。在树或图数据结构上进行宽度优先搜索（BFS）是一种简短而美丽的算法，其中就用到了队列。

调度算法通常在内部使用优先级队列。这些是特化的队列，其中元素的顺序不是基于插入时间，而是基于优先级。队列根据元素的键计算到每个元素的优先级。下一节详细介绍优先级队列以及它们在Python中的实现方式。

不过普通队列无法重新排列所包含的元素。就像在管道示例中一样，元素输入和输出的顺序完全一致。
Python中实现了几个队列，每种实现的特征略有不同，下面就来看看。

Python 队列列表——非常慢的队列

普通列表可以作为队列，但从性能角度来看并不理想。由于在起始位置插入或删除元素需要将所有其他元素都移动一个位置，因此需要的时间为。

因此不推荐在Python中凑合用列表作为队列使用（除非只处理少量元素）：

>>> q = []
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')

>>> q
['eat', 'sleep', 'code']

# 小心，这种操作很慢！
>>> q.pop(0)
'eat'

Python 队列 `collections.deque`——快速和稳健的队列

deque类实现了一个双端队列，支持在时间（非均摊）中从任一端添加和删除元素。由于deque支持从两端添加和移除元素，因此既可用作队列也可用作栈。

Python的deque对象以双向链表实现。这为插入和删除元素提供了出色且一致的性能，但是随机访问位于栈中间元素的性能很差，耗时为。

因此，默认情况下collections.deque是Python标准库中不错的队列型数据结构：

>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')

>>> q
deque(['eat', 'sleep', 'code'])

>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'

>>> q.popleft()
IndexError: "pop from an empty deque"

Python 队列 `queue.Queue`——为并行计算提供的锁语义

queue.Queue在Python标准库中以同步的方式实现，提供了锁语义来支持多个并发的生产者和消费者。

queue模块包含其他多个实现多生产者/多用户队列的类，这些队列对并行计算很有用。

在不同情况下，锁语义可能会带来帮助，也可能会导致不必要的开销。在后面这种情况下，最好使用collections.deque作为通用队列：

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')

>>> q
<queue.Queue object at 0x1070f5b38>

>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get_nowait()
queue.Empty

>>> q.get()
# 阻塞，永远停在这里……

Python 队列 `multiprocessing.Queue`——共享作业队列

multiprocessing.Queue作为共享作业队列来实现，允许多个并发worker并行处理队列中的元素。由于CPython中存在全局解释器锁（GIL），因此无法在单个解释器进程上执行某些并行化过程，使得大家都转向基于进程的并行化。

作为专门用于在进程间共享数据的队列实现，使用multiprocessing.Queue能够方便地在多个进程中分派工作，以此来绕过GIL的限制。这种类型的队列可以跨进程存储和传输任何可pickle的对象：

>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')

>>> q
<multiprocessing.queues.Queue object at 0x1081c12b0>

>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get()
# 阻塞，永远停在这里……

关键要点

Python核心语言及其标准库中含有几种队列实现。
列表对象可以用作队列，但由于性能较差，通常不建议这么做。
如果不需要支持并行处理，那么collections.deque是Python中实现FIFO队列数据结构的最佳选择。collections.deque是非常优秀的队列实现，具备期望的性能特征，并且可以用作栈（LIFO队列）。