Python Deque 模块使用详解

什么是Deque

Deque是 “double-ended queue”（双端队列）的缩写，在Python中是一个数据结构。它是一个可在两端添加和删除元素的序列，通俗点说它是一种可以在两端进行操作的序列。

Deque的主要方法

Deque包含以下方法:

方法	描述
append(x)	向右侧添加x元素
appendleft(x)	向左侧添加x元素
clear()	销毁deque，清除数据
count(x)	统计x出现次数
extend(iterable)	在右侧添加可迭代对象
extendleft(iterable)	在左侧添加可迭代对象
pop()	弹出右侧元素
popleft()	弹出左侧元素
remove(x)	删除deque中的x元素，如果没有引发ValueError错误
reverse()	反向deque中现有元素
rotate(n)	向右循环移动n步。如果n是负数，则向左旋转

Deque的示例

下面是两个操作deque的示例，一个是数组倒置，一个是滑动窗口。

数组倒置

from collections import deque

def reverse(arr):
    d = deque()
    for i in arr:
        d.appendleft(i)
    return list(d)

arr = [1, 2, 3, 4, 5]
print(reverse(arr)) # [5, 4, 3, 2, 1]

滑动窗口

from collections import deque

def window(arr, k):
    d = deque()
    res = []
    for i in range(len(arr)):
        if i >= k and d[0] <= i - k: # 检查左端是否超过滑动窗口长度
            d.popleft()
        while d and arr[d[-1]] <= arr[i]: # 检查右端丢弃元素，保证队列单调不升
            d.pop()
        d.append(i) # 将当前下标插入队列
        if i >= k - 1:
            res.append(arr[d[0]]) # 左端元素为窗口最大值
    return res

arr = [1,3,-1,-3,5,3,6,7]
print(window(arr, 3)) # [3, 3, 5, 5, 6, 7]

以上示例展示了如何使用deque进行数组倒置和滑动窗口计算，其语法简单易懂，易于编写。