Python deque 函数详解

什么是 deque？

deque（读作 “deck”）是 Python 标准库 collections 模块中提供的一个双端队列数据结构。 它支持在两端高效地添加（append）和弹出（pop）元素，时间复杂度均为 O(1)，比使用列表（list）模拟队列或栈更高效。

基本用法

首先需要导入：

from collections import deque

d = deque([1, 2, 3])
d.append(4)        # 右侧添加 → [1, 2, 3, 4]
d.appendleft(0)    # 左侧添加 → [0, 1, 2, 3, 4]
d.pop()            # 右侧弹出 → 返回 4，队列变为 [0, 1, 2, 3]
d.popleft()        # 左侧弹出 → 返回 0，队列变为 [1, 2, 3]

常用方法一览

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

性能优势

使用列表（list）在头部插入或删除元素的时间复杂度为 O(n)，而 deque 在两端的操作均为 O(1)， 特别适合实现队列（FIFO）、栈（LIFO）或滑动窗口等场景。

from collections import deque

queue = deque()
queue.append('A')   # 入队
queue.append('B')
print(queue.popleft())  # 出队 → 'A'

实际应用场景

1. 广度优先搜索（BFS）：用 deque 作为待访问节点队列
2. 滑动窗口算法：维护固定大小的窗口，快速进出元素
3. 撤销/重做功能：用双端队列记录操作历史
4. 日志缓冲：只保留最近 N 条日志

限制最大长度（maxlen）

创建 deque 时可指定 maxlen 参数，自动限制队列长度。当新元素加入导致超出长度时，另一端的元素会自动被移除。

d = deque(maxlen=3)
d.append(1)  # [1]
d.append(2)  # [1, 2]
d.append(3)  # [1, 2, 3]
d.append(4)  # [2, 3, 4] ← 自动丢弃最左边的 1