Python 的 collections.deque 是标准库里的双端队列实现，通常读作“deck”。它允许在序列两端插入和删除，既能当栈用，也能当队列用，可以理解为栈和队列的超集。很多人会拿它和 list 比较：list 在头部插入或删除时要搬移后续元素，复杂度是 O(n)；deque 的两端操作只需要调整指针，复杂度是 O(1)。这是 deque 存在的核心理由，也是选型时最需要抓住的点。
一、核心 API 与容易踩的顺序坑
导入方式：- from collections import deque
- dq = deque([1, 2, 3])
- dq.append(4) # 尾部添加
- dq.appendleft(0) # 头部添加
- dq.pop() # 删除并返回尾部元素
- dq.popleft() # 删除并返回头部元素
append 对应普通队列入队，appendleft 从头部插入，底层只动头指针，代价是常量级。空队列上调用 pop 或 popleft 会抛 IndexError，生产代码里最好先判断 if dq:，或者用 try/except 接住。
批量操作里有 extend 和 extendleft，后者最容易出错：- dq = deque([1, 2, 3])
- dq.extend([4, 5])
- dq.extendleft([-1, -2])
- # 结果：deque([-2, -1, 1, 2, 3, 4, 5])
extendleft([-1, -2]) 之后头部依次是 -2、-1，因为内部等价于逐个调用 appendleft，每次新元素都塞到最前面。想保持原顺序，不要直接用 extendleft。
特殊能力包括 rotate、remove、count、index、clear、copy 和 maxlen。例如：- dq = deque([1, 2, 3, 4, 5])
- dq.rotate(2) # deque([4, 5, 1, 2, 3])
- dq.rotate(-1) # deque([5, 1, 2, 3, 4])
- dq.remove(3)
- dq.count(2)
- dq.index(4)
rotate 正数向右循环移动，负数向左循环移动，在轮转调度、约瑟夫环、日历翻页里很顺手。remove 从左往右删除第一个匹配项，找不到会抛 ValueError。index、count 也是从左往右扫描。
二、四个典型算法场景
回文检测是双端队列最直观的案例：- def is_palindrome(s: str) -> bool:
- dq = deque(s.lower())
- while len(dq) > 1:
- if dq.popleft() != dq.pop():
- return False
- return True
- assert is_palindrome('racecar') is True
- assert is_palindrome('hello') is False
- assert is_palindrome('上海自来水来自海上') is True
这个写法用 popleft 和 pop 成对比较两侧字符，索引细节少，出错概率低。纯字符串回文用 s == s[::-1] 更快，但作为理解双端操作的示例更合适。
滑动窗口最大值是单调双端队列的经典应用。deque 里存窗口元素下标，并保证对应值从左到右单调递减，队首就是当前窗口最大值下标。每一步先清理过期队首，再从队尾弹出所有不大于当前值的下标，最后压入当前下标：- from collections import deque
- def max_sliding_window(nums, k):
- dq = deque()
- res = []
- for i, v in enumerate(nums):
- while dq and dq[0] <= i - k:
- dq.popleft()
- while dq and nums[dq[-1]] <= v:
- dq.pop()
- dq.append(i)
- if i >= k - 1:
- res.append(nums[dq[0]])
- return res
顺序很重要：先清理窗口之外的，再维护单调性，最后 append 当前下标。顺序错了，结果会时对时错。这个“丢弃未来不可能再用的元素”的思路，也能迁移到其他优化问题。
BFS 应该默认用 deque，而不是 list.pop(0)：- def bfs(root):
- if not root:
- return []
- res = []
- dq = deque([root])
- while dq:
- node = dq.popleft()
- res.append(node.val)
- if node.left:
- dq.append(node.left)
- if node.right:
- dq.append(node.right)
- return res
小规模图上看不出差异，节点上万后，list 头部弹出 O(n) 的代价会体现到秒级。双向 BFS 也可以用两个 deque 分别维护起点和终点扩展，每次从节点数更少的一端扩展一层，再用集合记录已访问节点判断相交。
约瑟夫环用 rotate 写非常直白：- def josephus(n, k):
- dq = deque(range(1, n + 1))
- while len(dq) > 1:
- dq.rotate(-(k - 1))
- dq.popleft()
- return dq[0]
josephus(7, 3) 的结果是 4。rotate(-(k-1)) 把第 k 个人转到队首，再 popleft 移除。任务轮转调度也可以用 rotate(-1) 模拟当前任务出队再入队。
三、底层实现与复杂度真相
CPython 中 deque 的底层是“块状双向链表”。多个 block 之间用双向链表串起来，每个 block 内部是一段连续存储元素的定长数组。block 容量与机器指针大小有关，CPython 源码里有一个基于 sizeof(void*) 计算的常量，通常约 64。块满时新分配 block 挂到链表末尾，块空时释放或回收。
这种结构让两端操作只需调整首尾 block 里的指针和元素，不需要像 list 那样搬移整片连续内存。但中间索引不是 O(1)：dq 要从头部或尾部沿链逐个块找过去，CPython 会根据下标离哪一端更近来决定遍历方向，平均仍是 O(n)。remove、index、count 同理，最坏都是 O(n)。一句话：deque 的两端是高速公路，中间是乡间小路。
线程安全方面，deque 的单个原子操作在 CPython 中受 GIL 保护，append、appendleft、pop、popleft 不会被其他线程打断，可以用于生产者消费者模型。但 if dq: item = dq.popleft() 这种“检查后操作”的组合不是原子的，需要自己加锁，或者使用 queue.Queue。queue.Queue 本质上是在 deque 之上包了一层线程安全机制和阻塞通知，put、get、task_done、join 提供完整多线程语义。
四、性能实测与容器选型
可以用 timeit 对比 list.pop(0) 和 deque.popleft()：- import timeit
- setup_list = 'lst = list(range(100000))'
- setup_deque = 'from collections import deque; dq = deque(range(100000))'
- t_list_pop0 = timeit.timeit('lst.pop(0)', setup=setup_list, number=10000)
- t_deque_popleft = timeit.timeit('dq.popleft()', setup=setup_deque, number=10000)
- print(f'list.pop(0): {t_list_pop0:.4f} s')
- print(f'deque.popleft(): {t_deque_popleft:.4f} s')
注意 number=10000 很容易让 list 越界，因为同一个 list 弹 10000 次已经空了。更严谨的测试应每轮重置容器，这里只是演示差异。实际运行时，list 的耗时在几十毫秒级别震荡，deque 通常稳定在几毫秒以下；数据量到百万级后，list 的劣势会指数级放大，deque 依旧平稳。头部 insert(0, x) 和 appendleft 也是同样结论。尾部操作两边都是 O(1)，差距可忽略。
maxlen 是有界队列的隐藏利器：- dq = deque(maxlen=3)
- for i in range(5):
- dq.append(i)
- # 结果：deque([2, 3, 4], maxlen=3)
达到上限后再插入，另一端的旧元素会自动挤出。日志缓存、实时数据流最近 N 条记录都很适合。maxlen 一旦设定不能修改，想改只能重建 deque。
选型可以按操作重心判断：随机访问多、中间插入多、数据量小，用 list，连续内存缓存命中高，索引 O(1)；高频头部插入删除，用 deque，两端 O(1)；BFS、滑动窗口、单调队列，用 deque；线程间安全传递任务，用 queue.Queue；按优先级取元素，用 heapq 或 PriorityQueue；日志缓存、最近 N 条记录，用 deque(maxlen=N)。deque 和 list 可以互转，实际开发中常把 deque 当临时缓冲区，处理完一批数据再 list(dq) 转成列表做随机访问或传给下游。
五、常见问题与避坑
不要把 deque 当 list 做随机访问。for i in range(len(dq)): dq 这种写法是 O(n^2)，改成 for line in dq 迭代才是 O(n)。需要索引访问时先转 list。deque 也不能直接切片，会报 TypeError: sequence index must be integer, not slice，可以自己写 itertools.islice 或转 list 再切。
deque 不能直接被 json.dumps 序列化，会抛 TypeError: Object of type deque is not JSON serializable。解决方式是在序列化前转 list：- import json
- from collections import deque
- dq = deque([1, 2, 3])
- data = json.dumps(list(dq))
- # 反序列化
- dq2 = deque(json.loads(data))
pickle 可以直接序列化 deque，不需要额外转换。深拷贝方面，deque 和 list 一样是可变容器，dq.copy() 是浅拷贝，只复制容器本身，里面的可变对象仍会互相影响，嵌套结构要用 copy.deepcopy(dq)。
面试和考试里还有受限双端队列考点。输入受限双端队列指一端可插入、可删除，另一端只允许删除；输出受限则相反，一端可插入、可删除，另一端只允许插入。常见题是给输入序列，问哪些输出序列合法。另一个高频题是用两个栈模拟双端队列，核心是把入队操作分散在两个栈上，弹出时从对应栈取，栈空时从另一个栈搬运。还要注意，deque 和 collections.defaultdict 没有关系，只是名字容易让人混淆。
实际写代码时，只要看到“头部插入或删除”的动作，就可以优先考虑 deque，不要等数据量上来再重构。需要旋转列表时，也先想想 rotate 能否直接解决。若只是写不追求性能的小脚本，list 完全够用，合适才是最重要的。 |
发表于