python中的deque详解

云计算 2024年11月22日 09:29 2 admin

在Python中，collections模块提供了一个双端队列（deque），这是一个高度优化的双向链表数据结构。deque支持在两端高效地添加和删除元素，比列表的操作更为高效。本文将详细介绍deque的功能、用法及其在不同场景下的应用。

什么是deque

deque（双端队列）是一种通用的队列，支持在两端插入和删除元素。它的实现基于双向链表，因此在两端进行操作的时间复杂度为O(1)，而在中间进行插入和删除操作的时间复杂度为O(n)。

基本用法

首先，导入 deque类：

froM collections import deque

创建deque

可以通过传递一个可迭代对象来创建deque：

d = deque([1, 2, 3, 4])
print(d)  # 输出：deque([1, 2, 3, 4])

也可以创建一个空的deque：

d = deque()
print(d)  # 输出：deque([])

基本操作

添加元素

在右侧添加：使用 APPend方法。

d.append(5)
print(d)  # 输出：deque([1, 2, 3, 4, 5])

在左侧添加：使用 appendleft方法。

d.appendleft(0)
print(d)  # 输出：deque([0, 1, 2, 3, 4, 5])

删除元素

从右侧删除：使用 pop方法。

d.pop()
print(d)  # 输出：deque([0, 1, 2, 3, 4])

从左侧删除：使用 popleft方法。

d.popleft()
print(d)  # 输出：deque([1, 2, 3, 4])

访问和修改元素

访问元素：可以像访问列表一样通过索引访问元素。
```
print(d[0])  # 输出：1
print(d[-1])  # 输出：4
```
修改元素：同样可以通过索引修改元素。
```
d[0] = 10
print(d)  # 输出：deque([10, 2, 3, 4])
```

高级操作

指定最大长度

可以在创建deque时指定最大长度。当添加元素使deque长度超过指定值时，最旧的元素会被自动移除。

d = deque(maxlen=3)
d.extend([1, 2, 3])
print(d)  # 输出：deque([1, 2, 3], maxlen=3)
d.append(4)
print(d)  # 输出：deque([2, 3, 4], maxlen=3)

批量添加元素

在右侧批量添加：使用 extend方法。

d.extend([5, 6])
print(d)  # 输出：deque([3, 4, 5, 6], maxlen=3)

在左侧批量添加：使用 extendleft方法。

d.extendleft([7, 8])
print(d)  # 输出：deque([8, 7, 3, 4, 5, 6], maxlen=3)

旋转deque

使用 rotate方法可以旋转deque。正数表示向右旋转，负数表示向左旋转。

d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)  # 输出：deque([4, 5, 1, 2, 3])
d.rotate(-3)
print(d)  # 输出：deque([2, 3, 4, 5, 1])

应用场景

队列和栈

由于deque在两端都支持高效的插入和删除操作，因此非常适合作为队列（FIFO）和栈（LIFO）使用。

队列：

queue = deque()
queue.append('task1')
queue.append('task2')
print(queue.popleft())  # 输出：task1

栈：

staCK = deque()
stack.append('task1')
stack.append('task2')
print(stack.pop())  # 输出：task2

滑动窗口

在处理需要滑动窗口的场景时，deque的最大长度特性非常有用。例如，计算滑动窗口的平均值：

def moving_average(iterable, n=3):
    d = deque(maxlen=n)
    for vAlue in iterable:
        d.append(value)
        if len(d) == n:
            print(sum(d) / n)

data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
moving_average(data)
# 输出：
# 2.0
# 3.0
# 4.0
# 5.0
# 6.0
# 7.0
# 8.0

广度优先搜索

在图算法中，deque可以用于实现高效的广度优先搜索（BFS）。

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)

    return visited

graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

print(bfs(graph, 'A'))
# 输出：{'E', 'D', 'F', 'A', 'C', 'B'}

优缺点分析

分析说明表：

优点	解释
高效的两端操作	在两端插入和删除元素的时间复杂度为O(1)，比列表更高效。
灵活性	既可以作为队列（FIFO），也可以作为栈（LIFO）使用。
最大长度限制	可以指定最大长度，当长度超过时自动移除最旧的元素，适合实现滑动窗口。
双向遍历	支持双向遍历，方便实现复杂的数据结构和算法。
内置旋转功能	通过旋转方法轻松实现元素位置的调整。
更高的内存开销	由于基于双向链表实现，deque的内存开销相对较高。
不适合随机访问	由于无法像列表一样通过索引快速访问任意元素，不适合频繁的随机访问场景。