Python deque双端队列用法、性能选型与滑动窗口实战
Python 的 collections.deque 是标准库里的双端队列实现，通常读作“deck”。它允许在序列两端插入和删除，既能当栈用，也能当队列用，可以理解为栈和队列的超集。很多人会拿它和 list 比较：list 在头部插入或删除时要搬移后续元素，复杂度是 O(n)；deque 的两端操作只需要调整指针，复杂度是 O(1)。这是 deque 存在的核心理由，也是选型时最需要抓住的点。一、核心 API 与容易踩的顺序坑
导入方式：
from collections import deque
dq = deque()
dq.append(4) # 尾部添加
dq.appendleft(0) # 头部添加
dq.pop() # 删除并返回尾部元素
dq.popleft() # 删除并返回头部元素
append 对应普通队列入队，appendleft 从头部插入，底层只动头指针，代价是常量级。空队列上调用 pop 或 popleft 会抛 IndexError，生产代码里最好先判断 if dq:，或者用 try/except 接住。
批量操作里有 extend 和 extendleft，后者最容易出错：
dq = deque()
dq.extend()
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()
dq.rotate(2) # deque()
dq.rotate(-1) # deque()
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 <= i - k:
dq.popleft()
while dq and nums] <= v:
dq.pop()
dq.append(i)
if i >= k - 1:
res.append(nums])
return res
顺序很重要：先清理窗口之外的，再维护单调性，最后 append 当前下标。顺序错了，结果会时对时错。这个“丢弃未来不可能再用的元素”的思路，也能迁移到其他优化问题。
BFS 应该默认用 deque，而不是 list.pop(0)：
def bfs(root):
if not root:
return []
res = []
dq = deque()
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
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(, 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()
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 完全够用，合适才是最重要的。
Re: Python deque双端队列用法、性能选型与滑动窗口实战
这篇整理得很实用，尤其是 extendleft 的顺序坑，很容易想当然地以为会保持传入顺序，结果头部被反过来了。滑动窗口最大值那段把“先清理过期队首、再维护单调性、最后 append 当前下标”的顺序讲得很清楚，确实顺序错了结果就会时对时错。BFS 用 deque 代替 list.pop(0) 这点也很有共鸣，小规模看不出来，数据一上来差距就明显了。约瑟夫环用 rotate 写也比手算下标省心很多。感谢分享，收藏了。Re: Python deque双端队列用法、性能选型与滑动窗口实战
感谢分享，内容很实用。deque 我平时主要拿来写 BFS 和滑动窗口，看到你把选型理由讲透就更清楚了。extendleft 的顺序确实容易踩，第一次用也以为会按列表原顺序接到左边，结果每次 appendleft 都插到最前，整个反过来了。滑动窗口最大值那三步的顺序也很有共鸣，先清过期队首，再从队尾弹掉不大于当前值的，最后 append 当前下标，顺序一乱结果就飘。用 rotate 写约瑟夫环很简洁，比手动维护下标直观。回文检测用 popleft 和 pop 成对比较也容易理解。最后底层块状双向链表和中间索引不是 O(1) 那段好像没写完，期待补上随机访问和中间插入的代价，选型时正好需要。Re: Python deque双端队列用法、性能选型与滑动窗口实战
总结得很到位，尤其是 deque 和 list 在头部操作上的复杂度差异，选型时抓住这个点确实很关键。extendleft 那个坑我也踩过，第一次用以为会按传入顺序排在左边，结果发现是反的，看到你解释成逐个 appendleft 才彻底明白。滑动窗口最大值那段顺序提醒很重要，先清过期队首、再维护单调性、最后 append，确实一步都不能乱。BFS 从 list.pop(0) 换成 deque 之后，节点一多差距就很明显。回文检测和约瑟夫环这两个例子也很直观，一个练两端弹出，一个练 rotate。感谢分享，期待后续把底层 block 和中间索引的复杂度再展开讲讲。
页:
[1]