2.6　队列结构

在程序设计中，队列结构也是一种常用的数据结构。队列结构和栈结构类似，其在现实生活中都有对应的例子，可以说队列结构是来源于生活的数据结构。

2.6.1　什么是队列结构

队列结构是从数据的运算来分类的，也就是说队列结构具有特殊的运算规则。而从数据的逻辑结构来看，队列结构其实就是一种线性结构。如果从数据的存储结构来进一步划分，队列结构包括两类。

・顺序队列结构：即使用一组地址连续的内存单元依次保存队列中的数据。在程序中，可以定义一个指定大小的结构数组作为队列。

・链式队列结构：即使用链表形式保存队列中各元素的值。

典型的队列结构，如图2-11所示。从图中可以看出，在队列结构中允许对两端进行操作，但是两端的操作不同。在表的一端只能进行删除操作，称为队头；在表的另一端只能进行插入操作，称为队尾。如果队列中没有数据元素，则称为空队列。

从数据的运算角度来分析，队列结构是按照“先进先出”（First In First Out，FIFO）的原则处理结点数据的。

其实，队列结构在日常生活中有很多生动的例子。例如，银行的电子排号系统，先来的人取的号靠前，后来的人取的号靠后。这样，先来的人将最先得到服务，后来的人将后得到服务，一切按照“先来先服务”的原则。

在硬件的存储类芯片中，有一类根据队列结构构造的芯片，即FIFO芯片。这类芯片具有一定的容量，保留了一端作为数据的存入，另一端作为数据的读出。先存入的数据将先被读出。

在队列结构中，数据运算非常简单。一般队列结构的基本操作只有两个。

・入队列：将一个元素添加到队尾（相当于到队列最后排队等候）。

・出队列：将队头的元素取出，同时删除该元素，使后一个元素成为队头。

除此之外，还需要有初始化队列、获取队列长度等简单的操作。下面分析如何在Java语言中建立顺序队列结构，并完成顺序队列结构的基本运算。

2.6.2　准备数据

学习了前面的理论知识后，下面就开始队列结构的程序设计。首先需要准备数据，即准备在队列操作中需要用到的变量及数据结构等。示例代码如下：

在上述代码中，定义了队列结构的最大长度QUEUELEN，队列结构数据元素的类DATA4及队列结构的类SQType。在类SQType中，data为数据元素，head为队头的序号，tail为队尾的序号。当head=0时表示队列为空，当tail=QUEUELEN时表示队列已满。

2.6.3　初始化队列结构

在使用顺序队列之前，首先要创建一个空的顺序队列，即初始化顺序队列。顺序队列的初始化操作步骤如下：

（1）按符号常量QUEUELEN指定的大小申请一片内存空间，用来保存队列中的数据。

（2）设置head=0和tail=0，表示一个空栈。

初始化顺序队列的代码示例如下：

在上述代码中，首先使用new关键字申请内存，申请成功后设置队头和队尾，然后返回申请内存的首地址。如果申请内存失败，将返回null。

2.6.4　判断空队列

判断空队列即判断一个队列结构是否为空。如果是空队列，则表示该队列结构中没有数据。此时可以进行入队列操作，但不可以进行出队列操作。

判断空队列的代码示例如下：

在上述代码中，输入参数q是一个指向操作的队列的引用。在程序中，根据队列head是否等于tail，判断队列是否为空。

2.6.5　判断满队列

判断满队列即判断一个队列结构是否为满。如果是满队列，则表示该队列结构中没有多余的空间来保存额外数据。此时不可以进行入队列操作，但是可以进行出队列操作。

判断满队列的代码示例如下：

在上述代码中，输入参数q是一个指向操作的队列的引用。程序中，判断队列tail是否已等于符号常量QUEUELEN，从而判断队列是否已满。

2.6.6　清空队列

清空队列即清除队列中的所有数据。清空队列的代码示例如下：

在上述代码中，输入参数q是一个指向操作的队列的引用。程序中，简单地将队列顶引用head和tail设置为0，表示执行清空队列操作。

2.6.7　释放空间

释放空间即释放队列结构所占用的内存单元。由前面知道，在初始化队列结构时，使用了new关键字分配内存空间。虽然可以使用清空队列操作，但是清空队列操作并没有释放内存空间，这就需要使用赋值null操作释放所分配的内存。

释放空间的代码示例如下：

在上述代码中，输入参数q是一个指向操作的队列的引用。在程序中，直接使用赋值null操作释放所分配的内存。一般在不需要使用队列结构的时候使用，特别是程序结束时。

2.6.8　入队列

入队列是队列结构的基本操作，主要操作是将数据元素保存到队列结构。入队列操作的具体步骤如下：

（1）首先判断队列顶tail，如果tail等于QUEUELEN，则表示溢出，进行出错处理；否则执行以下操作。

（2）设置tail=tail+1（队列顶引用加1，指向入队列地址）。

（3）将入队列元素保存到tail指向的位置。

入队列操作的代码示例如下：

在上述代码中，输入参数q是一个指向操作的队列的引用，输入参数data是需要入队列的数据元素。程序中首先判断队列是否溢出，如果溢出则不进行入队列操作，否则修改队列顶引用的值，再将元素入队列。

2.6.9　出队列

出队列是队列结构的基本操作，主要操作与入队列相反，其操作是从队列顶弹出一个数据元素。出队列操作的具体步骤如下：

（1）判断队列head，如果head等于tail，则表示为空队列，进行出错处理；否则，执行下面的步骤。

（2）从队列首部取出队头元素（实际是返回队头元素的引用）。

（3）设修改队头head的序号，使其指向后一个元素。

在上述代码中，输入参数q是一个指向操作的队列的引用。该方法返回值是一个DATA类型的数据，返回值是指向该数据元素的引用。

2.6.10　读结点数据

读结点数据即读取队列结构中结点的数据，这里的读操作其实就是读取队列头的数据。需要注意的是，读结点数据的操作和出队列操作不同。读结点数据的操作仅显示队列顶结点数据的内容，而出队列操作则将队列顶数据弹出，该数据不再存在了。

读结点数据的代码示例如下：

在上述代码中，输入参数q是一个指向操作的队列的引用。该方法的返回值同样是一个DATA4类型的引用数据，返回值是指向数据元素的引用。

2.6.11　计算队列长度

计算队列长度即统计该队列中数据结点的个数。计算队列长度的方法比较简单，用队尾序号减去队头序号即可。

计算队列长度的代码示例如下：

在上述代码中，输入参数q是一个指向操作的队列的引用。该方法的返回值便是队列的长度。

2.6.12　队列结构操作实例

学习了前面的队列结构的基本运算之后，便可以轻松地完成对队列结构的各种操作。下面给出一个完整的例子，来演示队列结构的创建、入队列和出队列等操作。代码示例如下：

【程序2-4】

在上述代码中，main（）主方法首先初始化队列结构，然后循环进行入队列操作，添加数据结点，当输入全部为0时则退出结点添加的进程。接下来，用户每按一次按键，则进行一次出队列操作，显示结点数据。当为空队列时，退出程序。然后该程序执行结果，如图2-12所示。