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：基本使用fromcollectionsimportdeque#创建一个空的dequed=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'])1234567891011121314151617181920212223'运行运行示例2：使用maxlen限制队列长度fromcollectionsimportdeque#创建一个最大长度为3的dequed=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)123456789101112131415161718'运行运行示例3：使用deque实现滑动窗口算法滑动窗口算法常用于数组或列表的子序列问题，如寻找最大/最小子序列和。fromcollectionsimportdequedefmax_sliding_window(nums,k):#使用deque保存窗口中的最大值索引window=deque()result=[]foriinrange(len(nums)):#如果deque不为空且当前元素大于deque尾部元素对应的值，则移除尾部元素whilewindowandnums[window[-1]]=k-1:result.append(nums[window[0]])#window[0]是当前窗口内最大值的索引#如果deque头部的索引已经不在当前窗口内，则移除头部索引ifwindow[0]=self.max_stack[-1]:self.max_stack.append(x)defpop(self):ifself.stack:ifself.stack[-1]==self.max_stack[-1]:self.max_stack.pop()returnself.stack.pop()returnNonedeftop(self):returnself.stack[-1]ifself.stackelseNonedefgetMax(self):returnself.max_stack[-1]ifself.max_stackelseNone#使用示例max_stack=MaxStack()max_stack.push(5)max_stack.push(7)max_stack.push(1)max_stack.push(5)print(max_stack.getMax())#输出:7max_stack.pop()print(max_stack.top())#输出:5print(max_stack.getMax())#输出:71234567891011121314151617181920212223242526272829303132333435'运行运行在这个例子中，MaxStack类使用两个deque：一个用于存储栈的元素，另一个用于存储当前栈中的最大值。这样，我们可以在常数时间内获取栈顶的最大值。示例6:使用deque实现广度优先搜索（BFS）在图的遍历中，deque常用于实现广度优先搜索（BFS）。fromcollectionsimportdequedefbfs(graph,root):visited=set()queue=deque([root])whilequeue:vertex=queue.popleft()print(vertex,end="")forneighbouringraph[vertex]:ifneighbournotinvisited:visited.add(neighbour)queue.append(neighbour)#图的邻接表表示graph={'A':['B','C'],'B':['D','E'],'C':['F'],'D':[],'E':['F'],'F':[]}bfs(graph,'A')#输出:ABCDEF1234567891011121314151617181920212223242526'运行运行在上面的例子中，我们使用deque作为队列来存储待访问的节点，实现了图的广度优先搜索。这些示例展示了deque在不同场景下的应用，从基本的队列操作到更复杂的算法实现。deque的灵活性和高效性使得它成为处理序列数据的强大工具。