python中的deque详解

文章目录

• 摘要
• 示例1：基本使用
• 示例2：使用maxlen限制队列长度
• 示例3：使用deque实现滑动窗口算法
• 示例 4: 使用 deque 实现旋转数组
• 示例 5: 使用 deque 实现最大/最小栈
• 示例 6: 使用 deque 实现广度优先搜索（BFS）

  摘要

  deque（双端队列）是Python标准库collections模块中的一个类，它支持从两端快速添加和删除元素。deque为固定大小或者可变大小的队列提供了线程安全的实现，并且它比使用列表（list）来实现相同的功能更为高效。

  

  deque的主要特点和操作包括：

  • 快速从两端添加和删除元素：deque在两端添加和删除元素的时间复杂度都是O(1)，而列表在列表头部添加或删除元素的时间复杂度是O(n)。
  • 线程安全：deque的实例可以在多线程环境中安全使用，而不需要额外的锁定。
  • 可选的最大长度：可以通过maxlen参数来限制deque的最大长度。当deque已满时，添加新元素会导致最早添加的元素被自动移除。

    下面是deque的一些详细示例：

    示例1：基本使用

    from collections import deque
    # 创建一个空的deque
    d = deque()
    # 从右侧添加元素
    d.append('a')
    d.append('b')
    print(d)  # 输出：deque(['a', 'b'])
    # 从左侧添加元素
    d.appendleft('c')
    print(d)  # 输出：deque(['c', 'a', 'b'])
    # 从右侧移除元素
    right_item = d.pop()
    print(right_item)  # 输出：'b'
    print(d)  # 输出：deque(['c', 'a'])
    # 从左侧移除元素
    left_item = d.popleft()
    print(left_item)  # 输出：'c'
    print(d)  # 输出：deque(['a'])
    

    示例2：使用maxlen限制队列长度

    from collections import deque
    # 创建一个最大长度为3的deque
    d = deque(maxlen=3)
    # 添加元素
    d.append('a')
    d.append('b')
    d.append('c')
    print(d)  # 输出：deque(['a', 'b', 'c'], maxlen=3)
    # 继续添加元素，最早添加的元素'a'将被移除
    d.append('d')
    print(d)  # 输出：deque(['b', 'c', 'd'], maxlen=3)
    # 尝试从左侧添加元素，同样会移除最早添加的元素
    d.appendleft('e')
    print(d)  # 输出：deque(['e', 'c', 'd'], maxlen=3)
    

    示例3：使用deque实现滑动窗口算法

    滑动窗口算法常用于数组或列表的子序列问题，如寻找最大/最小子序列和。

    from collections import deque
    def max_sliding_window(nums, k):
        # 使用deque保存窗口中的最大值索引
        window = deque()
        result = []
        for i in range(len(nums)):
            # 如果deque不为空且当前元素大于deque尾部元素对应的值，则移除尾部元素
            while window and nums[window[-1]] = k - 1:
                result.append(nums[window[0]])  # window[0]是当前窗口内最大值的索引
                # 如果deque头部的索引已经不在当前窗口内，则移除头部索引
                if window[0] = self.max_stack[-1]:
                self.max_stack.append(x)
        def pop(self):
            if self.stack:
                if self.stack[-1] == self.max_stack[-1]:
                    self.max_stack.pop()
                return self.stack.pop()
            return None
        def top(self):
            return self.stack[-1] if self.stack else None
        def getMax(self):
            return self.max_stack[-1] if self.max_stack else None
    # 使用示例
    max_stack = MaxStack()
    max_stack.push(5)
    max_stack.push(7)
    max_stack.push(1)
    max_stack.push(5)
    print(max_stack.getMax())  # 输出: 7
    max_stack.pop()
    print(max_stack.top())  # 输出: 5
    print(max_stack.getMax())  # 输出: 7
    

    在这个例子中，MaxStack 类使用两个 deque：一个用于存储栈的元素，另一个用于存储当前栈中的最大值。这样，我们可以在常数时间内获取栈顶的最大值。

    

    示例 6: 使用 deque 实现广度优先搜索（BFS）

    在图的遍历中，deque 常用于实现广度优先搜索（BFS）。

    from collections import deque
    def bfs(graph, root):
        visited = set()
        queue = deque([root])
        while queue:
            vertex = queue.popleft()
            print(vertex, end=" ")
            for neighbour in graph[vertex]:
                if neighbour not in visited:
                    visited.add(neighbour)
                    queue.append(neighbour)
    # 图的邻接表表示
    graph = {
        'A': ['B', 'C'],
        'B': ['D', 'E'],
        'C': ['F'],
        'D': [],
        'E': ['F'],
        'F': []
    }
    bfs(graph, 'A')  # 输出: A B C D E F
    

    在上面的例子中，我们使用 deque 作为队列来存储待访问的节点，实现了图的广度优先搜索。

    这些示例展示了 deque 在不同场景下的应用，从基本的队列操作到更复杂的算法实现。deque 的灵活性和高效性使得它成为处理序列数据的强大工具。