Python deque 详解

什么是 deque？

deque（全称 “double-ended queue”，即双端队列）是 Python 标准库 collections 模块中的一个高效数据结构。 它支持在两端快速地添加（append）和删除（pop）元素，时间复杂度均为 O(1)，非常适合实现队列、栈或滑动窗口等场景。

基本用法示例

from collections import deque

# 创建一个 deque
d = deque([1, 2, 3])

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

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

# 右侧弹出
right = d.pop()      # right = 4

# 左侧弹出
left = d.popleft()   # left = 0

print(d)             # deque([1, 2, 3])

常用方法一览

• append(x)：在右侧添加元素 x
• appendleft(x)：在左侧添加元素 x
• pop()：从右侧移除并返回元素
• popleft()：从左侧移除并返回元素
• extend(iterable)：从右侧批量添加多个元素
• extendleft(iterable)：从左侧批量添加（注意顺序反转）
• rotate(n)：向右旋转 n 步（负数表示向左）
• clear()：清空所有元素

性能优势

与普通列表（list）相比，deque 在首尾操作上具有显著性能优势：

• list.insert(0, x) 和 list.pop(0) 是 O(n) 操作
• deque.appendleft(x) 和 deque.popleft() 是 O(1) 操作

因此，在频繁进行首尾插入/删除的场景中，应优先使用 deque。

典型应用场景

• 实现队列（FIFO）：使用 append() 入队，popleft() 出队
• 实现栈（LIFO）：使用 append() 压栈，pop() 弹栈
• 滑动窗口算法：维护固定大小窗口内的最大值/最小值
• 广度优先搜索（BFS）：用作待访问节点的队列

小贴士

你可以通过设置 maxlen 参数创建一个有最大长度的 deque：

d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)  # 自动丢弃最左侧元素
print(d)     # deque([2, 3, 4], maxlen=3)

这在需要保留最近 N 条记录的场景中非常实用（如缓存、日志等）。