Python 双向队列Deque
首先 python的队列有很多种。Python标准库中包含了四种队列，分别是queue.Queue / asyncio.Queue /multiprocessing.Queue / collections.deque。可见deque是标准库collections中的，这其中最好用的是deque ，以下是deque的基本操作：
它的操作很像list。同时 相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。list实现在出队（pop）和插入（insert）时的空间复杂度大约为O(n)，deque在出队（pop）和入队（append）时的时间复杂度是O(1)。所以deque更有优越性 而且deque既可以表示队列又可以表示栈。
deque支持in操作符
q = collections.deque([1, 2, 3, 4]) print(5 in q) # False print(1 in q) # True # 顺时针旋转 q = collections.deque([1, 2, 3, 4]) q.rotate(1) print(q) # [4, 1, 2, 3] q.rotate(1) print(q) # [3, 4, 1, 2] # 逆时针旋转 q = collections.deque([1, 2, 3, 4]) q.rotate(-1) print(q) # [2, 3, 4, 1] q.rotate(-1) print(q) # [3, 4, 1, 2] # 还可以复制一个新队列： >>> d.append(1) >>> d.append(2) >>> d deque([1, 2]) >>> d1 = d.copy() >>> d1 deque([1, 2])
1234567891011121314151617181920212223242526值得注意的是 deque里边的形式是列表形式。
>>> d.clear() >>> d.append(1) >>> d.extend([3,4,5]) >>> d deque([1, 3, 4, 5]) 能不能从左边extend呢： >>> d.clear() >>> d.append(1) >>> d.extendleft([3,4,5]) >>> d deque([5, 4, 3, 1]) >>> d.extend(["a","b","c","d","e","f"]) >>> d deque(['a', 'b', 'c', 'd', 'e','f']) >>> d.index("c",0,4) #指定查找的区间 2 >>> d.index("c",0,2) error...
123456789101112131415161718192021题目
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
既然时间复杂度是O（1）
我们用deque就好
代码：
from collections import deque class MaxQueue: def __init__(self): self.d = deque() def max_value(self) -> int: return max(self.d) if self.d else -1 def push_back(self, value: int) -> None: self.d.append(value) def pop_front(self) -> int: return self.d.popleft() if self.d else -1 1234567891011121314
创建双向队列Deque序列
双向队列Deque提供了类似list的操作方法:
1 2 3 4 5 6 7 8 9 10 11 12 #!/usr/bin/python3 import collections #创建队列 d = collections.deque() d.append("1") d.append("2") d.append("3") print(len(d)) print(d[0]) print(d[-1])
123456789101112131415161718192021222324执行结果：
1 2 3 3 1 3 123456
两端都使用pop:
1 2 3 4 5 6 7 8 9 #!/usr/bin/python3 import collections #创建队列 d = collections.deque("12345") print(len(d)) print(d.popleft()) print(d.pop()) print(d)
123456789101112131415161718执行结果：
1 2 3 4 5 1 5 deque(['2', '3', '4']) 12345678
我们还可以限制deque的长度:
1 d1 = collections.deque(maxlen=30) 12
当限制长度的deque增加超过限制数的项时, 另一边的项会自动删除:
1 2 3 4 5 6 7 8 9 10 11 #!/usr/bin/python3 import collections #创建队列 d = collections.deque(maxlen=2) d.append(1) d.append(2) print(d) d.append(3) print(d)
12345678910111213141516171819202122执行结果：
1 2 deque([1, 2], maxlen=2) deque([2, 3], maxlen=2) 1234
添加list中各项到deque中:
1 2 3 4 5 6 7 8 9 10 11 1234567891011
#!/usr/bin/python3 import collections #创建队列 d = collections.deque([1,2,3,4,5]) print(d) d.extendleft([0]) print(d) d.extend([6,7,8]) print(d) 1234567891011
执行结果：
1 2 3 deque([1, 2, 3, 4, 5]) deque([0, 1, 2, 3, 4, 5]) deque([0, 1, 2, 3, 4, 5, 6, 7, 8]) 123456
网址：Python 双向队列Deque https://www.yuejiaxmz.com/news/view/49107
相关内容
栈和队列python 列表转为字典的两个小方法
Python的生活小技巧
Python中的遇到的错误（持续更新）
python中的print()语句中的end=''是什么意思
python自动化办公1
Python中if
省时省力，这些Python高效代码片段必须牢记
Python实现经典还钱问题算法：优化财务管理的编程技巧
Python项目设计：个人财务管理系统实现与功能详解
