数据结构-----队列应用

队列应用-----树的层次遍历：

如下图所示为一个树：

分为四层，我们在遍历的时候是根据层次进行遍历的
遍历的过程是，从左向右遍历，将新的元素放在队尾，访问对头元素，遍历完一个节点的左右节点之后，该节点出队。

具体过程如下：

对一号结点进行遍历：
遍历完1号结点之后，1号结点出队。

此时对头节点变成2号结点，因此将2号结点的左右节点插入队尾。

2号结点遍历完成后，出队。

此时对头节点变成3号结点，因此将3号结点的左右节点插入队尾。
遍历完3号结点之后，3号结点出队。

下面遍历4号结点，由于4号结点没有左右节点，因此直接出队，遍历下一个节点，重复进行上述操作，直至遍历完所有的节点。
队列的应用-----图的广度优先遍历。

队列应用------图的广度优先遍历：

如下图所示为一个图：

图的遍历方式和树有些相似，只是这里并不是依次访问左右节点，而是将和它相连的节点插入队尾。
具体过程如下：

访问一号结点：

与它相联着的有2号和3号结点。
然后1号结点出队。

和树一样接下来访问对头元素，2号结点。

然后2号结点出队。

然后访问3号结点，和3号结点相连的有1，5，6，但是由于1号结点已经访问过了，因此只需要将剩下的两个节点插入队尾。

依次类推，直至访问完所有的节点。

队列在操作系统中的应用：

多个进程争抢着使用有限的系统资源，FCFS（first come first service先来先服务）是一种常用策略。

举例：

CPU资源的分配：
在举一个生活中常见的例子：

打印数据缓冲区：

场景：去学校打印店打印论文，多个同学用同一台打印机打印，打印的先后顺序如何？

假设有一位同学，他需要打印论文，但是由于论文很长，需要一定时间去打印，因此在打印机为该同学工作的过程中，打印数据的缓冲区就会将其他同学要打印的内容组成一个“队列”。

因为打印机打印的速度远低于主机的速度，因为这样一来，也可缓解主机与打印机速度不匹配的问题。