湛江师范学院网站开发技术,工商变更,农产品交易平台,旅游网站开发系统的er图deque#xff08;双端队列#xff09;是Python标准库collections模块中的一个类#xff0c;它支持从两端快速添加和删除元素。deque为固定大小或者可变大小的队列提供了线程安全的实现#xff0c;并且它比使用列表#xff08;list#xff09;来实现相同的功能更为高效。 …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(maxlen3)# 添加元素
d.append(a)
d.append(b)
d.append(c)
print(d) # 输出deque([a, b, c], maxlen3)# 继续添加元素最早添加的元素a将被移除
d.append(d)
print(d) # 输出deque([b, c, d], maxlen3)# 尝试从左侧添加元素同样会移除最早添加的元素
d.appendleft(e)
print(d) # 输出deque([e, c, d], maxlen3)示例3使用deque实现滑动窗口算法
滑动窗口算法常用于数组或列表的子序列问题如寻找最大/最小子序列和。
from collections import dequedef 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()# 添加当前元素的索引到dequewindow.append(i)# 当窗口大小达到k时开始记录窗口内的最大值并尝试移动窗口左边界if i k - 1:result.append(nums[window[0]]) # window[0]是当前窗口内最大值的索引# 如果deque头部的索引已经不在当前窗口内则移除头部索引if window[0] i - k:window.popleft()return resultnums [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 dequedef rotate_array(nums, k):dq deque(nums)dq.rotate(-k) # 逆时针旋转 k 位如果是顺时针旋转则直接写 kreturn 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 dequeclass 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 Nonedef top(self):return self.stack[-1] if self.stack else Nonedef 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 dequedef 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 的灵活性和高效性使得它成为处理序列数据的强大工具。
