阅读量:0
文章目录
- 摘要
- 示例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]] <= nums[i]: window.pop() # 添加当前元素的索引到deque window.append(i) # 当窗口大小达到k时，开始记录窗口内的最大值，并尝试移动窗口左边界 if i >= k - 1: result.append(nums[window[0]]) # window[0]是当前窗口内最大值的索引 # 如果deque头部的索引已经不在当前窗口内，则移除头部索引 if window[0] <= i - k: window.popleft() return result nums = [1, 3, -1, -3, 5, 3, 6, 7] k = 3 print(max_sliding_window(nums, k)) # 输出：[3, 3, 5, 5, 6, 7] 在这个例子中，deque用于存储当前窗口内元素值的索引，通过维护一个递减的索引队列，我们可以快速找到窗口内的最大值。当窗口向右滑动时，我们更新队列并记录每个窗口的最大值。
在Python中，collections.deque 是一个非常实用的双向队列实现，它可以高效地在队列两端添加或移除元素。以下是一些使用 deque 的示例：
示例 4: 使用 deque 实现旋转数组
from collections import deque def rotate_array(nums, k): dq = deque(nums) dq.rotate(-k) # 逆时针旋转 k 位，如果是顺时针旋转则直接写 k return list(dq) nums = [1, 2, 3, 4, 5, 6, 7] k = 3 rotated_nums = rotate_array(nums, k) print(rotated_nums) # 输出: [5, 6, 7, 1, 2, 3, 4] 示例 5: 使用 deque 实现最大/最小栈
from collections import deque class MaxStack: def __init__(self): self.stack = deque() self.max_stack = deque() def push(self, x): self.stack.append(x) if not self.max_stack or x >= 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 的灵活性和高效性使得它成为处理序列数据的强大工具。
