python - Python Queue.Queue 和 deque 的一致性？

Question

鉴于此代码...

import Queue

def breadthFirstSearch(graph, start, end):
q = Queue.Queue()
path = [start]
q.put(path)
visited = set([start])
while not q.empty():
    path = q.get()
    last_node = path[-1]
    if last_node == end:
        return path
    for node in graph[last_node]:
        if node not in visited:
            visited.add(node)
            q.put(path + [node])

其中graph 是表示有向图的字典，例如{'stack':['overflow'], 'foo':['bar']} 即stack 指向overflow 而foo 指向bar。

为什么当我用集合中的 deque 替换 Queue.Queue 以提高效率时，我没有得到相同的结果？

from collections import deque

def breadthFirstSearch(graph, start, end):
q = deque()
path = [start]
q.append(path)
visited = set([start])
while q:
    path = q.pop()
    last_node = path[-1]
    if last_node == end:
        return path
    for node in graph[last_node]:
        if node not in visited:
            visited.add(node)
            q.append(path + [node])

Answer 1

您的Queue.Queue版本使用 FIFO，而您的deque版本使用 FILO。您应该改用它path = q.popleft()来解决此问题。

请注意，Queue.Queue内部使用底层证券deque来表示队列。有关详细信息，请参阅相关文档（请参阅_get方法）