队列的应用

队列在层次遍历中的应用

在信息处理中有一大类问题需要逐层或逐行处理。

这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行。

使用队列就是为了保存下一步的处理顺序。

例如在层次遍历二叉树时，遍历过程如下：

1. 根节点入队
2. 若队空，则结束遍历，否则重复3
3. 队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回2

序号	说明	队内	队外
1	A入	A
2	A出，BC入	BC	A
3	B出，D入	CD	AB
4	C出，EF入	DEF	ABC
5	D出，G入	EFG	ABCD
6	E出，HI入	FGHI	ABCDE
7	F出	GHI	ABCDEF
8	GHI出		ABCDEFGHI

---

队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛，以下仅从两个方面来阐述：

主机与外部设备之间速度不匹配的问题

例如主机和打印机之间的速度不匹配，由于主机输出数据的速度远比打印机工作的速度快得多，所以不能直接把输出数据送到打印机。解决办法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后暂停输出，转去处理其他事务.

打印机从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。

这样既能保证打印数据的正确性，又能提高主机的效率（缓冲区满去做其他事）。打印数据缓冲区中所存储的数据就是一个队列。

由多用户引起的资源竞争问题

例如CPU资源的竞争，在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，他们分别通过各自的终端向操作系统提出占用CPU的请求。

操作系统通常按照每个请求在时间上的先后顺序，把他们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU分配给新的队首请求的用户使用。这样做既能满足每个用户的请求，又能使得CPU正常运行，不发生冲突。