【Python】全面掌握 Collections Deque：队列与栈的高效实现及动态内存管理指南_puthon deque特点

本文章主要探讨 Python collections 模块中的 deque 类，详尽介绍了其定义、特性、构造方法、操作技巧、实际应用场景以及其使用时的注意事项和局限性。

第一章：deque 的定义和特性

1. 什么是双端队列（deque）

deque，全名为双端队列（Double-Ended Queue），是一个由 Python 的 collections 模块提供的容器类型。它支持从两端进行元素的快速添加和删除操作。deque 是线程安全的，可以在不使用锁的情况下从两端操作，这使得它特别适合用于多线程编程中实现数据共享的队列。

在 deque 中，可以使用 append 来在队列的右端添加元素，使用 appendleft 在队列的左端添加元素。同样地，可以使用 pop 从右端删除元素，使用 popleft 从左端删除元素。这种灵活性使得 deque 不仅可以用作普通的队列，也可以作为栈使用，非常适合需要双向操作的场合。

2. deque 与普通列表（list）的性能差异

deque 和 Python 的内置列表（list）在使用和功能上有着明显的区别，特别是在性能方面：

• 从两端添加或删除元素： 对于 deque，无论是从前端还是后端添加或删除元素，时间复杂度都是 O(1)。这得益于 deque 的数据结构设计，它允许两端都能高效地进行修改操作。相比之下，列表在尾部添加或删除元素（使用 append 和 pop）的效率也很高（O(1)），但在列表的开头插入或删除元素（如使用 insert(0, value) 或 pop(0)）时，性能会显著下降，因为这涉及到移动列表中的所有其他元素，时间复杂度为 O(n)，其中 n 是列表的长度。
• 内存效率： deque 在内存使用上通常比列表更加高效，因为它在两端的操作减少了内存重新分配的次数。列表在达到其容量极限时需要进行整体的内存重新分配，而 deque 则通过一个链表的形式分散存储，每次内存分配影响的范围较小。

由于这些特性，deque 是解决需要频繁修改两端元素的问题的理想选择，而列表则更适合那些主要进行尾部操作和顺序访问的任务。

第二章：构造函数

1. 如何创建一个 deque

要使用 deque，首先需要从 collections 模块中导入它。创建一个 deque 对象的基本方法非常简单，可以直接通过将一个可迭代对象传递给 deque 的构造函数来完成，这与创建列表类似。

from collections import deque

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

# 使用列表初始化 deque
d = deque([1, 2, 3, 4, 5])

# 使用字符串初始化，每个字符作为一个元素
d = deque("hello")
1
2
3
4
5
6
7
8
9
10

2. 可选参数 maxlen 的作用和使用场景

deque 的构造函数还接受一个名为 maxlen 的可选参数。这个参数用于设置 deque 可以容纳的最大元素数量。当设定了 maxlen 并且在 deque 中添加元素使其达到最大容量时，每当添加一个新元素，另一端的元素会被自动移除。

# 创建一个最大长度为 3 的 deque
d = deque([1, 2, 3], maxlen=3)

# 当尝试添加更多元素时，最旧的元素将被自动移除
d.append(4)  # deque([2, 3, 4])
d.appendleft(1)  # deque([1, 2, 3])
1
2
3
4
5
6

这个特性非常适合于需要限制容量的应用场景，如缓存机制或最近使用的项目（LRU）缓存。当只需要跟踪最新的几个项目时，使用 maxlen 可以自动维护 deque 的大小，避免手动删除老旧元素的复杂性。

第三章：添加和删除元素

deque 提供了多种方法来动态地添加和删除元素，使其非常适用于需要频繁修改的数据结构应用场景。以下是 deque 的基本操作方法的详细介绍。

1. 使用 append 方法在右端添加元素

append 方法是用于在 deque 的右端添加新元素的基本方法。这种操作非常快速，因为它不涉及元素之间的移动，只涉及到对尾部的访问和修改。

from collections import deque

d = deque([1, 2, 3])
d.append(4)  # 在右端添加元素
print(d)  # 输出: deque([1, 2, 3, 4])
1
2
3
4
5

这个方法通常用于实现栈（后进先出）或队列（先进先出）的操作。

2. 使用 appendleft 方法在左端添加元素

与 append 相对应，appendleft 方法允许用户在 deque 的左端添加新元素。这同样是一个时间复杂度为 O(1) 的操作，使得 deque 在需要从两端动态修改数据时表现出色。

d.appendleft(0)  # 在左端添加元素
print(d)  # 输出: deque([0, 1, 2, 3, 4])
1
2

appendleft 非常适合于需要从前端推入数据的场景，例如在某些特定的数据流或缓冲区操作中。

3. 使用 pop 方法从右端删除元素

pop 方法用于从 deque 的右端移除并返回最后一个元素，这是实现栈结构的标准操作。由于 deque 的设计，这种操作同样具有很高的效率（O(1)）。

last_item = d.pop()  # 移除并返回右端元素
print(last_item)  # 输出: 4
print(d)  # 输出: deque([0, 1, 2, 3])
1
2
3

4. 使用 popleft 方法从左端删除元素

popleft 方法是 deque 中从左端移除并返回第一个元素的方法。这一操作对于实现队列结构至关重要，允许快速的从队列头部移除元素。

first_item = d.popleft()  # 移除并返回左端元素
print(first_item)  # 输出: 0
print(d)  # 输出: deque([1, 2, 3])
1
2
3

第四章：访问和旋转元素

尽管 deque 主要设计用于高效地从两端添加和删除元素，它也支持通过索引访问单个元素。然而，相比列表，deque 在中间元素的访问效率方面有一定的限制。

1. 如何访问 deque 中的元素

deque 支持通过索引访问元素，这类似于列表的索引方式。可以直接使用索引操作符访问任意位置的元素。

from collections import deque
d = deque([0, 1, 2, 3, 4])

# 访问第一个元素
print(d[0])  # 输出: 0

# 访问最后一个元素
print(d[-1])  # 输出: 4
1
2
3
4
5
6
7
8

尽管这种访问方式在语法上很直接，但需要注意的是，deque 中元素的随机访问不如列表高效，特别是在 deque 很大时。这是因为 deque 是用链表实现的，链表的随机访问性能相比于数组来说较差。

2. deque 的索引和切片操作

与列表不同，deque 并不直接支持切片操作，即不能直接使用切片语法如 d[0:3] 来获取 deque 的一部分。如果需要执行切片操作，可以先将 deque 转换为列表，再进行切片，或者使用 itertools.islice 实现更高效的切片。

# 将 deque 转换为列表进行切片
d_list = list(d)
print(d_list[0:3])  # 输出: [0, 1, 2]

# 使用 itertools.islice 进行切片
from itertools import islice
slice_result = islice(d, 0, 3)
print(list(slice_result))  # 输出: [0, 1, 2]
1
2
3
4
5
6
7
8

虽然操作有那么一些复杂，但它们提供了在需要时对 deque 进行灵活处理的方法。

deque 更多地被用于那些主要涉及到在两端添加或移除元素的情况，而不是频繁地随机访问中间元素。如果需要经常访问集合中间的元素，可能需要考虑是否有其他更适合的数据结构，如列表。当然，deque 提供了足够的功能来高效地处理数据，尤其是涉及队列和栈操作。

3. deque 的 rotate 方法

deque 提供了一个非常有用的方法 rotate，可以旋转队列中的元素。这个方法可以向右或向左旋转 deque 中的元素，使得部分元素从一端移到另一端，非常适合于需要循环移位操作的场景。

rotate 方法接受一个参数 n。如果 n 是正数，deque 将会向右旋转；如果 n 是负数，则向左旋转。旋转操作的效果是将 deque 尾部的元素移动到前面，或者将前面的元素移动到尾部。

from collections import deque

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

# 向右旋转
d.rotate(1)
print(d)  # 输出: deque([5, 1, 2, 3, 4])

# 向左旋转
d.rotate(-1)
print(d)  # 输出: deque([1, 2, 3, 4, 5])
1
2
3
4
5
6
7
8
9
10
11

这种方法特别适合于需要周期性调整元素位置的应用，例如在某些算法中循环移位数组或处理缓冲流的数据。

第五章：扩展 deque

deque 提供了灵活的方法来扩展现有的双端队列，允许从两端迅速添加多个元素。这些功能特别适合于在执行批量操作时维护队列的效率和顺序。

1. 使用 extend 方法在右端扩展多个元素

extend 方法允许将一个可迭代对象中的元素添加到 deque 的右端。这个方法可以一次性添加多个元素，是扩展 deque 的一种高效方式。使用 extend 方法可以保持元素的添加顺序，与单独使用多次 append 方法相比，extend 在处理大量数据时更高效。

from collections import deque
d = deque([1, 2, 3])

# 使用 extend 在右端添加多个元素
d.extend([4, 5, 6])
print(d)  # 输出: deque([1, 2, 3, 4, 5, 6])
1
2
3
4
5
6

这种方法在需要将多个数据源或批量数据快速合并到现有队列中时非常有用，例如在数据流处理或批量文件处理中。

2. 使用 extendleft 方法在左端扩展多个元素

与 extend 类似，extendleft 方法允许将一个可迭代对象中的元素从左端添加到 deque 中。不同之处在于，extendleft 会逆序添加元素，因为它是从左端一次添加一个元素，所以首先添加的元素会被推到更远的位置。

# 使用 extendleft 在左端添加多个元素
d.extendleft([0, -1, -2])
print(d)  # 输出: deque([-2, -1, 0, 1, 2, 3, 4, 5, 6])
1
2
3

extendleft 方法的这种特性使得它在特定场景下非常有用，如需要反向保持元素添加的顺序时。然而，这也可能导致一些混淆，因为添加元素的顺序与 extend 是相反的。使用时需要特别注意这一点。

第六章：限制和性能考虑

当使用 deque 时，了解其性能限制和效率特点是至关重要的。这包括对 maxlen 属性的影响以及内存和操作效率的考量。

1. maxlen 属性的影响

maxlen 属性为 deque 设置了一个固定的长度限制。这意味着一旦 deque 达到了设定的最大长度，每当新元素被添加进来，最老的元素会自动被从另一端移除。这种机制有助于保持 deque 的大小不会无限增长，特别是在内存有限的环境中或者处理连续的数据流时。

from collections import deque

# 创建一个最大长度为 5 的 deque
d = deque(maxlen=5)
d.extend([1, 2, 3, 4, 5])
print(d)  # 输出: deque([1, 2, 3, 4, 5], maxlen=5)

# 添加新元素，自动移除最老元素
d.append(6)
print(d)  # 输出: deque([2, 3, 4, 5, 6], maxlen=5)
1
2
3
4
5
6
7
8
9
10

使用 maxlen 可以防止内存泄漏，确保 deque 不会因积累过多无关数据而影响性能。然而，这也意味着数据会丢失，因此在需要保留全部历史数据的应用中，使用 maxlen 需要谨慎。

2. deque 的内存效率和操作效率

内存效率：deque 通过使用双向链表实现，可以实现两端的快速添加和删除操作，而不需要为整个容器重新分配内存。这与列表相比，在进行大量的插入和删除操作时可以显著减少内存的使用和提高性能。

操作效率：

• 两端操作：deque 在其两端进行添加或删除操作都具有 O(1) 的时间复杂度，这使得它在实现如队列和栈等数据结构时非常高效。
• 随机访问：尽管 deque 支持索引访问，但其效率低于列表，因为链表需要从头开始遍历到指定位置，时间复杂度为 O(n)。因此，如果依赖于频繁的随机访问，deque 可能不是最优选择。
• 扩展操作：extend 和 extendleft 方法使得 deque 能够快速地从两端批量添加元素，这在处理大量数据时特别有用。

第七章：实际应用场景

deque 由于其独特的性能特性和灵活的操作方式，在许多编程问题中都有广泛的应用。下面列举了一些典型的使用场景，展示了 deque 在实际中的有效应用。

1. 实现队列和栈

由于 deque 支持从两端高效地添加和删除元素，它非常适合用于实现数据结构如队列（先进先出）和栈（后进先出）。

• 队列： deque 可以用作队列，其中元素从一端添加（通常是右端），从另一端（左端）移除。这模拟了队列的操作，适合于任务调度和消息处理等场景。

  from collections import deque
  queue = deque()
  queue.append('任务1')
  queue.append('任务2')
  queue.popleft()  # '任务1' 被处理
  1
  2
  3
  4
  5

• 栈： deque 也可以用作栈，其中元素从同一端添加和删除，模拟了栈的后进先出的特性。

  stack = deque()
  stack.append('页面1')
  stack.append('页面2')
  stack.pop()  # '页面2' 被访问
  1
  2
  3
  4

2. 实现滑动窗口

滑动窗口是一种常见的数据结构，用于处理连续数据流中的问题，如计算移动平均或滑动最大/最小值。deque 由于其两端操作的高效性，非常适合于实现滑动窗口的功能。

代码实现

from collections import deque

def maxSlidingWindow(nums, k):
    # 结果列表
    max_elements = []
    # 双端队列，用于存储可能是当前窗口最大值的元素索引
    d = deque()

    for i, num in enumerate(nums):
        # 移除所有小于当前元素的队尾元素的索引
        while d and nums[d[-1]] < num:
            d.pop()
        
        # 添加当前元素的索引到队列尾部
        d.append(i)

        # 检查队首元素是否超出窗口范围
        if d[0] == i - k:
            d.popleft()
        
        # 当索引大于等于窗口大小减1时，队首元素为当前窗口的最大值
        if i >= k - 1:
            max_elements.append(nums[d[0]])
    
    return max_elements

# 示例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(maxSlidingWindow(nums, k))  # 输出: [3, 3, 5, 5, 6, 7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

时间复杂度：$O(n)$，其中 n 是数组长度。每个元素最多被添加和移除队列一次。

维护 deque 的递减性质

每当一个新元素（比如当前元素为 num）需要加入到 deque 时，会执行以下操作：

1. 移除队尾小于当前元素的所有元素：
   • 检查 deque 的队尾元素，如果队尾元素对应的数组值小于当前元素 num，则将这些元素从 deque 中移除。这是因为这些元素不可能再成为后续窗口的最大值了（当前元素更大，且更晚离开窗口）。
   • 这个过程会一直持续，直到 deque 为空或者队尾元素大于等于当前元素为止。
   • 这确保了当当前元素被加入 deque 后，deque 依然维持从左到右的递减顺序。
2. 添加当前元素的索引到队尾：
   • 紧接着将当前元素的索引添加到 deque 的队尾。
   • 因为之前已经移除了所有小于它的元素，所以保持了 deque 的递减性质。

例子解析

以 nums = [1, 3, -1, -3, 5, 3, 6, 7] 和 k = 3 为例，考虑每一步的 deque 变化来理解：

• 第一步：i=0, num=1
  • deque = [0]，只有一个元素，无需比较。
• 第二步：i=1, num=3
  • deque = [0] 中，索引0对应的值是1，小于3，所以移除。
  • deque = [1]，现在 deque 只包含当前最大值3的索引。
• 第三步：i=2, num=-1
  • deque = [1] 中，索引1对应的值是3，大于-1，所以不移除。
  • deque = [1, 2]，虽然-1不是最大值，但保留其索引以保持窗口大小。
• 第四步：i=3, num=-3
  • 类似地，deque = [1, 2]，3和-1都大于-3，所以 deque 更新为 [1, 2, 3]。

检查和移除逻辑

• 检查条件：if d[0] == i - k 这行代码检查 deque 的队首元素的索引是否等于 i - k。这里，i - k 是当前索引 i 减去窗口大小 k，得到的是当前窗口的前一个位置。如果 deque 的队首元素索引等于这个值，这意味着队首元素是窗口移动前的一个元素，现在已经不在当前窗口范围内了（已经超出了窗口的左边界）。
• 移除操作：如果上述条件成立，使用 d.popleft() 从 deque 的左端移除该过期的元素索引。这确保了 deque 始终只包含当前窗口范围内的元素索引，且队首是当前窗口的最大值的索引。

3. 广度优先搜索 (BFS)

在图或树的遍历中，广度优先搜索通常使用队列来维护当前层的节点。deque 由于其从两端高效地添加和删除操作，非常适合用作这类算法的数据结构基础。

from collections import deque

def bfs(graph, start):
    # 初始化一个集合来存储已访问过的节点，防止重复访问
    visited = set()
    # 初始化一个双端队列，开始时只包含起始节点
    queue = deque([start])

    # 循环执行，直到队列为空
    while queue:
        # 从队列的左端移除一个元素，这保证了按层次顺序访问
        vertex = queue.popleft()

        # 如果这个节点未被访问过，则进行处理
        if vertex not in visited:
            # 将节点标记为已访问
            visited.add(vertex)
            # 找出所有未访问的邻居节点并加入队列，保证这些节点将在未来被访问
            # graph[vertex] 访问当前节点的邻居
            # - visited 确保只添加还未访问的邻居
            queue.extend(graph[vertex] - visited)

    # 返回所有从起始节点可达的节点集合
    return visited

# 示例图的遍历
graph = {1: {2, 3}, 2: {4}, 3: {4}, 4: {5}, 5: {}}
print(bfs(graph, 1))  # 输出: {1, 2, 3, 4, 5}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

第八章：注意事项和局限性

虽然 deque 在许多情况下表现出色，特别是在涉及到双端操作的场景中，但它并不总是最优的数据结构选择。了解 deque 的局限性和何时不应使用它是非常重要的。

1. deque 的局限性

• 随机访问性能：尽管 deque 支持索引访问，但由于其底层是双向链表的实现，所以在随机访问时的性能不如数组或列表。每次访问都可能涉及从头节点或尾节点开始的遍历，尤其是访问中间元素时，性能会明显下降。
• 不支持切片操作：deque 不支持直接的切片操作，这在需要执行大量基于位置的操作时可能不太方便。虽然可以通过转换为列表来间接实现，但这种转换本身就会带来额外的性能开销。
• 内存使用：与具有紧凑内存布局的数组相比，deque 的每个元素都可能需要更多的内存开销，因为除了存储数据外，还需要额外的空间来维护前驱和后继的链接。

2. 何时不应使用 deque

• 需要频繁随机访问的场景：如果依赖于频繁的、快速的随机访问操作，使用列表或动态数组可能是更好的选择。例如，在需要经常访问或修改中间位置元素的大型数据集时，列表的性能通常会优于 deque。
• 大规模数据处理时的内存考量：虽然 deque 在添加和删除操作中非常高效，但如果要常大的数据集并且内存使用是一个关键考虑因素，更紧凑的数据结构（如数组）可能更合适。
• 高度依赖切片操作的应用：在需要大量使用切片操作来处理数据的应用中，deque 的不支持直接切片可能成为一个限制。在这种情况下，列表或其他支持切片的数据结构可能更为适宜。

参考：

• Fun with deques in Python
• Sliding Window Maximum
• Understanding Python deque (Double-Ended Queue)