Deque双端队列-Python成为专业人士笔记

基本用法

对这个类特别典型的用法是popleft和appendleft：

from collections import dequed = deque([1, 2, 3])p = d.popleft()print(p) # p = 1 获取队列弹出的值print(d) #d = deque([2, 3]) popleft删除了第一值d.appendleft(5)print(d) # d = deque([5, 2, 3]) ,列首增加了值：5

deque队列可用方法

创建空的双端队列：

dl = deque()

创建带元素的双端队列：

dl = deque([1, 2, 3, 4])

向队列中添加元素（默认右侧添加)：

dl.append(5) # deque([1, 2, 3, 4, 5])

左侧添加元素：

dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])

向队列添加列表元素：

dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])

在左侧添加列表元素：

dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7]) ，注意添加的顺序

使用.pop()会默认在队列右侧删除一个元素：

dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])

使用.popleft()左侧删除元素：

dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6]) 注意会返回被删除的元素

根据值删除元素：

dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])

反转队列：

dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])

其中，函数extend和append的区别：

append: 添加一个对象，可以是数值、字符串、列表、元组等

extend: 只能添加一个列表，意即扩展列表

deque队列长度

在创建deque时使用maxlen参数来限制deque的大小：

from collections import deque d = deque(maxlen=3) # 限制只能增加3个元素 d.append(1) # deque([1]) d.append(2) # deque([1, 2]) d.append(3) # deque([1, 2, 3]) d.append(4) # deque([2, 3, 4]) (1 被删除因为最大元素为3个)

注意，一个列表对象在队列中算一个，如下：

from collections import deque d = deque(maxlen=3) # 限制只能增加3个元素 d.append([1,2,3,4]) d.append([1,2,3,4]) d.append([1,2,3,4]) d.append([1,2,3,4]) print(d) # deque([[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]], maxlen=3) 可以放入3个列表

广度优先搜索

Deque是唯一具有快速队列操作特性的Python数据结构，其一个基本用例是广度优先搜索：

from collections import deque def bfs(graph, root): distances = {} distances[root] = 0 q = deque([root]) while q: # 最早看到(但尚未访问)的节点将是最左边的节点 current = q.popleft() for neighbor in graph[current]: if neighbor not in distances: distances[neighbor] = distances[current] + 1 # 当我们看到一个新节点时，我们将其添加到队列的右侧 q.append(neighbor) return distances

假设我们现在有一个简单的有向图：

graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}

我们现在可以求出从某个起始位置开始的距离：

bfs(graph, 1) #输出：{1: 0, 2: 1, 3: 1} bfs(graph, 3) #输出：{3: 0, 4: 1, 5: 1}

以上内容来自创帆云整理<Python成为专业人士笔记>