Python双端队列deque的使用小结

今天解决一个更灵活的结构：双端队列。python里对应 collections.deque ，通常读作“deck”。它一头连着栈，一头连着队列，可以在序列的两端同时进行插入和删除。很多同学刚接触时觉得，这不就是 list 吗？头部也能加，尾部也能删。但真正到了刷题、写调度器、处理滑动窗口的时候，就会发现 list 在头部操作的时间复杂度撑不住，双端队列才是“两端都能高效干活”的角色。

这篇文章不只讲 api，我会先带你从“排队”这个生活场景理解双端队列的设计动机，然后把 deque 的核心方法逐个过一遍，再深入到 cpython 源码层面看看它底层到底是什么结构，为什么两端操作都是 o(1)，最后给出性能实测数据和应用场景选型建议。如果你正在准备数据结构考试、刷 leetcode，或者写代码时纠结到底用 list 还是 deque，这篇应该能帮你把问题一次性理清楚。

1. 双端队列的设计思路与基本操作：先从排队模型说起

1.1 为什么需要“两端都能操作”的队列

想象一个真实的排队场景：普通队列是“从队尾入、从队头出”，医院叫号、食堂打饭都是这个逻辑。但现实中的排队往往没有那么老实——有人赶时间等不及，直接从队头离开；有人取了号转了一圈回来，又站到队伍前面；如果是餐厅排号，服务员还可能直接把 vip 客人安排到最前面。

这种“两端都能进出”的需求，就是双端队列产生的动机。数据结构上定义，双端队列（double-ended queue，简称 deque）是一种允许在表的两端进行插入和删除操作的线性表。它不限制你从哪一端操作，你可以只从一端进、另一端出，那它就是个普通队列；也可以只在同一端进和出，那它就是个栈。

所以从能力模型上讲，双端队列可以看成栈和队列的“超集”。正因为它把两端操作都开放了，很多原本需要手动维护两个指针、绕来绕去的代码，用双端队列可以写得非常直白。后续算法题里你会反复看到这个优点。

1.2 deque 的核心 api，看完就能动手

python 标准库里的双端队列实现就在 collections 模块里，使用前先导入：

from collections import deque

最常用的就是下面这组方法，我把它们分成“插入”“删除”“批量操作”“特殊能力”四类来说。

插入：append 和 appendleft

dq = deque([1, 2, 3])
dq.append(4)        # 尾部添加，结果：deque([1, 2, 3, 4])
dq.appendleft(0)    # 头部添加，结果：deque([0, 1, 2, 3, 4])

append 等价于普通队列的入队操作， appendleft 则是从头部插入。注意 appendleft 不是 insert(0, x) 的优化版本那么简单，它在底层确实只动了头指针，代价是常量级的。

删除：pop 和 popleft

dq.pop()            # 删除并返回尾部元素，返回 4
dq.popleft()        # 删除并返回头部元素，返回 0

空队列上调用这两个方法会抛出 indexerror ，所以生产代码里最好先判断 if dq: 再取值，或者用 try/except 接住。

批量操作：extend 和 extendleft

dq = deque([1, 2, 3])
dq.extend([4, 5])          # 尾部批量添加，结果：deque([1, 2, 3, 4, 5])
dq.extendleft([-1, -2])    # 头部批量添加，结果：deque([-2, -1, 1, 2, 3, 4, 5])

这里有个非常容易踩的坑： extendleft([-1, -2]) 之后，队列头部依次是 -2 、 -1 ，也就是说传入列表的顺序是反着进来的。原因是 extendleft 内部等价于逐个调用 appendleft ，每次新元素都被塞到最前面。如果你想把一个序列“反转后放到头部”，用 extendleft 就对了；如果你想保持原顺序，就别用这个方法，老老实实先反转再 extend。

特殊能力：rotate、remove、count、index

dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)        # 结果：deque([4, 5, 1, 2, 3])，整体向右循环移动 2 步
dq.rotate(-1)       # 结果：deque([5, 1, 2, 3, 4])，整体向左循环移动 1 步

dq.remove(3)        # 从头部开始找，删除第一个值为 3 的元素
dq.count(2)         # 统计元素 2 出现的次数
dq.index(4)         # 返回元素 4 从左往右第一次出现的位置

rotate 是双端队列相对“队列”这个概念的独特操作，它把整个序列循环移动，正数向右、负数向左。在约瑟夫环、轮转调度、日历翻页这类循环场景里，这个方法的表达能力远超过手写取模逻辑。 remove 会从左往右删除第一个匹配项，如果没找到会抛出 valueerror ，使用时注意捕获异常。

剩下的 clear() （清空所有元素）、 copy() （浅拷贝）、 maxlen 属性这几个也很好懂，用到的时候查文档就行。

1.3 为什么 list 不能替代 deque

你可能会想：上述操作 list 不都能做吗？头部加用 insert(0, x) ，头部删用 pop(0) ，尾部操作就是常规的 append 和 pop 。表面看确实如此，但关键在于复杂度。

list 是连续内存数组，在头部插入或删除一个元素，必须把后面的所有元素整体向前或向后移动一个位置。数据量小的时候感觉不到，但数据量一上来，这个 memmove 的成本就会非常刺眼。举个例子，一个 10 万元的 list，执行一次 lst.pop(0) ，等于把 99999 个元素全部往前挪一格，时间复杂度 o(n)。如果你在一个循环里反复这么干，整体就是 o(n^2)，分分钟让你的程序卡成幻灯片。

deque 的内部结构决定了它的两端操作只需要调整几个指针，时间复杂度恒为 o(1)。这是它存在的根本理由，也是你选型时最需要关注的一点。当然，deque 也不是万 能 钥匙，它在“随机访问”上明显弱于 list，这里面有个很关键的复杂度真相，我放到第 3 节细讲。

2. 双端队列在算法题里最常见的四个应用场景

2.1 回文检测：双端队列最直观的例子

回文判断是很多教材讲解双端队列时第一个引用的小案例，因为它完美匹配双端队列的语义：从两端各取一个字符比较，不比了就继续向中间收拢。

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[i] != s[n-1-i] 的写法，deque 版本少了很多索引细节，出错概率更低。当然，纯字符串回文检测用切片 s == s[::-1] 是最快的，但作为数据结构教学场景，deque 的思路更适合用来理解双端操作的概念。

2.2 滑动窗口最大值：单调双端队列的经典应用

刷过 leetcode 的朋友对 239 题“滑动窗口最大值”应该不陌生。题目要求维护一个窗口，窗口每次向右滑动一个位置，返回每一步窗口内的最大值。如果每一步都重新遍历窗口，复杂度 o(nk) 在数据一大就会超时。单调队列解法可以把复杂度压到 o(n)，核心数据结构就是双端队列。

思路是这样的：deque 里存窗口内元素的下标，同时保证这些下标对应的元素值从左到右是单调递减的。队首永远是当前窗口最大值的下标。每次滑动窗口时做三件事：

1. 把已经滑出窗口左端的下标从队首弹出；
2. 从队尾往前弹出所有“比当前新元素小”的下标，因为它们不可能再成为最大值；
3. 把当前元素下标压入队尾。

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 当前下标。顺序错了，结果就会时对时错。

2.3 bfs 层序遍历与双向搜索优化

图或树的广度优先搜索（bfs）需要队列记录待访问节点。很多 python 教程一上来就用 list 当队列， pop(0) 取节点。前面已经说过，list 头部弹出是 o(n)，在大规模图上，这一个操作就能拖垮整体性能。正确做法是使用 deque ：

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 版本，小规模测试看不出差异，一旦树的节点数上万，差距就到秒级别了。我把“bfs 用 deque”当作默认写法，不是因为看起来更专业，而是它本身就是标准答案。

双向 bfs 是另一个优化场景。从起点和终点同时向外扩展，两个队列分别用 deque 维护，每次从节点数更少的一端扩展一层。判断是否相交时，用集合记录已访问节点。 deque 在这里的好处是两端都能高效弹出，天然适合这种“头尾夹击”的搜索模式。我之前在解“单词接龙”这类最短路径问题时，双向 bfs 的提速非常明显，比单向 bfs 少遍历一半甚至更多的状态。

2.4 轮转调度与约瑟夫环问题

双端队列的 rotate 方法处理循环类问题格外顺手。以约瑟夫环为例：n 个人围成一圈，从 1 开始报数，报到 k 的人出局，然后从下一个人重新报数，问最后剩下的人是几号。传统做法是用数组加取模，代码绕来绕去。用 deque 就很直白——每次把前 k-1 个人从队头搬到队尾，此时队头就是该出局的人，直接弹出。

def josephus(n, k):
    dq = deque(range(1, n + 1))
    while len(dq) > 1:
        dq.rotate(-(k - 1))
        dq.popleft()
    return dq[0]

rotate(-(k-1)) 表示整体向左移动 k-1 次，效果上等同于把第 k 个人转到队首。然后 popleft() 把他移除。实际跑 josephus(7, 3) 的结果是 4，跟手算一致。这种解法虽然没有数学推导那么快，但胜在写起来快、不会写错，面试时能迅速给出可运行版本。

任务轮转调度也是类似逻辑。假设有一组任务要按时间片轮流执行，每个任务执行一次后放到队尾，用 deque 加 rotate(-1) 就能模拟“当前任务出队再入队”的连续过程，代码非常简洁。

3. 剖析底层实现：deque 凭什么两端都是 o(1)

3.1 块状双向链表，不是简单的数组也不是普通链表

cpython 中 deque 的底层实现是“块状双向链表”（block-based doubly linked list）。这名字听着复杂，拆开就两部分：多个“块”（block）之间用双向链表串起来，每个块内部又是一段连续存储元素的定长数组。

每个 block 能存多少元素，跟机器上指针大小有关，cpython 源码里有一个基于 sizeof(void*) 计算的常量，通常是 64 左右。当一个块装满了，就新分配一个块挂到链表末尾；当一块的元素清空，这个块会被释放或者回收。

你可以把每个 block 想象成一节火车车厢，车厢里是一排座位。链表是车厢之间的挂钩。普通链表每个节点只存一个元素，指针开销大，缓存不友好；而块状链表把多个元素放进同一节车厢，既降低了指针占比，又提高了内存访问的局部性。头部和尾部操作的 o(1)，本质上是“只需要在首尾车厢里动座位”，不需要挪动整列火车的乘客。

这跟 list 有本质区别。list 是一整块连续内存，想在头部加一个元素，等于让整列火车所有乘客都站起来挪一个位子。deque 则只需要在第一节车厢里腾个座，或者挂一节新车厢。

3.2 索引和删除操作的复杂度真相

deque 虽然支持下标访问，比如 dq[0] 、 dq[-1] ，但它的索引操作不是 o(1) 的。因为底层是链表，要知道中间某个位置的值，只能从头部或者尾部沿着链逐个块找过去。cpython 的实现会做一个优化：根据下标距离哪一端更近来决定从哪边开始遍历。但不管怎么优化， dq[i] 的平均代价依然是 o(n)。

这是个特别容易踩坑的地方。有人看见 deque 能下标访问，就把它当成“加强版 list”，写 for i in range(len(dq)): print(dq[i]) 。这串代码看着没问题，实际是 o(n^2) 的操作。n 小的时候无感，n 到十万以上就明显卡顿。需要高频随机访问时，老老实实转成 list 再做。

remove 方法也一样。它从左往右扫描找第一个匹配值，最坏情况是 o(n)。 index 、 count 同理。所以 deque 的真正优势集中在“端点操作”，中间的任何操作它都不擅长。一句话总结：deque 的两端是高速公路，中间是乡间小路。

3.3 线程安全与并发边界

很多人不知道，deque 在 cpython 中是线程安全的，前提是你使用的是单个原子操作。 append 、 appendleft 、 pop 、 popleft 这些方法在 gil 的保护下不会被其他线程打断，因此可以用在生产者和消费者模型里，一个线程往里塞数据，另一个线程往外取。

但这不代表你可以放心大胆地在多线程里自由组合操作。比如下面这段代码：

if dq:
    item = dq.popleft()

先判断非空再弹出，中间可能被其他线程插入一次调度，导致队列状态已经变化。这种“检查后操作”的组合不是原子的，需要自己加锁，或者使用 queue.queue 。

queue.queue 本质上就是在 deque 之上包了一层线程安全机制和阻塞通知，它的 put 和 get 提供了完整的多线程语义，还有 task_done 和 join 配合。单线程算法题里没必要用它，但跨线程传递任务时，选择 queue.queue 更省心。这里的边界一定要分清，我在第 4 节的选型表里会再详细整理一次。

4. 性能实测与容器选型：什么时候用 deque 才不会亏

4.1 timeit 实测：list 头部操作 vs deque 头部操作

光说复杂度可能不够直观，我直接上 timeit 跑一组数据。因为 list 的 pop(0) 会改变原列表，重复多次测试每轮需要重新生成数据，所以我分别测“操作 10000 次”的总耗时，并重新初始化容器：

import timeit

setup_list = "lst = list(range(100000))"
setup_deque = "from collections import deque; dq = deque(range(100000))"

# list 从头部弹出一个元素
t_list_pop0 = timeit.timeit("lst.pop(0)", setup=setup_list, number=10000)
# deque 从头部弹出一个元素
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)，差距可以忽略。所以结论非常明确： 只有高频在头部操作时，deque 才值得替换 list 出场 。

4.2 maxlen：有界队列的隐藏利器

deque 构造时接受一个 maxlen 参数，表示队列的最大长度。达到上限后再插入元素，另一端的元素会被自动挤出，形成一个自动滚动的“滑动容器”。

dq = deque(maxlen=3)
for i in range(5):
    dq.append(i)
# 最终结果：deque([2, 3, 4], maxlen=3)

这个特性写日志缓存、实时数据流的最近 n 条记录特别适合。我之前做过一个监控工具，需要在内存里保留每个指标最近 100 条采样点，用 deque(maxlen=100) 一行代码就搞定，不需要自己写“超了就从左端删”的逻辑，比裸 list 优雅太多。

有界队列同样支持 appendleft ，从左边插入时会从右边挤出老元素。 rotate 在有界队列上也可以正常使用。要小心的是， maxlen 一旦设定就不能修改，想改只能重建 deque。

4.3 选型指南：list / deque / queue.queue / priorityqueue

根据我写过代码的经验，这几种容器怎么选，可以按“操作重心”来判断。我整理成一张表，方便你以后直接查：

list 和 deque 之间也不是水火不容。实际开发中，我常把 deque 作为“临时缓冲区”，处理完一批数据后再 list(dq) 转成列表做随机访问或传给下游。两者转换成本不高，不必纠结架构洁癖，哪个顺手用哪个。

5. 常见问题与避坑指南

5.1 别把 deque 当 list 做随机访问

我在 3.2 节强调过索引复杂度的问题，这里再给一个真实案例。有位朋友写一个日志分析脚本，用 deque 存日志行，然后写了个循环 for i in range(len(dq)): dq[i] ... ，跑 50 万条日志直接卡住。改成 for line in dq: 之后立刻流畅，原因是迭代器走链表是 o(n) 的总代价，而按索引逐个访问是 o(n^2)。需要索引访问时，先转 list 再操作，比硬用 deque 快得多。

另一个常见问题是对 deque 用切片。python 的 list 支持 lst[1:3] ，deque 不能直接切片，会报 typeerror: sequence index must be integer, not slice 。想要截取一段，要自己写 itertools.islice 或者转 list 再切。这个问题不致命，但遇到了容易愣一下。

5.2 序列化、深拷贝等隐蔽坑

deque 不能直接被 json.dumps 序列化。你如果写 json.dumps(some_deque) ，会抛 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))

反序列化时再用 deque(json.loads(data)) 装回来。用 pickle 则可以直接序列化 deque 对象，不需要额外转换。

深拷贝方面，deque 和 list 一样是可变容器。 dq.copy() 是浅拷贝，只复制了容器本身，里面的元素如果也是可变对象，修改元素会互相影响。想深拷贝得用 copy.deepcopy(dq) 。这个坑在嵌套结构里很常见，比如 deque 里存了若干个 dict，浅拷贝后修改 dict 字段，原对象也跟着变。

5.3 面试与考试里的双端队列考点

准备面试和 408 考试的同学，双端队列还有一个特殊考点：受限双端队列。数据结构教材里把双端队列分成“输入受限”和“输出受限”两类。输入受限双端队列指一端可插入、可删除，另一端只允许删除；输出受限则恰好相反，一端可插入、可删除，另一端只允许插入。考试题经常给出一个输入序列，问哪些输出序列用受限双端队列是合法的，哪些不合法。

这类题目考的是“两端操作到底受什么限制”的理解，也顺便考察对进出顺序的敏感度。我的建议是画图模拟，不要凭空推理。另一个高频面试题是“如何用两个栈模拟一个双端队列”，核心是把入队操作分散在两个栈上，弹出时从对应栈取，栈空时从另一个栈搬运。这类题的复杂度分析比实现本身更值钱，面试官很爱追问。

还有一个容易混淆的概念： deque 和 collections.defaultdict 里的 deque 没有关系，纯属名字像。前者是容器，后者压根不存在，别在记忆里搞混了。

最后分享一点实操体感

我自己的习惯是，只要在代码里看到“头部插入或删除”的动作，就直接用 deque，不犹豫。很多人一开始觉得 list.pop(0) 也能跑，等数据量上来再改，往往要重构一堆代码。还有一个越用越顺手的小技巧：需要旋转列表时，优先想一下 rotate 能不能解决问题。约瑟夫环、日历翻页、轮播图滚动这类循环场景， rotate 一句顶十句，比手写切片拼接清晰得多。

另外给初学者一个提醒：deque 非常适合 bfs 和滑动窗口，但如果你只是写个不追求性能的小脚本，list 完全没问题，不必为了显得专业强行换容器。合适才是最重要的。希望这篇能把双端队列的“为什么”讲透，你下次写代码的时候，能少几个纠结的时刻。

到此这篇关于python双端队列deque的使用小结的文章就介绍到这了,更多相关python双端队列deque内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！