队列ADT,实现与使用接口

周立功教授数年之心血之作《程序设计与数据结构》以及《面向AMetal框架与接口的编程（上）》，电子版已无偿性分享到电子工程师与高校群体，在公众号回复【编程】即可在线阅读。书本内容公开后，在电子行业掀起一片学习热潮。经周立功教授授权，本公众号特对《程序设计与数据结构》一书内容进行连载，愿共勉之。

第三章为算法与数据结构，本文为3.6 队列ADT。

>>>  3.6.1 建立抽象

队列可以简单的描述为：队列是一种特殊的容器，其限制插入位置在容器的尾部（队尾），删除位置在容器的头部（队头），是一种"先进先出"（First In-First Out，FIFO）的线性结构。比如，排队买票，人们从队尾加入队列，买完票后从队头离开（假定没有人插队），示意图详见图 3.28。

图 3.28 队列示意图

其抽象定义如下：

• 类型名：队列（Queue）

• 类型属性：存储一系列项

• 类型操作：从队尾添加项，从队头删除项，确定队列是否为空，确定队列是否已满，确定队列中的项数。

>>>3.6.2 建立接口

接口是通过头文件向用户提供的。首先创建一个头文件，命名为queue.h。在接口文件中，需要包含两部分内容：其一，抽象类型queueADT的定义；其二，声明各队列ADT的操作函数。

1、定义抽象类型queueADT

与栈类似，使用结构体类型来表示一个队列，在头文件中，只需要定义一个该结构体指针类型即可。结构体实际定义的细节、包含的具体成员无需在头文件中定义，交由具体实现完成对其的定义。定义抽象类型queueADT如下：

2、接口函数声明

• 创建队列

在使用队列前，必须正确的创建一个队列，因此需要提供一个用于创建新的queueADT的函数。其函数原型如下：

后置条件：返回队列。

其调用形式如下：

• 销毁队列

在创建队列时，具体实现会根据实际情况分配队列相关的存储空间，如队列对象本身的存储空间，队列项的存储空间等。因此，当一个队列不在使用时，应该释放掉队列相关的内存空间，以销毁一个队列，销毁后的队列不再存在，无法继续使用。其函数原型如下：

前置条件：queue为之前创建的队列；

后置条件：释放队列相关的所有内存，队列被销毁，不再有效。

其调用形式如下：

• 从队尾添加项（入队列）

用户通过该函数可以从队列尾部向队列中添加新元素，其函数原型如下：

前置条件：queue为之前创建的队列，value是待加入队尾的数据；

后置条件：如果队列不满，将value添加至队尾，该函数返回true；否则，队列已满，队列保持不变，该函数返回false。

其调用形式如下：

• 从队头移除项（出队列）

用户通过该函数可以从队列头部移除一个元素，其函数原型如下：

前置条件：queue为之前创建的队列，p_value为指向存储"移出队列的值"的变量的指针；

后置条件：如果队列不空，将队头的值拷贝到*p_value，同时删除当前队头，该函数返回true；否则，队列为空，该函数返回false。

其调用形式如下：

• 判断队列是否为空

判断队列是否为空的函数原型如下：

前置条件：queue为之前创建的队列；

后置条件：如果队列为空，则返回true，否则返回false。

其调用形式如下：

• 判断队列是否已满

判断队列是否已满的函数原型如下：

前置条件：queue为之前创建的队列；

后置条件：如果队列为空，则返回true，否则返回false。

其调用形式如下：

• 确定队列中元素的个数

确定栈中元素的个数的函数原型如下：

前置条件：queue为之前创建的队列；

后置条件：返回队列中元素的个数。

其调用形式如下：

程序清单 3.70 抽象队列接口（queue.h）

>>>3.6.3 实现与使用接口

在实现队列之前，首先需要确定使用何种数据存储结构。一般来说，可以使用地址连续的内存空间存储数据，比如，使用数组或动态分配一段内存空间；也可以使用地址非连续的链表结构存储数据。

1、顺序队列

在实现队列之前，我们先来分析一下顺序队列的原理。顺序队列采用连续的内存空间，假定使用front和rear两个变量来分别表示队头和队尾的位置，初始时，队列为空，队头和队尾都在为0，详见图3.29 (a)。

当从队尾增加数据时，rear增大向后移动，如data0入队列后，示意图详见图3.29 (b)，此时，队头front保持不变，队尾rear增加1，继续入队列，data1、data2、data3入队列后的示意图详见图3.29 (c)。

图3.29  队列示意图——入队