Python deque 双向队列
说明
《Python 教程》 持续更新中，提供建议、纠错、催更等加作者微信: gairuo123（备注：pandas教程）和关注公众号「盖若」ID: gairuo。跟作者学习，请进入 Python学习课程。欢迎关注作者出版的书籍：《深入浅出Pandas》 和 《Python之光》。
Deque（发音是 “deck”，Double-Ended Queue）是一个双向队列。Deque 支持线程安全，内存高效添加 (append) 和弹出 (pop)，从两端都可以，两个方向的大概开销都是 O(1) 复杂度。
什么是 Deque
列表是几乎所有 Python 的主要工作方式之一，然而，在某些情况下，选择 deque 可以带来更快的性能。deque 是双端队列的缩写，这就是为什么它被称为双端队列。Double End 表示它支持从两端添加和删除元素。
Python 的 Deque 结构为 class collections.deque([iterable[, maxlen]])，可以选择设置一个最大的长度 maxlen，如果 maxlen 没有指定或者是 None ，deques 可以增长到任意长度。否则，deque 就限定到指定最大长度。一旦限定长度的 deque 满了，当新项加入时，同样数量的项就从另一端弹出。限定长度 deque 提供类似 Unix filter tail 的功能。它们同样可以用与追踪最近的交换和其他数据池活动。
相比于 list 实现的队列，deque 实现拥有更低的时间和空间复杂度，而且 deque 既可以表示队列又可以表示栈。
性能
虽然 list 对象也支持类似操作，不过这里优化了定长操作和 pop(0) 和 insert(0, v) 的开销。它们引起 O(n) 内存移动的操作，改变底层数据表达的大小和位置。它返回一个新的双向队列对象，从左到右初始化(用方法 append()) ，从 iterable （迭代对象) 数据创建。如果 iterable 没有指定，新队列为空。
为什么 list 慢：
- 添加方法
append()和insert(index,value)，需要去遍历 list 才行，所以时间复杂度为 o(N) - 删除有
del names[index]、pop()、pop(index)、remove(value)，除了删除列表末尾元素方法pop()之外，剩下的要遍历 list，时间复杂度是 o(N)
deque 为了在两端高效实现插入和删除操作的双向列表，适合用于队列和栈，除了实现 list 的 append() 和 pop() 外，还支持 appendleft() 和 popleft()，这样就可以非常高效地往头部或者尾部添加或删除元素。
Python 标准库中包含了四种队列，分别是 queue.Queue、asyncio.Queue、multiprocessing.Queue、collections.deque，deque 是标准库 collections 中的，也是最好用的。
特性
一些常用的特别操作：
队列与列表的方法区别：
操作
以下是一些相关的操作：
import collections
# 定义长度为 4
d = collections.deque('abc', maxlen=4)
d
# deque(['a', 'b', 'c'])
# 从左插入 0
d.appendleft(0)
d
# deque([0, 'a', 'b', 'c'])
# 队列长度
d.maxlen
# 4
# 左边追加
d.append('c')
d
# deque(['a', 'b', 'c', 'c'])
# 元素等于 c 的个数
d.count('c')
# 2
# 右端增加一个序列，支持 iterable
d.extend(range(2))
d
# deque(['c', 'c', 0, 1])
# 左端增加一个序列，支持 iterable
# 注：左侧增加时顺序将被反过来添加
d.extendleft(['x', 'y'])
d
# deque(['y', 'x', 'c', 'c'])
# 返回值的第一个索引，未找到则引发 ValueError
# d.index("c",0,4) #指定查找的区间
d.index('c')
# 2
# 在位置 i 插入 x
# 插入会导致超出长度 maxlen 的话，就引发一个 IndexError
d.insert(2, 'z')
# IndexError: deque already at its maximum size
# 移除最右侧的那一个并返回
# 如没有元素，引发一个 IndexError
d.pop()
# 'c'
d
# deque(['y', 'x', 'c'])
# 移除最左侧的那一个并返回
# 如没有元素，引发一个 IndexError
d.popleft()
# 'y'
d
# deque(['x', 'c'])
# 移除找到的第一个 value
# 如果没有的话就引发 ValueError
d.remove('c')
d
# deque(['x'])
# 两个队列拼接
d = d + collections.deque(['y', 'z'])
d
# deque(['x', 'y', 'z'])
# 逆序排列, 返回 None
d.reverse()
d
# deque(['z', 'y', 'x'])
d[0]
# 'z'
d[-1]
# 'x'
# 向右循环移动 n 步
# 如果 n 是负数，就向左循环
d.rotate(2)
d
# deque(['y', 'x', 'z'])
d.clear()
# 移除所有元素，使其长度为0
d
# deque([])
应用
以下是几个官方文档的应用例子：
类似Unix tail 过滤功能
def tail(filename, n=10):
'Return the last n lines of a file'
with open(filename) as f:
return deque(f, n)
近期添加元素的序列
维护一个近期添加元素的序列，通过从右边添加和从左边弹出：
def moving_average(iterable, n=3):
# moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
# http://en.wikipedia.org/wiki/Moving_average
it = iter(iterable)
d = deque(itertools.islice(it, n-1))
d.appendleft(0)
s = sum(d)
for elem in it:
s += elem - d.popleft()
d.append(elem)
yield s / n
轮询调度器
一个 轮询调度器 可以通过在 deque 中放入迭代器来实现。值从当前迭代器的位置0被取出并暂存(yield)。 如果这个迭代器消耗完毕，就用 popleft() 将其从对列中移去；否则，就通过 rotate() 将它移到队列的末尾。
def roundrobin(*iterables):
"roundrobin('ABC', 'D', 'EF') --> A D E B F C"
iterators = deque(map(iter, iterables))
while iterators:
try:
while True:
yield next(iterators[0])
iterators.rotate(-1)
except StopIteration:
# Remove an exhausted iterator.
iterators.popleft()
rotate() 方法提供了一种方式来实现 deque 切片和删除。 例如， 一个纯的Python del d[n] 实现依赖于 rotate() 来定位要弹出的元素
def delete_nth(d, n):
d.rotate(-n)
d.popleft()
d.rotate(n)
要实现 deque 切片， 使用一个类似的方法，应用 rotate() 将目标元素放到左边。通过 popleft() 移去老的条目（entries），通过 extend() 添加新的条目， 然后反向 rotate。这个方法可以最小代价实现命令式的栈操作，诸如 dup, drop, swap, over, pick, rot, 和 roll 。
参考
- https://docs.python.org/zh-cn/3/library/collections.html#collections.deque
更新时间：Oct. 9, 2021, 8:14 a.m. 标签：python 队列
