广度优先搜索与队列

在算法中，广度优先搜索算法（BFS）和队列（Queue）是一对好朋友，基本上用到BFS思路的地方都可以用队列来解决

在 Python 中，可以使用以下几种方法实现队列

①collections包里的deque，对应操作

• pop()从尾取出
• appendleft() 从头插入

②queue包中的Queue，对应操作

• put() 插入
• get() 取出

③直接使用list，只要保证只使用

• pop() 取出
• insert(0,) 插入
  或者只使用
• append() 插入
• list[0]并且del list[0] 取出
  两者使用list方法的不同就区别于你把哪个当头，哪个当尾
  三种方法各有优劣。

第一种是正统的Python的双端队列，缺点是调用的函数有点复杂，可能一不小心写了append，就不对了。
第二种使用封装的函数很直接，put()和get()不容易搞混淆。但是Queue类型其实里面本身就装了一个deque。
第三种优势在于不用调包，但是函数使用逻辑可能造成混淆。在这里，完整版代码采用第二种，好理解，精简版代码采用第三种，省行数。三种方式可以按照你的喜好互相替换，完全不影响结果。
补充一下，使用列表时，list.insert(0, )的时间复杂度是O(n)，跟deque是有区别的。deque的appendleft(val)的时间复杂度是O(1)。所以用deque更好。