Python全面掌握CollectionsDeque：队列与栈的高效实现及动态内存管理指南

见贤思齐

文章目录第一章：`deque`的定义和特性1.什么是双端队列（deque）2.`deque`与普通列表（list）的性能差异第二章：构造函数1.如何创建一个`deque`2.可选参数`maxlen`的作用和使用场景第三章：添加和删除元素1.使用`append`方法在右端添加元素2.使用`appendleft`方法在左端添加元素3.使用`pop`方法从右端删除元素4.使用`popleft`方法从左端删除元素第四章：访问和旋转元素1.如何访问`deque`中的元素2.`deque`的索引和切片操作3.`deque`的`rotate`方法第五章：扩展`deque`1.使用`extend`方法在右端扩展多个元素2.使用`extendleft`方法在左端扩展多个元素第六章：限制和性能考虑1.`maxlen`属性的影响2.`deque`的内存效率和操作效率第七章：实际应用场景1.实现队列和栈2.实现滑动窗口代码实现维护`deque`的递减性质例子解析检查和移除逻辑3.广度优先搜索(BFS)第八章：注意事项和局限性1.`deque`的局限性2.何时不应使用`deque`本文章主要探讨Pythoncollections模块中的deque类，详尽介绍了其定义、特性、构造方法、操作技巧、实际应用场景以及其使用时的注意事项和局限性。第一章：deque的定义和特性1.什么是双端队列（deque）deque，全名为双端队列（Double-EndedQueue），是一个由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的构造函数来完成，这与创建列表类似。fromcollectionsimportdeque#创建一个空的dequed=deque()#使用列表初始化dequed=deque([1,2,3,4,5])#使用字符串初始化，每个字符作为一个元素d=deque("hello")123456789102.可选参数maxlen的作用和使用场景deque的构造函数还接受一个名为maxlen的可选参数。这个参数用于设置deque可以容纳的最大元素数量。当设定了maxlen并且在deque中添加元素使其达到最大容量时，每当添加一个新元素，另一端的元素会被自动移除。#创建一个最大长度为3的dequed=deque([1,2,3],maxlen=3)#当尝试添加更多元素时，最旧的元素将被自动移除d.append(4)#deque([2,3,4])d.appendleft(1)#deque([1,2,3])123456这个特性非常适合于需要限制容量的应用场景，如缓存机制或最近使用的项目（LRU）缓存。当只需要跟踪最新的几个项目时，使用maxlen可以自动维护deque的大小，避免手动删除老旧元素的复杂性。第三章：添加和删除元素deque提供了多种方法来动态地添加和删除元素，使其非常适用于需要频繁修改的数据结构应用场景。以下是deque的基本操作方法的详细介绍。1.使用append方法在右端添加元素append方法是用于在deque的右端添加新元素的基本方法。这种操作非常快速，因为它不涉及元素之间的移动，只涉及到对尾部的访问和修改。fromcollectionsimportdequed=deque([1,2,3])d.append(4)#在右端添加元素print(d)#输出:deque([1,2,3,4])12345这个方法通常用于实现栈（后进先出）或队列（先进先出）的操作。2.使用appendleft方法在左端添加元素与append相对应，appendleft方法允许用户在deque的左端添加新元素。这同样是一个时间复杂度为O(1)的操作，使得deque在需要从两端动态修改数据时表现出色。d.appendleft(0)#在左端添加元素print(d)#输出:deque([0,1,2,3,4])12appendleft非常适合于需要从前端推入数据的场景，例如在某些特定的数据流或缓冲区操作中。3.使用pop方法从右端删除元素pop方法用于从deque的右端移除并返回最后一个元素，这是实现栈结构的标准操作。由于deque的设计，这种操作同样具有很高的效率（O(1)）。last_item=d.pop()#移除并返回右端元素print(last_item)#输出:4print(d)#输出:deque([0,1,2,3])1234.使用popleft方法从左端删除元素popleft方法是deque中从左端移除并返回第一个元素的方法。这一操作对于实现队列结构至关重要，允许快速的从队列头部移除元素。first_item=d.popleft()#移除并返回左端元素print(first_item)#输出:0print(d)#输出:deque([1,2,3])123第四章：访问和旋转元素尽管deque主要设计用于高效地从两端添加和删除元素，它也支持通过索引访问单个元素。然而，相比列表，deque在中间元素的访问效率方面有一定的限制。1.如何访问deque中的元素deque支持通过索引访问元素，这类似于列表的索引方式。可以直接使用索引操作符访问任意位置的元素。fromcollectionsimportdequed=deque([0,1,2,3,4])#访问第一个元素print(d[0])#输出:0#访问最后一个元素print(d[-1])#输出:412345678尽管这种访问方式在语法上很直接，但需要注意的是，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进行切片fromitertoolsimportisliceslice_result=islice(d,0,3)print(list(slice_result))#输出:[0,1,2]12345678虽然操作有那么一些复杂，但它们提供了在需要时对deque进行灵活处理的方法。deque更多地被用于那些主要涉及到在两端添加或移除元素的情况，而不是频繁地随机访问中间元素。如果需要经常访问集合中间的元素，可能需要考虑是否有其他更适合的数据结构，如列表。当然，deque提供了足够的功能来高效地处理数据，尤其是涉及队列和栈操作。3.deque的rotate方法deque提供了一个非常有用的方法rotate，可以旋转队列中的元素。这个方法可以向右或向左旋转deque中的元素，使得部分元素从一端移到另一端，非常适合于需要循环移位操作的场景。rotate方法接受一个参数n。如果n是正数，deque将会向右旋转；如果n是负数，则向左旋转。旋转操作的效果是将deque尾部的元素移动到前面，或者将前面的元素移动到尾部。fromcollectionsimportdequed=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])1234567891011这种方法特别适合于需要周期性调整元素位置的应用，例如在某些算法中循环移位数组或处理缓冲流的数据。第五章：扩展dequedeque提供了灵活的方法来扩展现有的双端队列，允许从两端迅速添加多个元素。这些功能特别适合于在执行批量操作时维护队列的效率和顺序。1.使用extend方法在右端扩展多个元素extend方法允许将一个可迭代对象中的元素添加到deque的右端。这个方法可以一次性添加多个元素，是扩展deque的一种高效方式。使用extend方法可以保持元素的添加顺序，与单独使用多次append方法相比，extend在处理大量数据时更高效。fromcollectionsimportdequed=deque([1,2,3])#使用extend在右端添加多个元素d.extend([4,5,6])print(d)#输出:deque([1,2,3,4,5,6])123456这种方法在需要将多个数据源或批量数据快速合并到现有队列中时非常有用，例如在数据流处理或批量文件处理中。2.使用extendleft方法在左端扩展多个元素与extend类似，extendleft方法允许将一个可迭代对象中的元素从左端添加到deque中。不同之处在于，extendleft会逆序添加元素，因为它是从左端一次添加一个元素，所以首先添加的元素会被推到更远的位置。#使用extendleft在左端添加多个元素d.extendleft([0,-1,-2])print(d)#输出:deque([-2,-1,0,1,2,3,4,5,6])123extendleft方法的这种特性使得它在特定场景下非常有用，如需要反向保持元素添加的顺序时。然而，这也可能导致一些混淆，因为添加元素的顺序与extend是相反的。使用时需要特别注意这一点。第六章：限制和性能考虑当使用deque时，了解其性能限制和效率特点是至关重要的。这包括对maxlen属性的影响以及内存和操作效率的考量。1.maxlen属性的影响maxlen属性为deque设置了一个固定的长度限制。这意味着一旦deque达到了设定的最大长度，每当新元素被添加进来，最老的元素会自动被从另一端移除。这种机制有助于保持deque的大小不会无限增长，特别是在内存有限的环境中或者处理连续的数据流时。fromcollectionsimportdeque#创建一个最大长度为5的dequed=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)12345678910使用maxlen可以防止内存泄漏，确保deque不会因积累过多无关数据而影响性能。然而，这也意味着数据会丢失，因此在需要保留全部历史数据的应用中，使用maxlen需要谨慎。2.deque的内存效率和操作效率内存效率：deque通过使用双向链表实现，可以实现两端的快速添加和删除操作，而不需要为整个容器重新分配内存。这与列表相比，在进行大量的插入和删除操作时可以显著减少内存的使用和提高性能。操作效率：两端操作：deque在其两端进行添加或删除操作都具有O(1)的时间复杂度，这使得它在实现如队列和栈等数据结构时非常高效。随机访问：尽管deque支持索引访问，但其效率低于列表，因为链表需要从头开始遍历到指定位置，时间复杂度为O(n)。因此，如果依赖于频繁的随机访问，deque可能不是最优选择。扩展操作：extend和extendleft方法使得deque能够快速地从两端批量添加元素，这在处理大量数据时特别有用。第七章：实际应用场景deque由于其独特的性能特性和灵活的操作方式，在许多编程问题中都有广泛的应用。下面列举了一些典型的使用场景，展示了deque在实际中的有效应用。1.实现队列和栈由于deque支持从两端高效地添加和删除元素，它非常适合用于实现数据结构如队列（先进先出）和栈（后进先出）。队列：deque可以用作队列，其中元素从一端添加（通常是右端），从另一端（左端）移除。这模拟了队列的操作，适合于任务调度和消息处理等场景。fromcollectionsimportdequequeue=deque()queue.append('任务1')queue.append('任务2')queue.popleft()#'任务1'被处理12345栈：deque也可以用作栈，其中元素从同一端添加和删除，模拟了栈的后进先出的特性。stack=deque()stack.append('页面1')stack.append('页面2')stack.pop()#'页面2'被访问12342.实现滑动窗口滑动窗口是一种常见的数据结构，用于处理连续数据流中的问题，如计算移动平均或滑动最大/最小值。deque由于其两端操作的高效性，非常适合于实现滑动窗口的功能。代码实现fromcollectionsimportdequedefmaxSlidingWindow(nums,k):#结果列表max_elements=[]#双端队列，用于存储可能是当前窗口最大值的元素索引d=deque()fori,numinenumerate(nums):#移除所有小于当前元素的队尾元素的索引whiledandnums[d[-1]]=k-1:max_elements.append(nums[d[0]])returnmax_elements#示例nums=[1,3,-1,-3,5,3,6,7]k=3print(maxSlidingWindow(nums,k))#输出:[3,3,5,5,6,7]123456789101112131415161718192021222324252627282930时间复杂度：O(n)O(n)O(n)，其中n是数组长度。每个元素最多被添加和移除队列一次。维护deque的递减性质每当一个新元素（比如当前元素为num）需要加入到deque时，会执行以下操作：移除队尾小于当前元素的所有元素：检查deque的队尾元素，如果队尾元素对应的数组值小于当前元素num，则将这些元素从deque中移除。这是因为这些元素不可能再成为后续窗口的最大值了（当前元素更大，且更晚离开窗口）。这个过程会一直持续，直到deque为空或者队尾元素大于等于当前元素为止。这确保了当当前元素被加入deque后，deque依然维持从左到右的递减顺序。添加当前元素的索引到队尾：紧接着将当前元素的索引添加到deque的队尾。因为之前已经移除了所有小于它的元素，所以保持了deque的递减性质。例子解析以nums=[1,3,-1,-3,5,3,6,7]和k=3为例，考虑每一步的deque变化来理解：第一步：i=0,num=1deque=[0]，只有一个元素，无需比较。第二步：i=1,num=3deque=[0]中，索引0对应的值是1，小于3，所以移除。deque=[1]，现在deque只包含当前最大值3的索引。第三步：i=2,num=-1deque=[1]中，索引1对应的值是3，大于-1，所以不移除。deque=[1,2]，虽然-1不是最大值，但保留其索引以保持窗口大小。第四步：i=3,num=-3类似地，deque=[1,2]，3和-1都大于-3，所以deque更新为[1,2,3]。检查和移除逻辑检查条件：ifd[0]==i-k这行代码检查deque的队首元素的索引是否等于i-k。这里，i-k是当前索引i减去窗口大小k，得到的是当前窗口的前一个位置。如果deque的队首元素索引等于这个值，这意味着队首元素是窗口移动前的一个元素，现在已经不在当前窗口范围内了（已经超出了窗口的左边界）。移除操作：如果上述条件成立，使用d.popleft()从deque的左端移除该过期的元素索引。这确保了deque始终只包含当前窗口范围内的元素索引，且队首是当前窗口的最大值的索引。3.广度优先搜索(BFS)在图或树的遍历中，广度优先搜索通常使用队列来维护当前层的节点。deque由于其从两端高效地添加和删除操作，非常适合用作这类算法的数据结构基础。fromcollectionsimportdequedefbfs(graph,start):#初始化一个集合来存储已访问过的节点，防止重复访问visited=set()#初始化一个双端队列，开始时只包含起始节点queue=deque([start])#循环执行，直到队列为空whilequeue:#从队列的左端移除一个元素，这保证了按层次顺序访问vertex=queue.popleft()#如果这个节点未被访问过，则进行处理ifvertexnotinvisited:#将节点标记为已访问visited.add(vertex)#找出所有未访问的邻居节点并加入队列，保证这些节点将在未来被访问#graph[vertex]访问当前节点的邻居#-visited确保只添加还未访问的邻居queue.extend(graph[vertex]-visited)#返回所有从起始节点可达的节点集合returnvisited#示例图的遍历graph={1:{2,3},2:{4},3:{4},4:{5},5:{}}print(bfs(graph,1))#输出:{1,2,3,4,5}12345678910111213141516171819202122232425262728第八章：注意事项和局限性虽然deque在许多情况下表现出色，特别是在涉及到双端操作的场景中，但它并不总是最优的数据结构选择。了解deque的局限性和何时不应使用它是非常重要的。1.deque的局限性随机访问性能：尽管deque支持索引访问，但由于其底层是双向链表的实现，所以在随机访问时的性能不如数组或列表。每次访问都可能涉及从头节点或尾节点开始的遍历，尤其是访问中间元素时，性能会明显下降。不支持切片操作：deque不支持直接的切片操作，这在需要执行大量基于位置的操作时可能不太方便。虽然可以通过转换为列表来间接实现，但这种转换本身就会带来额外的性能开销。内存使用：与具有紧凑内存布局的数组相比，deque的每个元素都可能需要更多的内存开销，因为除了存储数据外，还需要额外的空间来维护前驱和后继的链接。2.何时不应使用deque需要频繁随机访问的场景：如果依赖于频繁的、快速的随机访问操作，使用列表或动态数组可能是更好的选择。例如，在需要经常访问或修改中间位置元素的大型数据集时，列表的性能通常会优于deque。大规模数据处理时的内存考量：虽然deque在添加和删除操作中非常高效，但如果要常大的数据集并且内存使用是一个关键考虑因素，更紧凑的数据结构（如数组）可能更合适。高度依赖切片操作的应用：在需要大量使用切片操作来处理数据的应用中，deque的不支持直接切片可能成为一个限制。在这种情况下，列表或其他支持切片的数据结构可能更为适宜。参考：FunwithdequesinPythonSlidingWindowMaximumUnderstandingPythondeque(Double-EndedQueue)