一、概述
Python deque（双端队列）是Python标准库collections模块中的一个数据容器，它是一种具有线性表的性质，并且可以在队列的两端进行添加和删除元素。与列表相比，deque除了支持队列和栈的操作，还提供了旋转、均摊复杂度为O（1）的appendleft和popleft方法。
有时候我们需要使用队列，找到最前面/最后面的项目，或者需要从中删除一些项目，那么deque就可以派上用场。deque是一个双端队列，可以在队列的头部或尾部快速插入和删除元素，具有高效地进行双端操作的特性。
二、deque基础使用
Deque实例可以从左端和右端添加或删除元素。更具体来说，在deque开头添加和删除元素是O（1）的操作，但将一个元素插入中间是比较慢的，因为它需要移动内部元素以为新元素腾出空间。以下是deque的基本操作。
from collections import deque
d = deque()
d.append('a') # 添加到队列右侧
d.appendleft('b') # 添加到队列左侧
d.extend(['c', 'd']) # 在队列右侧添加多个元素
d.extendleft(['e', 'f'])# 在队列左侧添加多个元素
print(d) # deque(['f', 'e', 'b', 'a', 'c', 'd'])
d.pop() # 从队列右侧删除元素
d.popleft() # 从队列左侧删除元素
print(d) # deque(['b', 'a', 'c'])
三、deque的高效性
deque作为一个双端队列，在队列两端同时添加和删除元素的时候具有高效性。例如，可以使用deque在一个大数组上模拟一个滑动窗口，下面我们通过一个例子来演示deque的高效性。
我们有一个长度为100,000的列表，要在其中找到长度为100的最大子序列。假设我们用列表进行求解的话，代码会是这样的：
a = [...] # 长度为100,000的列表
k = 100
largest_sum = float('-inf')
for i in range(len(a)-k):
current_sum = sum(a[i:i+k])
largest_sum = max(largest_sum, current_sum)
在上面的代码中，我们遍历了列表中的每个子序列，并在其中找到了最大子序列。但是由于要遍历很多子序列，时间复杂度为O（n * k）。
改用deque，我们可以将时间复杂度降至O（n），如下所示。
from collections import deque
a = [...] # 长度为100,000的列表
k = 100
d = deque()
largest_sum = float('-inf')
for i, item in enumerate(a):
# 弹出过期数据
if len(d) == k:
d.popleft()
# 加入新数据
d.append(item)
if len(d) == k:
current_sum = sum(d)
largest_sum = max(largest_sum, current_sum)
在上面的代码中，我们使用deque维护了一个长度为100的滑动窗口，时间复杂度为O（n），具有比上面使用列表更高的效率。
四、deque的其他用途
除了作为双端队列，deque还有其他的用途。比如，在操作系统中，deque被用来存储系统调用。在图形学和游戏中，deque被用来存储和管理动画帧。在Web框架中，deque被用来存储客户请求和消息日志。
五、总结
deque是Python标准库中的一个双端队列，具有线性表的性质，并且可以在队列的两端进行添加和删除元素。与列表相比，deque除了支持队列和栈的操作，还提供了旋转、均摊复杂度为O（1）的appendleft和popleft方法。deque可用于从队列中查找最前面/最后面的项目，或者需要从中删除一些项目，具有高效地进行双端操作的特性。该数据容器在操作系统、游戏等领域有广泛应用。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/182180.html
微信扫一扫 
支付宝扫一扫 