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

帆云量化

基本用法

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

from collections import deque
d = 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)