python deque模块简单使用代码实例

当我们在Python中需要实现简单的队列或双向队列数据结构时，可以使用Python的deque模块。本文将详细讲解Python deque模块的简单使用代码实例，并提供两个示例来说明使用deque的好处。

什么是Python deque模块？

deque模块是Python标准库 collections 中的一个子模块，提供了一个双向队列的数据结构，支持高效的插入、删除、旋转等操作，并提供了线程安全的备选实现。

Python deque模块的简单使用代码实例

示例1：使用deque实现队列数据结构

考虑以下代码：

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)

print(queue.popleft())
print(queue.popleft())
print(queue.popleft())

在以上代码示例中，我们使用deque创建了一个队列数据结构，并向队列中添加了3个元素。我们使用popleft()方法从队列的左端弹出元素。

输出：

1
2
3

可以看到，我们从队列中弹出的元素的顺序是我们添加的顺序。

示例2：使用deque实现滑动窗口

考虑以下代码：

from collections import deque

def max_in_window(arr, k):
    n = len(arr)
    if k > n or k <= 0:
        return []

    # 创建一个双向队列
    dq = deque()
    res = []

    for i in range(n):
        # 从队列右边移除超过k范围的元素
        # i - k为当前滑动窗口的左边界
        while dq and i - k == dq[0]:
            dq.popleft()
        # 从队列右边移除比当前元素小的元素
        while dq and arr[dq[-1]] < arr[i]:
            dq.pop()
        # 将当前元素的下标入队
        dq.append(i)
        # 如果当前i已经到达k-1，即当前窗口已经形成
        # 那么dq的左边界存储的就是窗口内最大值的下标
        if i >= k - 1:
            res.append(arr[dq[0]])

    return res


arr = [4, 3, 5, 4, 3, 3, 6, 7]
k = 3
print(max_in_window(arr, k))

在以上代码示例中，我们实现了一个函数max_in_window，这个函数接收两个参数arr和k，其中arr是一个数组，k是一个数字，表示窗口的大小。max_in_window函数返回一个数组，其中存储的是在arr中每个大小为k的窗口中的最大值。

我们使用deque模拟滑动窗口，dq中存储的是窗口中元素的下标，每次向右移动窗口时，首先从队列左端移除超出窗口范围的元素，然后从队列右端依次移除比当前元素小的元素，最后将当前元素的下标加入队列。此时队列的左端就存储着窗口中最大元素的下标，当i大于等于k-1时，即窗口满足大小要求时，dq的左端既是窗口内的最大值。

输出：

[5, 5, 5, 4, 6, 7]

可以看到，我们成功地实现了每个窗口中的最大值的搜索。

总结

本文介绍了Python deque模块的简单使用代码实例，包括如何使用deque实现队列数据结构，以及如何使用deque实现滑动窗口。这些代码示例有助于开发者更好地理解deque模块的使用，提升开发效率。