【Python 双端队列 deque 使用】

文章目录Python 双端队列 deque 使用 什么是双端队列 基本用法和初始化常用操作和方法添加元素删除元素访问和查询性能优势与比较实际应用场景队列和栈的实现滑动窗口问题回文检查进阶技巧和注意事项线程安全与列表的互操作最大长度的使用技巧总结Python 双端队列 deque 使用 在编程中处理数据集合时我们经常需要在两端高效地添加或删除元素。Python 的collections模块提供了一个强大的工具——deque双端队列它支持在队列的两端进行快速、线程安全的操作。本文将深入探讨deque的使用包括其特性、方法、应用场景以及性能优势。通过代码示例和图表您将学会如何在实际项目中灵活运用deque。什么是双端队列 双端队列deque发音为 “deck”是一种线性数据结构允许在两端进行插入和删除操作。与普通列表list相比deque在头部和尾部的操作具有更高的效率时间复杂度为 O(1)而列表在头部插入或删除元素的时间复杂度为 O(n)。这使得deque在处理队列、栈或需要频繁两端操作的场景中非常有用。Python 的deque是通过双向链表实现的这为其高效的两端操作提供了基础。它还具有线程安全的特性适用于多线程环境。基本用法和初始化要使用deque首先需要从collections模块导入它fromcollectionsimportdeque您可以创建一个空的deque或者使用可迭代对象如列表、元组等进行初始化# 创建一个空 dequeddeque()print(fEmpty deque:{d})# 输出: deque([])# 使用列表初始化 dequeddeque([1,2,3,4])print(fDeque from list:{d})# 输出: deque([1, 2, 3, 4])# 使用元组初始化ddeque((5,6,7))print(fDeque from tuple:{d})# 输出: deque([5, 6, 7])deque还支持可选参数maxlen用于指定队列的最大长度。当队列已满时添加新元素会自动从另一端丢弃旧元素# 创建最大长度为 3 的 dequeddeque([1,2,3],maxlen3)print(fDeque with maxlen3:{d})# 输出: deque([1, 2, 3], maxlen3)# 添加新元素头部元素被丢弃d.append(4)print(fAfter appending 4:{d})# 输出: deque([2, 3, 4], maxlen3)常用操作和方法deque提供了一系列方法用于在两端添加、删除和访问元素。以下是一些常用操作添加元素append(x): 在右端添加元素 x。appendleft(x): 在左端添加元素 x。extend(iterable): 在右端扩展可迭代对象中的元素。extendleft(iterable): 在左端扩展可迭代对象中的元素注意顺序会反转。ddeque([1,2,3])# 在右端添加元素d.append(4)print(fAfter append(4):{d})# 输出: deque([1, 2, 3, 4])# 在左端添加元素d.appendleft(0)print(fAfter appendleft(0):{d})# 输出: deque([0, 1, 2, 3, 4])# 在右端扩展多个元素d.extend([5,6])print(fAfter extend([5, 6]):{d})# 输出: deque([0, 1, 2, 3, 4, 5, 6])# 在左端扩展多个元素顺序反转d.extendleft([-2,-1])print(fAfter extendleft([-2, -1]):{d})# 输出: deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])删除元素pop(): 移除并返回右端元素。popleft(): 移除并返回左端元素。remove(value): 移除第一个匹配的 value从左到右扫描。ddeque([1,2,3,4,5])# 移除右端元素rightd.pop()print(fPopped from right:{right}, deque:{d})# 输出: Popped from right: 5, deque: deque([1, 2, 3, 4])# 移除左端元素leftd.popleft()print(fPopped from left:{left}, deque:{d})# 输出: Popped from left: 1, deque: deque([2, 3, 4])# 移除特定值d.remove(3)print(fAfter remove(3):{d})# 输出: deque([2, 4])访问和查询支持索引访问但注意性能中间元素访问为 O(n)两端为 O(1)。index(x[, start[, stop]]): 返回 x 的索引可指定范围。count(x): 返回 x 的出现次数。ddeque([10,20,30,40,50])# 索引访问print(fElement at index 2:{d[2]})# 输出: 30# 查找索引idxd.index(30)print(fIndex of 30:{idx})# 输出: 2# 计数d.append(20)countd.count(20)print(fCount of 20:{count})# 输出: 2性能优势与比较与 Python 列表相比deque在两端操作上具有显著性能优势。以下是一个简单的性能对比图表展示在不同操作上的时间复杂度渲染错误:Mermaid 渲染失败: Parse error on line 4: ... B -- D[两端添加/删除: O(1)] B -- E[中间访 -----------------------^ Expecting SQE, DOUBLECIRCLEEND, PE, -), STADIUMEND, SUBROUTINEEND, PIPE, CYLINDEREND, DIAMOND_STOP, TAGEND, TRAPEND, INVTRAPEND, UNICODE_TEXT, TEXT, TAGSTART, got PS从上图可以看出如果您需要频繁在序列两端进行操作deque是更优的选择。例如在实现队列或广度优先搜索BFS时deque的popleft()效率远高于列表的pop(0)。以下是一个简单的性能测试代码对比deque和列表在头部删除操作上的效率importtimefromcollectionsimportdeque# 测试 deque 的 popleftddeque(range(1000000))starttime.time()whiled:d.popleft()deque_timetime.time()-start# 测试列表的 pop(0)llist(range(1000000))starttime.time()whilel:l.pop(0)list_timetime.time()-startprint(fDeque popleft time:{deque_time:.4f}seconds)print(fList pop(0) time:{list_time:.4f}seconds)运行上述代码您会发现deque的速度远快于列表例如在普通计算机上deque可能只需零点几秒而列表可能需要数秒或更久。实际应用场景deque在许多实际场景中非常有用。以下是一些常见应用队列和栈的实现由于deque支持高效的两端操作它可以轻松实现队列FIFO和栈LIFO# 作为队列使用先进先出queuedeque()queue.append(task1)# 入队queue.append(task2)taskqueue.popleft()# 出队print(fProcessed:{task})# 输出: Processed: task1# 作为栈使用后进先出stackdeque()stack.append(item1)# 压栈stack.append(item2)itemstack.pop()# 弹栈print(fPopped:{item})# 输出: Popped: item2滑动窗口问题在数据处理和算法中滑动窗口是常见模式deque可以高效维护窗口内的元素defsliding_window_max(nums,k):# 使用 deque 存储索引维护当前窗口内的最大值dqdeque()result[]fori,numinenumerate(nums):# 移除不在窗口内的索引whiledqanddq[0]i-k1:dq.popleft()# 移除所有小于当前元素的索引保持递减顺序whiledqandnums[dq[-1]]num:dq.pop()dq.append(i)ifik-1:result.append(nums[dq[0]])returnresult# 示例nums[1,3,-1,-3,5,3,6,7]k3print(fSliding window max:{sliding_window_max(nums,k)})# 输出: [3, 3, 5, 5, 6, 7]回文检查deque可以方便地检查字符串是否为回文正反读都一样defis_palindrome(s):dqdeque(s.lower().replace( ,))# 忽略大小写和空格whilelen(dq)1:ifdq.popleft()!dq.pop():returnFalsereturnTrue# 测试print(is_palindrome(radar))# Trueprint(is_palindrome(Python))# False进阶技巧和注意事项线程安全deque是线程安全的这意味着可以在多线程环境中安全地进行两端操作而不需要额外的锁机制。但请注意其他操作如索引访问可能仍需同步。与列表的互操作deque可以与列表相互转换但要注意性能ddeque([1,2,3])lstlist(d)# deque 转列表d2deque(lst)# 列表转 deque最大长度的使用技巧当设置maxlen时deque会自动丢弃旧元素这在实现固定大小缓存或最近使用记录时非常有用# 实现一个简单的 LRU最近最少使用缓存classLRUCache:def__init__(self,capacity):self.cache{}self.orderdeque(maxlencapacity)defget(self,key):ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key,value):ifkeyinself.cache:self.order.remove(key)self.cache[key]value self.order.append(key)# 如果超过容量删除最旧的iflen(self.order)self.order.maxlenandkeynotinself.cache:oldself.order.popleft()delself.cache[old]# 使用示例cacheLRUCache(2)cache.put(1,a)cache.put(2,b)print(cache.get(1))# 输出: acache.put(3,c)# 键 2 被移除print(cache.get(2))# 输出: -1未找到总结Python 的deque是一个强大而灵活的双端队列实现适用于需要高效两端操作的场景。通过本文您学会了如何初始化、操作和利用deque解决实际问题。无论是实现数据结构、处理滑动窗口还是优化性能deque都是一个值得掌握的工具。如果您想深入了解 Python 标准库中的其他数据结构可以查阅 Python 官方文档 或参考一些优秀的编程资源如 Real Python。继续探索和实践您将更加熟练地运用deque提升代码效率 希望这篇博客对您有所帮助如有问题或建议欢迎讨论。 Happy coding!