python必背源代码双端队列deque代码
详细讲解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的根本原因。
必背的进阶操作代码
旋转操作 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边界才发生,大幅减少了分配次数。
理解这个结构能解释一个常见疑问: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)时间移动元素,当图的节点数很大时性能差距非常明显。
场景二:滑动窗口最大值
这是算法面试中的经典题目,也是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。选择的核心依据是操作集中在哪里:
用list的场景:频繁按索引随机访问、切片操作、排序。
deque不擅长的:按索引访问中间元素(O(n))、切片(不支持)、排序(需要先转为list)。
一个容易忽略的细节:deque是线程安全的——append、appendleft、pop、popleft 在CPython中都是原子操作,可以在多线程环境中安全使用,不需要额外加锁。这也是标准库 queue.Queue 底层使用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不多,但每一个方法都有明确的使用场景,记住它们的时间复杂度和行为特点,就能在合适的地方正确使用。
免责声明:本文内容仅供参考,不代表本站观点。转载或引用请注明出处。









