Loading... ## collections.deque `deque`类实现了一个双端队列,支持在$O(1)$时间复杂度从任一端添加和删除元素。<br/>由于`deque`支持从两端添加和移除元素,因此既可用作**队列**也可用作**栈**。 Python的`deque`对象以双向链表实现, 这为元素的插入/删除提供了出色且一致的性能,但是随机访问位于栈中间元素的性能很差,时间复杂度$O(n)$。 因此,默认情况下`collections.deque`是Python标准库中不错的队列型数据结构 --- ## 用法: 作为queue 队列在算法中有广泛的应用,经常用于解决调度和并行编程问题。在树或图数据结构上进行宽度优先搜索(BFS)是一种简短而美丽的算法,其中就用到了队列。 ### 双端队列 可以在左后/前后两侧添加删除元素, 常用方法如下 * 左侧添加与删除元素 * popleft() * appendleft(elem) * 右侧添加与删除元素(同常规, list兼容) * pop() * append(elem) 示例代码 ```python # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None: return [] # 基于 collections.deque 双端队列 from collections import deque # q = deque() q = [] # 从后出, 此时可以使用list代替deque q.append(root) results = [] while q: # 从前出 # elem = q.popleft() # results += [elem.val] # # 注意顺序以及从队列左侧加入 # if elem.right is not None: # q.appendleft(elem.right) # if elem.left is not None: # q.appendleft(elem.left) # 从后出, 此时可以使用list代替deque elem = q.pop() results += [elem.val] # 注意顺序以及从队列左侧加入 if elem.right is not None: q.append(elem.right) if elem.left is not None: q.append(elem.left) return results ``` ### 优先级队列 待补充 --- ### FIFO队列 `collections.deque`是Python中实现FIFO队列数据结构的最佳选择。`collections.deque`是非常优秀的队列实现,具备期望的性能特征,并且可以用作栈(LIFO队列)。 <span style='color:red'>这里不建议使用list, 性能开销太大.</span> 常用方法: * 右侧加入, 左侧弹出 * append(elem), popleft() 示例代码 ```python from collections import deque = collections.deque() queue.append('a') queue.append('b') queue.append('c') print(queue) queue.appendleft('A') queue.appendleft('B') print(queue) ``` --- ## 用法: 作为stack stack作为后入先出的数据结构类型(LIFO队列), 可以使用`list`或`collections.deque`, 选择从右侧进出2者可以无缝替换 ```python # leetcode链接: https://leetcode.cn/problems/binary-tree-preorder-traversal/ # 二叉树的前序遍历, 非递归解法, 借助stack先入后出 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None: return [] # 模拟stack先入后出 from collections import deque # q = deque() # 或 q = [] # 从后出, 此时可以使用list代替deque q.append(root) results = [] while q: # 从后出, 此时可以使用list代替deque elem = q.pop() results += [elem.val] # 注意顺序以及从队列右侧加入 if elem.right is not None: q.append(elem.right) if elem.left is not None: q.append(elem.left) return results ``` THE END 本文作者:将夜 本文链接:https://zoe.red/2024/350.html 版权声明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。 最后修改:2024 年 02 月 29 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏