极客教程Python deque函数详解
1. 引言
在Python中，deque是一个非常有用的数据结构。它是一个双端队列，可以在队列的两端快速进行插入和删除操作。本文将详细介绍deque的使用方法和一些常见的应用场景。
2. deque的基本用法
deque是Python标准库collections模块中的一个类，使用之前需要先导入模块：
from collections import deque
2.1 创建deque对象
可以使用deque()函数来创建一个空的deque对象，也可以将一个可迭代对象转换为deque对象。下面是一些示例代码：
# 创建一个空的deque对象
d = deque()
print(d) # 输出: deque([])
# 将一个可迭代对象转换为deque对象
s = "hello"
d = deque(s)
print(d) # 输出: deque(['h', 'e', 'l', 'l', 'o'])
lst = [1, 2, 3]
d = deque(lst)
print(d) # 输出: deque([1, 2, 3])
从上面的代码可以看出，deque对象可以存储任意类型的元素。
2.2 deque对象的操作
deque对象支持一系列的操作，包括添加元素、删除元素、访问元素等。
2.2.1 添加元素
可以使用append()函数在deque的右侧添加元素，也可以使用appendleft()函数在deque的左侧添加元素。示例代码如下：
d = deque([1, 2, 3])
d.append(4)
print(d) # 输出: deque([1, 2, 3, 4])
d.appendleft(0)
print(d) # 输出: deque([0, 1, 2, 3, 4])
2.2.2 删除元素
可以使用pop()函数从deque的右侧删除元素，并返回删除的元素。类似地，可以使用popleft()函数从deque的左侧删除元素，并返回删除的元素。示例代码如下：
d = deque([0, 1, 2, 3, 4])
x = d.pop()
print(x) # 输出: 4
print(d) # 输出: deque([0, 1, 2, 3])
y = d.popleft()
print(y) # 输出: 0
print(d) # 输出: deque([1, 2, 3])
2.2.3 访问元素
可以使用索引或者切片来访问deque对象中的元素。示例代码如下：
d = deque([0, 1, 2, 3])
print(d[0]) # 输出: 0
print(d[-1]) # 输出: 3
print(d[1:3]) # 输出: deque([1, 2])
2.3 deque的其他常用函数和属性
除了上述的基本用法，deque还提供了一些常用的函数和属性，下面我们来逐个介绍。
2.3.1 extend()和extendleft()函数
extend()函数用于在deque的右侧添加多个元素，extendleft()函数用于在deque的左侧添加多个元素。示例代码如下：
d = deque([1, 2, 3])
d.extend([4, 5, 6])
print(d) # 输出: deque([1, 2, 3, 4, 5, 6])
d.extendleft([0, -1, -2])
print(d) # 输出: deque([-2, -1, 0, 1, 2, 3, 4, 5, 6])
2.3.2 rotate()函数
rotate()函数用于将deque对象中的元素向右循环移动n个位置，n可以是负数。示例代码如下：
d = deque([1, 2, 3, 4, 5, 6])
d.rotate(2)
print(d) # 输出: deque([5, 6, 1, 2, 3, 4])
d.rotate(-2)
print(d) # 输出: deque([1, 2, 3, 4, 5, 6])
2.3.3 count()函数
count()函数用于返回deque对象中指定元素的个数。示例代码如下：
d = deque([1, 2, 2, 3, 3, 3])
print(d.count(2)) # 输出: 2
2.3.4 remove()函数
remove()函数用于删除deque对象中第一次出现的指定元素。如果元素不存在，则会抛出ValueError。示例代码如下：
d = deque([1, 2, 3, 2, 3, 4])
d.remove(2)
print(d) # 输出: deque([1, 3, 2, 3, 4])
2.3.5 maxlen属性
maxlen属性用于获取或设置deque对象的最大长度。如果deque对象的长度超过了最大长度，那么在执行插入操作时将自动删除最左侧的元素。示例代码如下：
d = deque([1, 2, 3], maxlen=3)
print(d.maxlen) # 输出: 3
d.append(4)
print(d) # 输出: deque([2, 3, 4], maxlen=3)
3. deque的应用场景
deque在很多实际的问题中都有广泛的应用。下面我们介绍一些典型的场景。
3.1 滑动窗口
滑动窗口是一个常见的问题，可以使用deque来高效地解决。假设有一个长度为n的数组，要求计算出每个长度为k的连续子数组的最大值。可以使用一个大小为k的deque来保存当前窗口内的元素，通过维护一个单调递减的deque来实时更新最大值。示例代码如下：
from collections import deque
def max_sliding_window(nums, k):
result = []
window = deque()
for i, num in enumerate(nums):
if window and window[0] <= i - k:
window.popleft()
while window and nums[window[-1]] < num:
window.pop()
window.append(i)
if i >= k - 1:
result.append(nums[window[0]])
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k)) # 输出: [3, 3, 5, 5, 6, 7]
3.2 队列实现BFS
BFS（广度优先搜索）是一种常用的图搜索算法，在实现中需要使用队列来保存待处理的节点。可以使用deque来实现队列，实现更快速的BFS算法。示例代码如下：
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
visited.add(node)
# 处理当前节点
print(node)
# 将未访问的相邻节点加入队列
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
# 定义图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
运行结果：
A
B
C
D
E
F
3.3 队列实现任务调度
在某些情况下，需要按照一定的优先级对任务进行调度。可以使用deque来实现任务队列，通过调整任务的插入位置和删除顺序，实现不同的调度策略。示例代码如下：
from collections import deque
class Task(object):
def __init__(self, name, priority):
self.name = name
self.priority = priority
def __str__(self):
return self.name
def __repr__(self):
return self.name
def schedule_tasks(tasks):
queue = deque()
for task in tasks:
if not queue or task.priority <= queue[-1].priority:
queue.append(task)
else:
inserted = False
for i in range(len(queue)):
if task.priority > queue[i].priority:
queue.insert(i, task)
inserted = True
break
if not inserted:
queue.append(task)
return queue
tasks = [
Task("Task 1", 3),
Task("Task 2", 1),
Task("Task 3", 2),
Task("Task 4", 4),
Task("Task 5", 2)
]
task_queue = schedule_tasks(tasks)
print([str(task) for task in task_queue])
运行结果：
['Task 4', 'Task 1', 'Task 3', 'Task 5', 'Task 2']
4. 总结
本文详细介绍了Python中deque的基本用法和常用函数，以及deque在滑动窗口、BFS和任务调度等场景中的应用。deque是一个非常有用的数据结构，可以帮助我们更高效地解决各种问题。