python必背源代码双端队列deque代码

Mason
Mason
发布时间:2026-11-17 | 7人浏览过
原创

详细讲解Python标准库collections.deque双端队列的核心源代码,包括基本操作、内部结构原理、必背代码片段及实际应用场景。

Python标准库 collections.deque 是一种双端队列数据结构,支持在两端以O(1)时间复杂度进行添加和删除操作。掌握它的核心代码片段,是Python编程中需要反复使用的基本功。本文从deque的创建、常用操作、内部结构到典型应用场景,逐一给出需要记住的源代码,并解释每段代码背后的原理。

deque的创建与基本操作

deque位于 collections 模块中,使用前需要导入。以下是创建deque和基本操作的代码:

from collections import deque

# 创建空的双端队列
d = deque()

# 从可迭代对象创建
d = deque([1, 2, 3, 4, 5])

# 创建有最大长度限制的deque
d = deque(maxlen=5)

deque可以接受任何可迭代对象作为初始数据,包括列表、元组、字符串和生成器。maxlen 参数设定队列的最大容量——当元素数量超过上限时,对面一端的元素会被自动丢弃。这个特性非常适合实现"滑动窗口"和"最近N条记录"一类的需求。

两端添加和删除

from collections import deque

d = deque([1, 2, 3])

# 右端添加
d.append(4)         # deque([1, 2, 3, 4])

# 左端添加
d.appendleft(0)     # deque([0, 1, 2, 3, 4])

# 右端删除并返回
val = d.pop()       # val=4, deque([0, 1, 2, 3])

# 左端删除并返回
val = d.popleft()   # val=0, deque([1, 2, 3])

这四个方法是deque最核心的操作。与list不同,list的 insert(0, x) 和 pop(0) 需要移动全部元素,时间复杂度为O(n);deque在两端操作均为O(1),这是选择deque替代list的根本原因。

python必背源代码双端队列deque代码
图1:deque双端操作与list的时间复杂度对比

必背的进阶操作代码

旋转操作 rotate

d = deque([1, 2, 3, 4, 5])

# 向右旋转2步:右端元素移到左端
d.rotate(2)          # deque([4, 5, 1, 2, 3])

# 向左旋转1步:左端元素移到右端
d.rotate(-1)         # deque([5, 1, 2, 3, 4])

rotate(n) 将deque整体旋转n步。正数表示右旋(右端元素依次移到左端),负数表示左旋。这个操作的时间复杂度为O(k)(k为旋转步数),在循环缓冲、轮询调度等场景中非常有用。

批量添加 extend 和 extendleft

d = deque([3, 4, 5])

# 在右端批量添加
d.extend([6, 7, 8])       # deque([3, 4, 5, 6, 7, 8])

# 在左端批量添加(注意:逐个添加,结果顺序反转)
d.extendleft([2, 1, 0])   # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

extendleft 的行为需要特别注意:它会逐个调用 appendleft,所以添加后的元素顺序与原始可迭代对象相反。如果传入 [2, 1, 0],先添加2到左端,再添加1到2的左边,最后添加0到1的左边,最终0在最左侧。

查找、计数与删除

d = deque([1, 2, 3, 2, 4, 2])

# 统计元素出现次数
d.count(2)           # 3

# 查找元素位置
d.index(3)           # 2

# 删除第一个匹配的元素
d.remove(2)          # deque([1, 3, 2, 4, 2])

# 反转
d.reverse()          # deque([2, 4, 2, 3, 1])

# 清空
d.clear()            # deque([])

这些方法的行为与list类似,但要知道 index、remove、count 的时间复杂度都是O(n),因为deque不支持按索引快速跳转——它的内部结构是分块的双向链表,不是连续数组。

deque的内部结构原理

CPython中deque的底层实现并非一条简单链表,而是一个由固定大小的块(block)组成的双向链表。每个block可以容纳64个元素(CPython 3.x的默认值)。deque对象维护着指向第一个block和最后一个block的指针,以及左右两端在各自block内的索引位置。

当右端 append 时,如果当前最右block还有空位,直接写入;如果满了,分配一个新block链接到右侧。popleft 同理,从最左block取出元素,block空了就释放。这种设计使得两端操作都是O(1),而内存分配只在block边界才发生,大幅减少了分配次数。

python必背源代码双端队列deque代码
图2:deque底层分块双向链表结构

理解这个结构能解释一个常见疑问:deque支持下标访问(d[i]),但随机访问的时间复杂度是O(n),因为需要从头或尾逐block跳转来定位目标元素。如果你的场景需要频繁按索引读写中间元素,list是更好的选择。

maxlen限定长度的deque

设置 maxlen 后,deque会自动维护固定长度。当新元素加入导致超出上限时,对面一端的元素被自动丢弃,无需手动管理:

from collections import deque

# 只保留最近5条日志
recent_logs = deque(maxlen=5)

for i in range(10):
    recent_logs.append(f"log_{i}")

print(recent_logs)
# 输出: deque(['log_5', 'log_6', 'log_7', 'log_8', 'log_9'], maxlen=5)

这段代码是很多实际系统中"保留最近N条记录"功能的标准写法。比如保留最近10条聊天消息、最近100个监控数据点,或者实现命令行的历史记录功能。一旦创建后,maxlen 属性是只读的,不能修改。

典型应用场景的必背代码

场景一:用deque实现BFS(广度优先搜索)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        node = queue.popleft()    # O(1) 取出队首
        result.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)  # O(1) 加入队尾

    return result

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))
# 示例输出: ['A', 'B', 'C', 'D', 'E', 'F']

BFS是deque最经典的应用场景。如果用list代替deque,list.pop(0) 每次需要O(n)时间移动元素,当图的节点数很大时性能差距非常明显。

python必背源代码双端队列deque代码
图3:使用deque实现BFS的队列操作流程和图的遍历顺序

场景二:滑动窗口最大值

这是算法面试中的经典题目,也是deque应用的标准范例。使用deque维护一个单调递减队列,可以在O(n)时间内找到每个窗口的最大值:

from collections import deque

def max_sliding_window(nums, k):
    """返回大小为k的滑动窗口中的最大值列表"""
    result = []
    dq = deque()  # 存储索引,保持对应值单调递减

    for i, num in enumerate(nums):
        # 移除窗口左边界之外的索引
        while dq and dq[0] < i - k + 1:
            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

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(nums, 3))
# 示例输出: [3, 3, 5, 5, 6, 7]

这段代码值得反复理解的关键点:deque中存储的是索引而不是值,这样才能判断元素是否已经滑出窗口。deque维护的是一个单调递减序列——队首永远是当前窗口的最大值对应的索引。新元素进入时,把所有比它小的元素从右端移除,因为它们在当前元素存在的情况下不可能再成为任何窗口的最大值。

场景三:简单的任务调度器

from collections import deque

def round_robin(tasks, time_slice):
    """简单的轮转调度"""
    queue = deque(tasks)
    execution_log = []

    while queue:
        task_name, remaining = queue.popleft()
        run_time = min(time_slice, remaining)
        remaining -= run_time
        execution_log.append(f"{task_name} 执行 {run_time}s")

        if remaining > 0:
            queue.append((task_name, remaining))

    return execution_log

tasks = [("任务A", 7), ("任务B", 3), ("任务C", 5)]
for log in round_robin(tasks, 3):
    print(log)

# 示例输出:
# 任务A 执行 3s
# 任务B 执行 3s
# 任务C 执行 3s
# 任务A 执行 3s
# 任务C 执行 2s
# 任务A 执行 1s

轮转调度是操作系统中的基本算法,deque的两端操作完美匹配这种"从头取出、处理后放回尾部"的模式。rotate 方法在这类循环调度场景中也经常用到。

deque与list的选择依据

并不是所有场景都适合用deque替代list。选择的核心依据是操作集中在哪里:

用deque的场景:频繁在两端添加/删除元素,如队列、BFS、滑动窗口、日志缓冲。
用list的场景:频繁按索引随机访问、切片操作、排序。
deque不擅长的:按索引访问中间元素(O(n))、切片(不支持)、排序(需要先转为list)。

一个容易忽略的细节:deque是线程安全的——append、appendleft、pop、popleft 在CPython中都是原子操作,可以在多线程环境中安全使用,不需要额外加锁。这也是标准库 queue.Queue 底层使用deque作为存储的原因之一。

python必背源代码双端队列deque代码
图4:deque核心方法、时间复杂度与典型应用总结

完整速查代码模板

以下代码将前面所有关键操作汇总为一个可直接运行的脚本,方便日常查阅和练习:

from collections import deque

# === 1. 创建 ===
d = deque()                    # 空队列
d = deque([1, 2, 3])          # 从列表创建
d = deque('abc')              # 从字符串创建: deque(['a','b','c'])
d = deque(range(5), maxlen=3) # 限定长度: deque([2, 3, 4], maxlen=3)

# === 2. 两端操作(全部 O(1)) ===
d = deque([1, 2, 3])
d.append(4)                   # 右端加: [1, 2, 3, 4]
d.appendleft(0)               # 左端加: [0, 1, 2, 3, 4]
d.pop()                       # 右端删: [0, 1, 2, 3]
d.popleft()                   # 左端删: [1, 2, 3]

# === 3. 批量操作 ===
d.extend([4, 5])              # 右端扩展: [1, 2, 3, 4, 5]
d.extendleft([-1, 0])         # 左端扩展(顺序反转): [0, -1, 1, 2, 3, 4, 5]

# === 4. 旋转 ===
d = deque([1, 2, 3, 4, 5])
d.rotate(2)                   # 右旋: [4, 5, 1, 2, 3]
d.rotate(-2)                  # 恢复: [1, 2, 3, 4, 5]

# === 5. 查询与修改 ===
d = deque([1, 2, 3, 2, 1])
d.count(2)                    # 2
d.index(3)                    # 2
d.remove(2)                   # 删除首个2: [1, 3, 2, 1]
d.reverse()                   # 反转: [1, 2, 3, 1]

# === 6. 转换 ===
lst = list(d)                 # 转list
d2 = deque(sorted(d))         # 排序(需转为list再创建)

# === 7. 复制 ===
import copy
d_copy = d.copy()             # 浅拷贝
d_deep = copy.deepcopy(d)     # 深拷贝

将这份代码保存为一个 .py 文件,遇到deque相关问题时快速查阅,比反复搜索文档更高效。deque的API不多,但每一个方法都有明确的使用场景,记住它们的时间复杂度和行为特点,就能在合适的地方正确使用。

相关专题:

本站声明

本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。

Python 相关产品和应用

全部下载

专题列表