python deque

# Python deque：看似简单却藏着不少门道

很多人刚开始接触Python时，list几乎是万能的。装数据、切片、append、pop，用起来顺手得很。但当你开始处理大量数据，特别是需要在队列两端频繁操作时，list的真相就慢慢浮出来了——它的pop(0)和insert(0, x)其实很慢，因为每次都会移动后面的所有元素。这时候，deque就登场了。

它到底是什么东西

简单说，deque是“double-ended queue”的缩写，也就是双端队列。它来自collections模块。和list不一样，deque在设计上就考虑了两端操作的高效。无论是从左边还是右边添加、删除元素，它的时间复杂度都是O(1)。这听着可能不够直观，拿装水果的篮子来打比方吧：list就像一箱摆得整整齐齐的苹果，你要从最底下拿一个，得先把上面所有苹果挪开。而deque更像一个两头通的管道，从哪头塞进去、从哪头拿出来都很顺畅。

deque在底层是用双向链表实现的，不过它做了很多优化。CPython的实现里，deque实际上是一个固定大小的数组块组成的环形缓冲区。这种设计既保持了链表的灵活，又避免了频繁的内存分配。知道这些细节在日常使用中未必有用，但偶尔遇到性能瓶颈时，能帮你更准确地判断问题所在。

能用来干什么

deque最常见的用途是做队列和栈。其实Python的list也能当栈用，而且效率不错，因为append和pop都是在尾部操作。但当你要实现一个FIFO（先进先出）队列时，deque的优势就很明显了。比如你写一个简单的任务调度器，任务按顺序进来，又按顺序出去，用deque就很合适。

另一个常用的场景是维护一个固定大小的滑动窗口。比如记录用户最近的10次操作，或者监控系统里最近1000个时间点的数据。deque的maxlen参数正好派上用场。当元素数量超过maxlen时，旧数据会自动从另一端弹出。这比你自己写逻辑来检查长度、删除旧数据要省心得多。

还有个不太起眼但很实用的功能——旋转（rotate）。比如你有一组轮询的代理IP，每次用完一个就把它放到末尾，用rotate(1)就能实现这种循环。或者实现一个简单的歌曲播放列表的下一首、上一首功能，也很顺手。

怎么用才顺手

先看最基础的：

fromcollectionsimportdeque d=deque([1,2,3])d.append(4)# 右边添加d.appendleft(0)# 左边添加d.pop()# 右边弹出d.popleft()# 左边弹出

这些操作都很直观。但有几个细节值得提一下。

先用maxlen：

d=deque(maxlen=5)foriinrange(10):d.append(i)print(d)

你会看到deque始终只保留最后5个元素。这比每次手动检查len(d) > 5然后d.popleft()要干净得多。

再说rotate：

d=deque([1,2,3,4,5])d.rotate(2)# 向右旋转2步# 结果: [4, 5, 1, 2, 3]d.rotate(-3)# 向左旋转3步

这个函数在做某种轮询或循环时特别好用。不过要注意，假如你的deque很大（比如十万级），rotate会相当快，因为它只是调整了内部指针，并不实际移动数据。

还有几个不太常用但值得了解的：index()可以在deque里查找元素，remove()可以删除指定值。但注意，这些操作都是O(n)的，因为deque不是为随机访问优化的。非要频繁做随机访问的话，还是用list或者考虑其他数据结构吧。

最佳实践里的一些坑

先说说什么时候不该用deque。如果你主要做的是随机访问（比如d[500]），或者频繁在中间插入数据，那deque反而比list慢。deque的设计理念就是“两头快，中间慢”，强求它做不擅长的事只会让自己难受。

另外要记住，deque虽然叫“双端队列”，但它是线程安全的。append和popleft在多个线程间调用不会出问题。不过这仅限于单个操作，如果你要做一系列原子操作，还是得自己加锁。

内存占用方面，deque比list大一些。因为每个元素都要额外存储指针。如果你的数据量特别大，而且主要只在一端操作，那list反而可能更省内存。

还有就是，不要把deque和deque之间做加法运算。虽然Python里[1,2] + [3,4]是允许的，但deque没有这个操作。想把两个deque合并，可以用extend方法。

和其他同类技术比一比

和list比，deque在两端操作上快得多。拿一个有10万个元素的list做pop(0)，耗时大概是deque的popleft的几百倍。但list的优势在于随机访问（O(1) vs O(n)），以及更少的内存占用。

和queue.Queue比，deque更轻量。Queue是为线程间通信设计的，内部有锁，性能开销大。如果你的场景不需要跨线程同步，用deque就够了。

和collections.OrderedDict比，二者看似都能保持顺序，但用途完全不同。OrderedDict主要是为了快速查找和更新，同时保持插入顺序。deque则是为了高效的两端操作。

还有个容易搞混的是multiprocessing.Queue。它是为进程间通信准备的，底层实现复杂得多，开销也大。如果你的数据不需要跨进程传递，别用这个。

日常用的话，记住一条原则：当你在写代码时发现自己在频繁地用list的pop(0)、insert(0, x)，或者手动维护一个固定大小的队列时，就该掏出deque了。反之，如果你主要做随机访问，或者数据量不超过几万，list可能更合适。

写代码这事儿，选对工具比写花哨的算法更实在。deque不是什么高深的东西，但在该用它的地方用上它，代码会干净不少，性能也会有质的提升。