Python 的队列实现

队列是计算机科学中一个常见的数据结构，特别在算法、网络等领域有着广泛的利用。Python 语言中一样提供了队列的实现。

import queue
# 创建一个先进先出（FIFO）队列
q = queue.Queue()
# 向队列中添加元素
q.put(1)
q.put(2)
q.put(3)
# 从队列中取出元素
print(q.get())  # 输出 1
print(q.get())  # 输出 2

在 Python 中，常见的队列实现有三种：Queue、LifoQueue 和 PriorityQueue。其中 Queue 为先进先出（FIFO）队列，LifoQueue 为落后先出（LIFO）队列，PriorityQueue 则根据优先级决定元素的顺序。

# 创建一个落后先出（LIFO）队列
lifo = queue.LifoQueue()
# 向队列中添加元素
lifo.put(1)
lifo.put(2)
lifo.put(3)
# 从队列中取出元素
print(lifo.get())  # 输出 3
print(lifo.get())  # 输出 2

除使用队列来实现通讯和数据交换等操作，队列在算法中也有侧重要的利用。例如使用队列来实现广度优先搜索（BFS），在建立树和图的层级结构时十分便捷。

def bfs(graph, start):
visited, queue = set(), [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.add(node)
queue.extend(graph[node] - visited)
return visited
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
print(bfs(graph, 'A'))  # 输出 {'A', 'C', 'B', 'E', 'D', 'F'}