一、队列

队列（Queue）是一个数据集合，仅允许在列表的一端插入，在另一端删除。进行插入的一端称为“队尾”（rear），插入的动作称为入队；进行删除的一端称为“队头”（front），删除的动作称为出队。队列的性质是先进先出（FIFO，First-in-First-out）。下图为一个例子：

图1：队列

队列的实现方式：环形队列

设队列的最大长度为maxsize，队头指针为front，队尾指针为rear。上图中，队列最大长度为5，初始空队列front和rear都指向0。

• 当front == rear时，队为空，如图（a）
• 当(rear + 1) % maxsize == 0，队满。对于图（d1）的情况front == rear，无法判断到底是队空还是队满，因此需要牺牲一个存储单元，如图（d2）。
• 出队时队头指针前进1，front = (front + 1) % maxsize。
• 入队时队尾指针前进1，tear = (tear + 1) % maxsize。

上面的式子中，都有对maxsize的取余，因为比如当指针达到最大值5时，再加1就会超过5，此时取余可以重新进入队列循环。

二、广度优先搜索

广度优先搜索（BFS，Breadth First Search）的一个常见应用是找出从根结点到目标结点的最短路径，其实现用到了队列。下面用一个例子来说明BFS的原理，在下图中，我们BFS 来找出根结点 A 和目标结点 G 之间的最短路径。

图3：BFS例子

• 首先初始化一个队列Q，将根节点入队：A
• A出队，将与A相邻的节点入队，此时队列为BCD
• B出队，将与B相邻的节点入队，此时队列为CDE
• C出队，将与C相邻的节点入队，此时队列为DEF（节点E已经被遍历过，不需要再入队）
• D出队，将与D相邻的节点入队，此时队列为EFG
• E出队，下面没有节点
• F出队，下面是G，已遍历过，为目标值，遍历结束