Python 中 collections 的 deque 使用详解

deque 是 Python 内置的一个双向队列数据类型，具有高效地添加和弹出元素的特性，功能类似于列表，但操作更加高效。

1. 创建 deque 对象

deque 对象可以通过 collections 模块中的 deque 函数来创建，不同于列表，它接收一个 maxlen 参数，用于限制 deque 的最大容量，如果不传入该参数，则 deque 会无限扩容。

from collections import deque

# 创建一个空 deque
d = deque()

# 创建一个带有默认值的 deque（初始容量为 3）
d = deque([1, 2, 3], maxlen=3)

2. 添加元素

双向队列的头部和尾部都可以添加元素。deque 提供了 3 种方法添加元素，分别是：

• append(x): 添加元素 x 到 deque 的右边（即尾部）。
• appendleft(x): 添加元素 x 到 deque 的左边（即头部）。
• extend(iterable): 添加一个可迭代对象的多个元素到 deque 的右边（即尾部）。
• extendleft(iterable): 添加一个可迭代对象的多个元素到 deque 的左边（即头部），注意添加顺序与可迭代对象的顺序相反。

下面是添加元素的示例代码：

d = deque([1, 2, 3])
d.append(4)
print(d)  # deque([1, 2, 3, 4], maxlen=None)

d.appendleft(0)
print(d)  # deque([0, 1, 2, 3, 4], maxlen=None)

d.extend([5, 6])
print(d)  # deque([2, 3, 4, 5, 6], maxlen=None)

d.extendleft([0, -1])
print(d)  # deque([-1, 0, 2, 3, 4, 5, 6], maxlen=None)

3. 弹出元素

弹出元素可以使用 pop() 方法和 popleft() 方法，弹出一个 deque 中的元素，当 deque 为空时，它们会抛出 IndexError 异常。

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

d.pop()  # 弹出 4
print(d)  # deque([1, 2, 3], maxlen=None)

d.popleft()  # 弹出 1
print(d)  # deque([2, 3], maxlen=None)

4. 旋转操作

旋转 deque 的两种方法是 rotate(n) 和 rotate(-n)，它们可以将 deque 的元素向右或者向左移动 n 个位置，当 n > 0 时向右旋转，当 n < 0 时向左旋转，n 的绝对值表示旋转的位数。

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

d.rotate(2)  # 右旋转 2 位
print(d)  # deque([4, 5, 1, 2, 3], maxlen=None)

d.rotate(-2)  # 左旋转 2 位
print(d)  # deque([1, 2, 3, 4, 5], maxlen=None)

5. 示例说明

示例 1：使用 deque 模拟滑动窗口

下面的示例展示了如何使用 deque 来模拟一个滑动窗口。给定一段长度为 n 的数组和一个滑动窗口大小 k，请输出每个滑动窗口的最大值。

import collections

def max_sliding_window(nums, k):
    res = []
    dq = collections.deque()
    for i in range(len(nums)):
        if i >= k and dq[0] <= i-k:
            dq.popleft()
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3, 3, 5, 5, 6, 7]

示例 2：使用 deque 获得滑动平均值

下面的示例展示了如何使用 deque 来计算一个滑动窗口的平均值。这里使用 deque 来维护当前的窗口，每次添加数字时，同时移除超出窗口大小的第一个数，然后计算窗口内的平均值。

import collections

class MovingAverage:

    def __init__(self, size: int):
        self.size = size
        self.nums = collections.deque()
        self.sum = 0

    def next(self, val: int) -> float:
        if len(self.nums) == self.size:
            self.sum -= self.nums.popleft()
        self.sum += val
        self.nums.append(val)
        return self.sum / len(self.nums)

m = MovingAverage(3)
print(m.next(1))  # 1.0
print(m.next(10))  # 5.5
print(m.next(3))  # 4.666666666666667
print(m.next(5))  # 6.0