python散装笔记——59: Queue队列模块 60: Deque 模块

大家好，欢迎来到IT知识分享网。

队列模块实现了多生产者、多消费者队列。当信息必须在多个线程之间安全交换时，它在线程编程中特别有用。

队列模块提供以下三种队列类型： 1. 队列 2. 生命队列 3. PriorityQueue

可能出现的异常： 1. 满（队列溢出） 2. 空（队列下溢）

1: 简单示例

from queue import Queue question_queue = Queue() for x in range(1,10): temp_dict = ('key', x) question_queue.put(temp_dict) while(not question_queue.empty()): item = question_queue.get() print(str(item))

输出结果：

('key', 1) ('key', 2) ('key', 3) ('key', 4) ('key', 5) ('key', 6) ('key', 7) ('key', 8) ('key', 9)

Deque 模块

1: deque 的基本使用

该类的主要实用方法是 popleft 和 appendleft

from collections import deque d = deque([1, 2, 3]) p = d.popleft() # p = 1, d = deque([2, 3]) d.appendleft(5) # d = deque([5, 2, 3])

2: deque 中的可用方法

创建空的 deque：

dl = deque() # deque([]) creating empty deque

创建包含一些元素的 deque

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

为 deque 添加元素

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

添加 deque 左边的元素：

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

向 deque 添加元素列表：

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])

颠倒 deque 中元素的顺序：

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

3: 限制 deque 的大小

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

from collections import deque d = deque(maxlen=3) # only holds 3 items 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)

4: 广度优先搜索

Deque 是唯一具有快速 队列操作 的 Python 数据结构。(注意 queue.Queue 通常并不合适，因为它是用于线程间通信的）。队列的一个基本用例是广度优先搜索。

from collections import deque def bfs(graph, root): distances = {} distances[root] = 0 q = deque([root]) while q: # The oldest seen (but not yet visited) node will be the left most one. current = q.popleft() for neighbor in graph[current]: if neighbor not in distances: distances[neighbor] = distances[current] + 1 # When we see a new node, we add it to the right side of the queue. 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, 4: 2, 5: 2} >>> bfs(graph, 3) {3: 0, 4: 1, 5: 1}