队列及特点和应用详解

与栈一样，队列（Queue）也是一种数据结构，它包含一系列元素。但是，队列访问元素的顺序不是后进先出（LIFO)，而是先进先出（FIFO）。队列中元素的处理就像是站在商店收款台前排队等待的顾客：排在最前面的顾客最先结账。

队列数据结构常用于计算机操作系统。它们在多用户/多任务环境中尤为重要，在这种环境中，多个用户或任务可能同时请求同一资源。例如，打印由队列控制，因为一次只能打印一个文档。队列用于保存由系统用户提交的打印作业，而打印机则一次处理一个作业。

通信软件也会使用队列来保存通过网络和拨号连接方式接收到的信息。有时，信息传输到系统的速度比它能处理的要快，因此在收到信息时会先将其放入队列中。

顺序队列和链队列

队列与栈一样，也可以实现为数组或链表。前面介绍过，顺序栈与链栈相比有两项优势，而这样的优势在顺序队列与链队列的对比中也同样存在。实际上，队列与栈之间的主要区别在于每个结构中数据元素的访问方式。

队列操作

队列和商店收款台的排队线一样，也分前面（以 front 表示）和后面（以 rear 表示），如图 1 所示。

图 1 队列示意图

当一个元素被添加到队列中时，它被添加到后面。当一个元素从队列中移除时，它将从前面移除。队列的两个主要操作就是入队（enqueue）和出队（dequeue）。入队意味着在队列的后面插入一个元素，而出队则意味着从队列的前面移除一个元素。有若干个算法可以实现这些操作，现在就从最简单的开始介绍。

假设有一个空的静态整数队列，最多能够保存 3 个值。可以使用该队列执行入队操作，示例如下：

图 2 显示了执行以上入队操作之后的队列状态。

图 2 执行入队操作之后的队列状态

请注意前面的索引（它是一个持有下标或者指针的变量）总是引用相同的物理元素。而后面的索引则会随着项目入队而在数组中移动。现在来看一看出队操作的执行方式。图 3 显示了连续 3 次出队操作之后的队列状态。

图 3 出队操作的执行方式

在出队操作中，队列前面的元素被删除。这是通过将所有元素向前移动一个位置来完成的。在第一次出队操作之后，值 3 从队列中移除，值 6 在前面。在第二次出队操作之后，值 6 被移除，值 9 在前面。请注意，当只有一个值存储在队列中时，该值是 front 和 rear 共同指向的值。

如图 3 所示，在执行最后的出队操作之后，队列变成了空的。通过将表示前面的 front 和表示后面的 rear 两个索引都设置为 -1，可以表示一个空队列。

这个算法的问题是效率低下。每当一个项目出队时，队列中剩余的项目都被复制到其相邻元素。队列中的项目越多，则每次后续的出队操作所花费的时间就越长。

以下是解决该问题的一种方法：使 front 和 rear 的索引都可以在数组中移动。与以前一样，当一个项目入队时，后面的索引被移动以给它生成空间。但是在这个设计中，当一个项目出列时，前面的索引向着队列后面移动一个元素，这可以从逻辑上将前面的项目从队列中移除，并且意味着不需要将剩余项目复制到其相邻的元素。

但是，使用这种方法之后，随着项目的添加和删除，队列会逐渐"爬"向数组的末尾，如图 4 所示。

图 4 解决队列低效间题的一种设计方案

这种方法的问题是后面的索引不能超出数组中的最后一个元素。解决的办法是将数组视为循环而不是线性的。当一个项目移动到一个循环数组的末尾时，它只是简单地回到了开头。例如，来看一下如图 5 所示的队列。

图 5 循环队列

值3位于队列的后面，值 7 位于队列的前面。现在，假设要执行入队操作，将值 4 插入到队列中。图 6 显示了队列以 rear 表示的尾部如何绕到了数组的开头。

图 6 队列的尾部绕到了数组的开头

那么，该如何将 rear 标记绕到数组的开头呢？ 一个简单的方法就是使用 if 语句，示例如下：

if (rear == queueSize - 1)
    rear = 0;
else
    rear++;

另外还有一种方法就是使用求余算术：

该语句使用 ％ 运算符将 rear 中的值调整到适当的位置。虽然这种方法看起来更优雅，但这两种方法都可以任意选择使用。