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

1
dl = deque()   

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
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个)

1
2
3
4
5
6
7
8
9
10
11
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个列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

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

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

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