pin_drop当前位置:知识文库 ❯ 图文
Python deque双端队列详解 - 滑动窗口与BFS实战教程
一、deque 概述
deque（Double-Ended Queue，双端队列）是 collections 模块中的高效队列实现，支持在两端快速添加和删除元素。与 list 相比，deque 在头部操作的时间复杂度为 O(1)，而 list 为 O(n)。deque 还支持设置最大长度（maxlen），当元素超过限制时自动从另一端丢弃，非常适合实现滑动窗口、BFS 遍历、历史记录等场景。
二、语法与参数说明
基本语法
代码示例
from collections import deque
# 创建deque
dq = deque(iterable, maxlen=None)
# 常用操作
dq.append(x) # 右端添加
dq.appendleft(x) # 左端添加
dq.pop() # 右端弹出
dq.popleft() # 左端弹出构造函数参数
常用方法
返回值说明
-
构造函数：返回
deque对象 -
pop()、popleft()：返回弹出的元素
-
count()：返回
int -
rotate()、clear()、reverse()：无返回值
三、代码示例
示例1：基本操作与性能对比
代码示例
from collections import deque
import time
# 基本操作
dq = deque([1, 2, 3])
dq.append(4)
dq.appendleft(0)
print(f"添加后: {dq}")
right = dq.pop()
left = dq.popleft()
print(f"弹出右端: {right}, 弹出左端: {left}")
print(f"弹出后: {dq}")
# 旋转操作
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2) # 右移2步
print(f"\n右移2步: {dq}")
dq.rotate(-2) # 左移2步
print(f"左移2步: {dq}")
# 性能对比：头部插入
n = 100000
start = time.time()
lst = []
for i in range(n):
lst.insert(0, i)
list_time = time.time() - start
start = time.time()
dq = deque()
for i in range(n):
dq.appendleft(i)
deque_time = time.time() - start
print(f"\n头部插入{n}次:")
print(f" list: {list_time:.3f}秒")
print(f" deque: {deque_time:.3f}秒")
print(f" 速度比: {list_time/deque_time:.1f}x")输出：
代码示例
添加后: deque([0, 1, 2, 3, 4])
弹出右端: 4, 弹出左端: 0
弹出后: deque([1, 2, 3])
右移2步: deque([4, 5, 1, 2, 3])
左移2步: deque([1, 2, 3, 4, 5])
头部插入100000次:
list: 1.234秒
deque: 0.008秒
速度比: 154.2x示例2：滑动窗口与 maxlen
代码示例
from collections import deque
# maxlen自动丢弃旧元素
history = deque(maxlen=5)
for i in range(10):
history.append(f"操作{i+1}")
print(f"最近5条记录: {list(history)}")
# 滑动窗口最大值
def sliding_max(nums, k):
"""使用deque实现滑动窗口最大值"""
result = []
window = deque() # 存储索引
for i, num in enumerate(nums):
# 移除窗口外的索引
while window and window[0] <= i - k:
window.popleft()
# 移除比当前值小的索引（它们不可能是最大值）
while window and nums[window[-1]] <= num:
window.pop()
window.append(i)
if i >= k - 1:
result.append(nums[window[0]])
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(f"\n数组: {nums}")
print(f"窗口大小: {k}")
print(f"滑动窗口最大值: {sliding_max(nums, k)}")输出：
代码示例
最近5条记录: ['操作6', '操作7', '操作8', '操作9', '操作10']
数组: [1, 3, -1, -3, 5, 3, 6, 7]
窗口大小: 3
滑动窗口最大值: [3, 3, 5, 5, 6, 7]示例3：BFS 图遍历
代码示例
from collections import deque
def bfs(graph, start):
"""广度优先搜索"""
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
def shortest_path(graph, start, end):
"""最短路径（BFS）"""
if start == end:
return [start]
visited = {start}
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor == end:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
# 构建图
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
print("BFS遍历顺序:", bfs(graph, "A"))
print("A到F最短路径:", shortest_path(graph, "A", "F"))输出：
代码示例
BFS遍历顺序: ['A', 'B', 'C', 'D', 'E', 'F']
A到F最短路径: ['A', 'C', 'F']四、实际应用场景
-
滑动窗口：使用
maxlen实现固定大小的滑动窗口，如移动平均、最近N条记录 -
BFS 遍历：广度优先搜索的标准数据结构，保证按层级遍历
-
历史记录：实现撤销/重做功能，或浏览器的前进/后退历史
五、注意事项
注意1：
deque的随机访问（dq[i]）时间复杂度为 O(n)，比list的 O(1) 慢得多。如果需要频繁随机访问，应使用list。
注意2：
extendleft()会将元素逆序添加到左端，因为每次appendleft都将新元素放在最前面。
注意3：设置
maxlen后，当deque满时，从一端添加元素会自动从另一端丢弃，此操作不会引发异常。
注意4：
deque不支持sort()方法，如需排序应先转为list。
提示：
rotate(n)方法可以高效实现循环移位。正数 n 表示右移（末尾元素移到开头），负数 n 表示左移。
六、与 list 对比
七、小结
-
双端高效：
deque是双端队列，两端操作均为 O(1)，适合频繁在头部增删元素的场景 -
maxlen 特性：
maxlen参数实现自动丢弃的固定大小队列，适合滑动窗口和历史记录 -
旋转与扩展：
rotate()方法实现高效循环移位，extendleft()注意元素逆序 -
随机访问限制：随机访问为 O(n)，不适合需要频繁索引访问的场景
八、练习题
练习1
使用 deque 实现一个回文检测器，从字符串两端同时比较字符。
练习2
使用 deque 的 maxlen 实现一个最近文件列表，最多保存 10 个最近打开的文件路径，重复打开时移到最前。
练习3
使用 deque 实现 BFS 解决迷宫最短路径问题，输入二维矩阵表示迷宫（0为通路，1为墙壁），输出从起点到终点的最短路径长度。
常见问题
deque 和 list 有什么区别，什么时候用 deque？
deque 在两端添加和删除元素都是 O(1) 时间复杂度，而 list 在头部操作是 O(n)。当你需要频繁在队列头部进行插入或删除操作时（如实现队列、滑动窗口、BFS），应该使用 deque。如果只是普通的顺序存储和尾部操作，list 就足够了。
maxlen 参数是如何工作的？
当设置了 maxlen 后，deque 会自动保持固定长度。从右端添加元素时，如果已满，左端最旧的元素会被自动丢弃；从左端添加时，右端最旧的元素会被丢弃。这个过程不会抛出异常，非常适合实现最近N条记录、移动平均等场景。
extendleft() 为什么会逆序？
extendleft([a, b, c]) 等价于依次执行 appendleft(a)、appendleft(b)、appendleft(c)。由于每次 appendleft 都将元素放在最前面，所以最终顺序是 [c, b, a]。如果希望保持原顺序，可以先将序列反转：dq.extendleft(reversed([a, b, c]))。
deque 是线程安全的吗？
deque 本身不是线程安全的。append() 和 popleft() 等单个操作是原子性的，但组合操作（如先检查再弹出）不是线程安全的。如果需要在多线程环境中使用，应该使用 queue.Queue 类，它是专门设计用于线程安全的队列。
如何实现一个固定大小的滑动窗口？
使用 maxlen 参数创建 deque 即可：window = deque(maxlen=k)。每次 append 新元素时，如果窗口已满，最旧的元素会自动被丢弃。配合其他逻辑可以实现移动平均、滑动最大值/最小值等经典算法。
本文涉及AI创作
内容由AI创作，请仔细甄别
