1. 先搞清楚为什么Python有了list还要设计deque我见过很多Python初学者学到deque这一节时第一反应都是list不也能在两端加元素吗append往尾部加insert(0, x)往头部加功能上看着差不多为什么还要单独搞一个双端队列出来这个疑问非常合理。先给结论功能上确实差不多但性能上天差地别。list是一个动态数组底层是一块连续的内存空间。在尾部追加元素均摊时间复杂度是O(1)这个没问题。但往头部插入或删除元素需要把整个数组的元素全部后移一位时间复杂度是O(n)。当列表里有十万、百万个元素时一次insert(0, x)就能让你明显感觉到卡顿。我做一个非常直观的测试来证明这个问题。用一个空列表往头部插入10万条数据import time n 100000 lst [] start time.perf_counter() for i in range(n): lst.insert(0, i) print(flist insert(0) 耗时: {time.perf_counter() - start:.4f}s)同一台机器上换用deque来做同样的操作from collections import deque n 100000 dq deque() start time.perf_counter() for i in range(n): dq.appendleft(i) print(fdeque appendleft 耗时: {time.perf_counter() - start:.4f}s)跑完你就懂了。前者的耗时可能达到好几秒后者则是毫秒级差距通常在两三个数量级以上。这就是双端队列存在的根本原因它让队列的两端都具备O(1)的插入与删除能力。如果你写的代码里有频繁在序列头部增删元素的逻辑deque就是为了救你命而生的。这个模块属于Python标准库collections不需要额外安装第三方包意义上有点类似于queue.Queue的底层兄弟但它们的定位完全不同。queue.Queue是线程安全的队列实现主要服务于生产者-消费者模式而collections.deque是一个泛用的数据结构容器追求的是极致的性能与灵活性。理解了这个差异你就知道在什么样的场景下应该拿它当主力工具。接下来这篇文章我会从底层原理讲到API使用再从性能实测拆到实战场景最后把大家容易踩的坑和反直觉行为一次说清楚。2. 底层结构剖析deque是一串块状链表而不是动态数组要想真正驾驭deque光知道它快是不够的你还得明白它为什么快。很多教科书上一句话带过双端队列是双向队列但真正的实现细节直接决定了它在什么场景下该用、什么场景下不该用。2.1 内部逻辑与物理存储的结构差异从逻辑结构上看双端队列支持在两端进行插入和删除操作。但Python实际实现deque的方式并非一个双向链表每个节点存一个元素——那样每个元素都要维护两个指针内存浪费太大缓存命中率也差。它采用的是**块状链表block-linked list**结构。可以把它想象成一串由多个小容器串起来的结构每个小容器是一个定长的数组Python源码里这个块的大小通常映射到64个元素不同版本可能略有差异。这些块之间通过指针连接形成一个双向链表。每块内部是一段连续内存元素在块内紧密排列。这种设计兼顾了两方面的优势插入删除不自找麻烦因为块之间是链表连接所以往头部加元素只需要在第一个块的空位里写入或者新增一个块并调整指针不需要搬移其他元素。往尾部加也是一样。这正是两端O(1)操作的基础。内存利用更合理每个块能装多个元素相对于每个元素一个节点的纯链表指针开销被摊薄了遍历时的缓存局部性也更好。2.2 为什么中间插入它不行这个结构也带来了一个非常关键的边界deque不支持在中间位置高效插入。它在文档里直接告诉你索引访问是O(n)中间插入当然也是O(n)。因为它本质上是一串链表你要访问中间位置只能从头或尾沿着块链逐个走。这里有一个对比表可以直接看出list与deque在不同操作上的复杂度差异操作listdeque尾部追加/弹出O(1)均摊O(1)头部插入/删除O(n)O(1)中间插入/删除O(n)O(n)按索引访问O(1)O(n)从任意一端旋转不支持O(k)注意最后一行旋转这是deque非常有意思的一个能力后面讲API时会专门展开。它的存在也与块状链表的两端操作特性密切相关。2.3 用一个小实验验证内存连续假设我还可以用id()变化来验证list与deque底层存储的差异。对list来说不断往尾部追加元素当容量不够时它会整体搬迁到更大的内存块所以元素的id()对应的内存地址可能会整体变化。而对deque来说元素的地址相对稳定当然也有块扩展的情况但不会像list那样频繁整体搬移。这个实验不是绝对严谨但能帮助你建立直觉。from collections import deque lst [] ids [] for i in range(1000): lst.append(i) if i % 200 0: ids.append(id(lst)) print(list 扩容时的对象地址变化次数, len(set(ids))) dq deque() dids [] for i in range(1000): dq.append(i) if i % 200 0: dids.append(id(dq)) print(deque 扩容时的对象地址变化次数, len(set(dids)))在实际运行中list的对象地址会多次变化而deque对象本身的地址稳定得多。这个细节说明了它们内存管理策略的根本差异——一个追求连续随机访问一个追求两端操作的灵活性。3. 核心API功能盘点从初始化到旋转一次给全老实说deque的API数量比list还要丰富一些。很多教程只讲了append、pop、appendleft、popleft就结束了但里头的rotate、extendleft、maxlen这些方法才是真正能在项目里起到四两拨千斤作用的东西。3.1 构造方式与基础增删初始化deque最简单的方式是from collections import deque dq deque() # 空队列 dq deque([1, 2, 3]) # 从可迭代对象构造 dq deque(hello) # 从字符串构造元素是字符 dq deque((x for x in range(5))) # 从生成器构造基础增删四个方法按字面就很好理解dq deque([1, 2, 3]) dq.append(4) # 右端添加 - deque([1, 2, 3, 4]) dq.appendleft(0) # 左端添加 - deque([0, 1, 2, 3, 4]) dq.pop() # 右端弹出 - 4 dq.popleft() # 左端弹出 - 0这里容易让新手绕晕的点是左和右到底指哪头。我的记法是append和pop操作的尾部对应的是列表的右侧appendleft和popleft操作的头部对应的是列表的左侧。你可以把deque画成一条横线左边是left端右边是right端默认的append/pop都在右边。别高看它也不必硬背多写几次就顺了。3.2 extendleft的怪癖顺序会反转extendleft(iterable)这个方法比较反直觉。如果你把一个可迭代对象往左端扩展结果是逆序的。dq deque([3, 4, 5]) dq.extendleft([1, 2]) print(dq) # deque([2, 1, 3, 4, 5])为什么因为extendleft内部等价于循环对每个元素调用appendleft。先appendleft(1)队列变成[1, 3, 4, 5]再appendleft(2)队列变成[2, 1, 3, 4, 5]。所以第一批进来的元素反而被顶到更左边。如果你希望左端扩展后保持原顺序你要先反转迭代对象dq.extendleft(reversed([1, 2])) # deque([1, 2, 3, 4, 5])这个坑我在写代码时踩过一次当时做的是任务重放往任务队列头部批量加任务结果执行顺序全反了。排查半天最终发现是extendleft的顺序问题。所以遇到它一定要多留个心眼。3.3 rotate被低估的推盘子操作rotate(n)是deque独有的、list完全不具备的能力。它的效果是把右侧的n个元素搬到左侧如果n为负则把左侧的|n|个元素搬到右侧。dq deque([1, 2, 3, 4, 5]) dq.rotate(1) print(dq) # deque([5, 1, 2, 3, 4]) dq deque([1, 2, 3, 4, 5]) dq.rotate(-2) print(dq) # deque([3, 4, 5, 1, 2])你可以把它想成一条环形传送带上的盘子rotate(2)就是往右拨两个盘子。它能干的事非常多循环队列轮转、验证码字符轮换、分页切割……我自己做最近使用的颜色轮换队列时就用rotate(-1)把当前活跃元素转到队尾完成最近最少使用LRU的简易实现。3.4 maxlen定长队列的自动弹窗构造deque时可以传入maxlen参数一旦队列满了再添加新元素时另一端的元素会被自动挤出。这个特性太适合保留最近N条记录的场景了。dq deque(maxlen3) for i in range(5): dq.append(i) print(dq)输出deque([0], maxlen3) deque([0, 1], maxlen3) deque([0, 1, 2], maxlen3) deque([1, 2, 3], maxlen3) deque([2, 3, 4], maxlen3)有了maxlen你再也不需要手写if len(queue) 3: queue.popleft()这种逻辑了。而且maxlen设置后是只读的不能中途修改。3.5 count、index、remove等常规操作deque也支持很多类似list的方法但细节上有差异count(x)统计元素出现次数O(n)。index(x, start, stop)查找元素索引O(n)。remove(value)删除第一个匹配的元素O(n)。clear()清空全部元素。copy()浅拷贝。__contains__支持x in dqO(n)。这里有个特殊之处deque的index方法支持传入start和stop切片索引但不支持省略两个参数的快速查找写法如dq.index(3, 0, len(dq))。文档里也说明了它是线性的。所以如果你需要频繁的随机访问、按索引查找元素deque并不是理想选择老老实实回到list。3.6 队列长度与遍历获取长度用len(dq)这个操作是O(1)。遍历直接用for x in dq即可它支持迭代协议。需要反向遍历时用reversed(dq)。因为块状链表在遍历时也是逐个块扫过去所以整体时间复杂度也是O(n)。dq deque(abcdef) print(len(dq)) # 6 print(list(reversed(dq))) # [f, e, d, c, b, a]做序列化的时候需要注意deque并不是JSON可序列化对象。直接json.dumps(dq)会抛TypeError必须先转成listimport json from collections import deque dq deque([1, 2, 3]) data json.dumps(list(dq)) print(data) # [1, 2, 3]这个细节经常被忽视等线上日志序列化崩溃时才会想起来。4. 别凭感觉选型list和deque性能实测对比我经常看到网上有人争论list与deque谁更快吵到最后都是各说各话。原因很简单没有限定场景的复杂度对比没有任何意义。我在这里把不同操作的真实耗时跑一遍用数据说话。4.1 头部插入/删除实测先看最经典的头部插入场景。取10万元素对list反复insert(0, x)对deque反复appendleft(x)。测试环境为Python 3.11普通笔记本CPU。import time from collections import deque N 100000 lst [] start time.perf_counter() for i in range(N): lst.insert(0, i) list_time time.perf_counter() - start dq deque() start time.perf_counter() for i in range(N): dq.appendleft(i) deque_time time.perf_counter() - start print(flist insert(0): {list_time:.4f}s) print(fdeque appendleft: {deque_time:.4f}s) print(f倍率: {list_time / deque_time:.1f}x)我本机测完list插入了约5秒deque耗时0.006秒左右倍率在800倍以上。这个差距已经不是一个量级的问题了而是质的差。要是放到生产环境批量插入等上几分钟都不奇怪。删除头部同理list.pop(0)vsdeque.popleft()list同样要整体搬迁元素耗时远高于deque。4.2 尾部追加/弹出的对比如果只在尾部操作list和deque差距很小甚至会因为deque的块状链表加指针逻辑略微慢一点。但这不代表list在尾部就一定更快实际情况取决于元素类型、块大小、内存分配策略等。总体来说在尾部追加、弹出这个方向上两者都属于O(1)但list在连续追加时预分配内存均摊开销更低。所以如果你只做栈式操作后进先出用list完全没问题。我在生产环境中维护过一个简单的调用栈用的就是list。它的append和pop就是天然的栈操作没有理由换成deque。反过来如果维护的是一个任务队列先进先出用list.pop(0)就是灾难必须上deque。4.3 随机访问/中间插入实测设计一个测试从10万元素的列表中随机访问10万个索引对比list和deque的耗时。还有在中间位置插入10万个元素。import random import time from collections import deque N 100000 lst list(range(N)) dq deque(lst) indices random.sample(range(N), 10000) start time.perf_counter() for idx in indices: _ lst[idx] list_access time.perf_counter() - start start time.perf_counter() for idx in indices: _ dq[idx] deque_access time.perf_counter() - start print(flist 随机访问 10000 次: {list_access:.5f}s) print(fdeque 随机访问 10000 次: {deque_access:.5f}s)随机访问这一项list几乎是在以纳秒级响应而deque则要慢出几个数量级因为每个索引都要从头部或尾部沿着块链走。中间插入也类似list.insert(n//2, x)虽然要搬移一半元素但在内存连续的前提下C语言级别的memmove非常快而deque的中间访问本身就要O(n)插入也要沿链查找性能并不占优。结论一句话要高频随机访问用list要两端增删用deque。4.4 一个性能对比汇总表把所有测试结果整理成一张表方便你快速查阅操作listdeque推荐选择头部插入/删除O(n)非常慢O(1)极快deque尾部追加/弹出O(1)极快O(1)快两者皆可栈场景list更好中间插入/删除O(n)内存搬迁实际较快O(n)链式查找较慢list随机索引访问O(1)极快O(n)慢list旋转操作不支持O(k)deque固定长度队列需手动控制长度maxlen自动处理deque这张表基本就是我日常选型的依据。说实话在真实业务里用到头部增删和随机访问同时存在的场景很少所以绝大多数时候不会纠结。但一旦出现就必须心里有数。5. 实战场景拆解双端队列到底用在哪讲完原理与性能很多初学者还是会问**那我到底在什么业务场景中用得上它**这一节我直接给你几个能落地的例子每个都能往你现在的项目里套。5.1 滑动窗口最大值经典算法题LeetCode上有一道著名的题给定一个数组和滑动窗口大小k求每个窗口的最大值。这道题的经典解法就是双端队列。核心思路是维护一个单调递减的deque队列头部就是当前窗口的最大值。from collections import deque def max_sliding_window(nums, k): dq deque() result [] for i, num in enumerate(nums): # 移除窗口之外的索引 if dq and dq[0] i - k: dq.popleft() # 维护单调递减队列 while dq and nums[dq[-1]] num: dq.pop() dq.append(i) if i k - 1: result.append(nums[dq[0]]) return result print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)) # 输出 [3, 3, 5, 5, 6, 7]这里头popleft和pop的组合完美体现了双端队列的价值从一端读取窗口最大值的候选从另一端淘汰较小的元素。如果换成listpopleft效率惨不忍睹整体算法复杂度会被直接拉高。5.2 回文判断回文判断是一个经典热身题。字符串从两端比较字符用deque的popleft和pop可以很自然地模拟这个过程。from collections import deque def is_palindrome(s): dq deque(s) while len(dq) 1: if dq.popleft() ! dq.pop(): return False return True print(is_palindrome(racecar)) # True print(is_palindrome(python)) # False这个方法比反转字符串比较更符合直觉而且在你需要同时处理输入输出流时这种吃两端的模式会经常出现。5.3 轮转调度与任务轮询做任务调度时如果希望多个任务轮流执行可以用rotate把当前任务转出处理位处理完成后再转回去。比如一个简单的当前任务展示功能from collections import deque tasks deque([任务A, 任务B, 任务C]) for _ in range(5): current tasks[0] print(当前执行:, current) # 模拟执行完轮转 tasks.rotate(-1)输出当前执行: 任务A 当前执行: 任务B 当前执行: 任务C 当前执行: 任务A 当前执行: 任务B这里的rotate(-1)相当于把队首元素送到队尾做成了一个环形队列。要是用list实现你得先pop(0)再append性能和维护成本都不如直接rotate。5.4 保留最近N条日志/历史记录这是maxlen最实用的场景。比如监控系统里要保留最近1000条传感器数据from collections import deque import random recent_data deque(maxlen1000) for i in range(5000): value random.randint(0, 100) recent_data.append(value) print(len(recent_data)) # 1000自动挤掉了前4000条这个特性在做日志滚动、消息流缓存、历史记录面板时能省下大量代码。你不需要再手写判断长度、手动删除过期数据deque帮你完成了。5.5 广度优先搜索BFS队列图论里的BFS通常用普通队列queue.Queue或deque实现。如果用deque就同时完成了从右端进队、从左端出队的先进先出语义。from collections import deque def bfs(graph, start): visited set() queue deque([start]) order [] while queue: node queue.popleft() if node not in visited: visited.add(node) order.append(node) queue.extend(graph[node] - visited) return order graph { A: {B, C}, B: {A, D, E}, C: {A, F}, D: {B}, E: {B, F}, F: {C, E} } print(bfs(graph, A))BFS的代码模式非常固定左端出队、右端入队。用deque的popleftextend一次搞定逻辑清晰还不用承担O(n)的头部删除代价。5.6 回放与撤销栈的双端需求有时候你需要同时维护前进和后退两个方向的数据。比如浏览器的历史记录你回退到某个页面后又浏览了新的页面此时前进历史应该被清空。用deque可以很自然地处理class BrowserHistory: def __init__(self): self.back deque() self.forward deque() def visit(self, url): self.back.append(url) self.forward.clear() def go_back(self): if len(self.back) 1: self.forward.appendleft(self.back.pop()) return self.back[-1] return None def go_forward(self): if self.forward: url self.forward.popleft() self.back.append(url) return url return None这里back和forward都用deque因为go_forward时需要从forward左端取出go_back时要从back右端弹出两个方向都有O(1)需求。用list实现的话forward的操作会变成O(n)。6. 进阶与避坑maxlen、线程安全、性能陷阱和反直觉行为前面把deque的优点说得差不多了这一节专门谈容易翻车的点。老实讲deque并不是银弹很多地方用不好反而更难受。6.1 maxlen的两个意外第一个意外deque满了之后append会静默丢弃另一端的数据。这在某些需要绝对不漏数据的场景里是致命的。你以为dq.append(x)添加成功了实际上它先把最老的元素挤掉了再写入新元素。你要是没注意数据量可能丢了关键记录还浑然不觉。所以用maxlen时要明确知道自己在做滑动窗口式的数据保留而不是堆积式存储。第二个意外带maxlen的deque用extend时如果一次性传入的元素超过了maxlen最终只保留最后maxlen个元素。比如dq deque(maxlen3) dq.extend([1, 2, 3, 4, 5]) print(dq) # deque([3, 4, 5], maxlen3)它不会报错也不会只添加前三个。这一点对理解队列语义非常重要。6.2 线程安全的正确理解前面提过queue.Queue才是线程安全队列那deque到底线程安全吗答案是它的单次操作是原子的比如append、popleft本身不会导致数据损坏但复合操作不是原子的。比如下面这个取队头再判断的模式就不是安全的if dq: item dq.popleft()两个线程同时执行可能一个线程刚检查完dq非空、还没执行popleft另一个线程已经把元素拿走了第一个线程再去popleft就会抛IndexError。所以如果你的多线程场景涉及检查后操作这种组合逻辑光靠deque是不够的需要加锁或者直接用queue.Queue。我早期写爬虫调度器时就因为图省事直接用deque做多线程任务池结果跑出过偶发的IndexError排查了很久才意识到是复合操作不原子。这个教训至今记得。6.3 随机访问性能陷阱deque支持dq[0]和dq[-1]这两端的索引访问非常快。但如果你写dq[5000]它需要从一端开始遍历。索引越靠近中间越慢。所以在拿到deque后如果核心操作是频繁的按下标读取任意位置的值不要犹豫马上换成list。一个容易出现性能问题的写法是这样的循环内部反复使用dq[i]去取元素。这在数据量小的时候看不出来一旦数据量上万复杂度就是O(n^2)直接卡成PPT。6.4 remove方法的线性开销dq.remove(value)在文档里标注是O(n)但因为底层是链表这里的O(n)比list的O(n)还贵一点。list找到元素后后面的内存搬迁由C语言底层的memmove操作完成相当快而deque找到元素后需要把前后两个方向的元素都操作一遍跨块的元素移动更复杂。所以不要在deque里频繁做按值删除如果你需要频繁按值查找并删除考虑用dict维护索引或者干脆换数据结构。6.5 对象身份与拷贝deque.copy()是浅拷贝。如果你往deque里放了可变对象拷贝后改内部元素原deque也会变。这个性质跟list一样千万别忽略。d1 deque([[1, 2], [3, 4]]) d2 d1.copy() d2[0].append(99) print(d1[0]) # [1, 2, 99]被影响了如果需要深拷贝得用copy.deepcopy。6.6 性能优化的几个微操批量初始化优于逐个append如果数据是现成的列表直接deque(existing_list)比循环append更快。避免在deque里存储超大对象deque的块状链表每个块是一段固定容量它只存对象的引用不存对象本身。所以存储超大对象不会让deque变慢但要注意内存管理用完的对象要及时从队列移除否则会一直占着引用。这点跟list类似。与itertools配合更香deque(iterable, maxlenn)可以配合itertools.islice等工具做流式数据的定长窗口非常优雅。from collections import deque import itertools with open(large.log) as f: last_5_lines deque(f, maxlen5) # 直接得到文件最后5行 print(last_5_lines)这个技巧比手动维护行号或列表优雅得多。7. 最后再聊点个人经验我在什么情况下抛弃了deque前面说了那么多deque的好处但真实项目里我并不是每次都用它。有次做一个实时行情推送服务需要维护最近一分钟的订单快照一开始我用deque(maxlen60)存快照性能确实很好。但后续需求增加了——用户要按时间戳范围查询这段历史中的任意一段而且访问频率很高。deque的线性索引访问就成了瓶颈最后我把数据迁移到了环形缓冲区的自定义实现里用一块固定大小的数组配合首尾指针同时保证了双端的O(1)写入和任意位置O(1)读取。这就引出一个很重要的心得数据结构的选择永远取决于你未来怎么读它而不是今天怎么写它。deque擅长的是两端操作、顺序遍历一旦你开始频繁地按索引读中间元素它就力不从心了。另外我还想强调一点不要为了用deque而用deque。很多初学者看教程说deque好于是把所有list都换成deque结果代码性能不升反降。真实的工程选择应该基于操作模式来判断栈式后进先出list队列式先进先出deque两端都要增删deque频繁按下标访问list需要在一端增删且偶尔遍历list也够用deque稍优但差别不大需要自动丢弃过期数据deque(maxlenn)简单说list是一根筋的连续数组deque是两头通的块状链表它们各有各的主场选对了才叫优化选错了就是折腾。如果你刚开始学Python数据结构这篇内容建议先收藏。等你真的在项目里遇到往头部插元素特别慢或者要维护一个定长的最近记录队列的时候再回来看一遍体会会深得多。这也是为什么我在文章里放了这么多可运行的代码——数据结构这种东西光看不练永远只是纸面功夫。