3.3  队列

3.3.1  队列的定义

前面所讲的栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出” (FIFO---First In First Out)的数据结构：即限定只能在表的一端进行插入，在表的另一端进行删除，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，允许删除的一端叫队头(front)。如图3.8所示是一个有5 个元素的队列。入队的顺序依次为a₁、 a₂ 、a₃ 、a₄  、 a₅ ，出队时的顺序将依然是a₁、 a₂ 、a₃ 、a₄  、 a₅ 。

显然，队列也是一种运算受限制的线性表，所以又叫先进先出表。在日常生活中队列的例子很多，如排队买票、食堂排队买饭或自动取款机排队取款，排在队头的人处理完后从队头走掉，而后来的人则必须排在队尾等待，为了不造成次序的混乱，采取的一种让先到的客户比晚到的客户先得到服务的办法。

抽象数据类型队列的定义如下：

ADT Queue { 

数据对象：

D＝{ a_i | a_i ∈ElemSet, i=1,2,...,n,  n≥0 }  {称 n 为队列的长度。} 

数据关系：

R1＝{ <a_i-1 ,a_i >|a_i-1 ,a_i∈D,  i=2,...,n } {约定其中a₁端为队列头，a_n端为队列尾。}

基本操作：

（1）队列初始化：Init_Queue(q)

初始条件：  队q不存在。

操作结果：　构造了一个空队。

（2）入队操作：　In_Queue(q,x),

初始条件：　队q存在。

操作结果：　对已存在的队列q，插入一个元素x到队尾，队发生变化。

（3）出队操作：　Out_Queue(q,x)

初始条件:   队q存在且非空

操作结果：　删除队首元素，并返回其值，队发生变化。

（4）读队头元素：Front_Queue(q,x)

初始条件:   队q存在且非空

操作结果：　读队头元素，并返回其值，队不变；

（5）判队空操作：Empty_Queue(q)

初始条件：　队q存在

操作结果：　若q为空队则返回为1，否则返回为0。

……

} ADT Queue

3.3.2  链队列的存储结构和操作的实现

队列的链式存储结构称为链队列。和链栈类似，用单链表来实现链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。

3.3.3  顺序队列的存储结构和操作的实现

虽然链队列很方便，但由于每个结点都有指针域，因此比顺序存储多占用内存空间。所以在有些情况下仍需要用顺序存储结构来表示队列。

队列的顺序存储结构称为顺序队列。可以用一组地址连续的存储单元依次存放队头到队尾的元素，因为队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针，它们的初始值在队列初始化时均应置为０。入队时将新元素插入所指的位置，然后将rear加１。出队时，删去所指的元素，然后将front加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。

3.4  队列的应用

队列是一种应用广泛的数据结构，凡是具有“先进先出”需要排队处理的问题，都可以使用队列来解决。

（1）CPU资源的竞争问题。

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

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

在计算机进行数据输入、输出处理时，由于外部设备的速度远远低于CPU数据处理的速度，此时可以设定一个“队列缓冲区”进行缓冲。当计算机要输出数据时，将计算机的数据按块逐个添加到“队列缓冲区”的尾端，而外部设备则按照其输出速度从队首逐个取出数据块输出。这样，虽然输出数据速度较慢，但却能保证与计算机输出的数据有完全相同的次序，而不至于发生输出次序的混乱或数据的丢失。

（3）舞伴问题。

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。

在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。

（4）队列还可以很好地异步处理数据传送和存储，当需要频繁地向数据库中插入数据或向搜索引擎提交数据时，就可采取队列来异步插入。另外，还可以将较慢的处理逻辑、有并发数量限制的处理逻辑，通过消息队列放在后台处理，例如FLV视频转换、发送手机短信、发送电子邮件等。