XIAOSUO 记录个人学习的足迹

一、CPU资源的竞争问题

　　在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。

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

　　以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。

三、舞伴问题

　　假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
　　分析：先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。代码如下：

四、用队列排序数据

　　队列也可以用来对数据进行排序。回顾计算的早期时代，那时的程序都是通过穿孔卡片录入到大型计算机内，其中每张卡片上存有单独一条程序语句。卡片用机械排序器进行排序，这种排序器采用类似箱子的结构。而我们可以用队列排序数据的方式来模拟此过程，这种排序技术被称为基数排序。基数排序在编程的指令系统中不是最快的排序方法。但是它却能说明队列的一种有趣的应用。

　　具体的过程与实现我会在讲排序的时候再详细介绍，现在只要知道基数排序是通过队列来实现的就行了。

五、优先队列

　　大家现在已经知道，队列是一种先进先出的数据结构。这种行为的效果就是会最先移除结构内最早进入的数据项。然而，很多应用程序需要一种可以把具有最高优先级的数据项最先移除的数据结构，即使这个数据项在结构中不是“最早进入的”。对于这类应用程序Queue有一种特殊的案例，那就是优先队列。