预计阅读本页时间：-
正如您所看到的，用抽象数据类型方法进行C语言编程包含下面三个步骤：
1．以抽象、通用的方式描述一个类型，包括其操作。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
2．设计一个函数接口来表示这种新类型。
3．编写具体代码以实现这个接口。
您已经看到如何把这种方法应用于简单列表。现在，将其应用于一个更复杂的数据类型：队列。
17.4.1 定义队列抽象数据类型
队列（queue）是具有两个特殊属性的列表。第一，新的项目只能被添加到列表结尾处，在这方面，队列与简单列表类似。第二，项目只能从列表开始处被移除。可以将队列看成是一队买电影票的人。您在队尾加入队列，在买完票后从队首离开。队列是一种“先进先出（First In, First Out, FIFO）”的数据形式，就像买电影票的队伍一样（如果没有人插队）。让我们仍然建立一个非正式的抽象定义，如表17.2所示：
表17.2 队列类型总结
| 类 型 名 称： | 队 列 |
|---|---|
| 类型属性： | 可保存一个规则的项目序列 |
| 类型操作： | 把队列初始化为空队列 |
| 确定队列是否为空 | |
| 确定队列是否已满 | |
| 确定队列中的项目数 | |
| 向队列尾端添加项目 | |
| 从队列首端删除和恢复项目 | |
| 清空队列 |
17.4.2 定义接口
接口定义将包含在queue.h文件中。我们将使用C的typedef工具创建两个类型名：Item和Queue。相应结构的确切实现应该是queue.h文件的一部分，但从概念上讲，结构的设计属于具体实现阶段。现在，我们假设已经定义了这些类型，集中考虑函数原型。
首先考虑初始化。这将改变一个Queue类型的变量，所以函数应把一个Queue变量的地址作为参数：
接下来，确定队列为空或满涉及到返回真或假值的函数。这里我们假设C99的stdbool.h头文件可用。如果该文件不可用，可以使用int类型或自定义一个bool类型。因为函数不改变队列，所以它可以接受一个Queue参数。但另一方面，如果只传递Queue的地址，可能会更快一些并可以节省内存，这取决于Queue类型对象的大小。这次我们尝试这种方法。另一个好处是，这样所有的函数都将把地址作为参数，而不像List例子中的情况。为了表明函数不改变队列，您可以而且也应该使用const限定词：
解释一下，指针pq指向一个不能通过pq改变的Queue数据对象。可以为返回队列中项目数的函数定义一个类似的原型。
向队列的尾端添加项目需要表示项目和队列。这种情况下将改变队列，所以必须（而不是可选）使用指针。函数可以是void类型，或者您可以使用返回值来指示添加项目操作是否成功。我们采用第二种方法：
最后，删除项目可以有多种做法。如果把项目定义为一个结构或基本类型之一，可以由函数返回项目。函数参数可以是Queue或者指向Queue的指针。因此，一种可能的原型如下：
但是，下面的原型更为通用：
把从队列中删除的项目存放在由pitem指针指向的位置，并且用返回值指示操作是否成功。
用于清空队列的函数所需的惟一参数是队列的地址，可以使用下面的原型：
17.4.3 实现接口的数据表示
第一步是决定队列使用哪种C数据形式。一种可能是数组。数组的优点是便于使用，并且向数组中已有数据的末尾添加项目很简单。但从队列首端删除项目会导致问题。在买票队伍的模型中，从队列首端删除一个项目包括复制数组首元素的值，然后将数组中剩下的每一项都向前移动一个元素。编程实现这个过程很简单，但是这会浪费计算机的大量时间（请参见图17.6）。
另一种解决数组实现中删除问题的方法是保持剩下的元素不动,并改变队列首端的位置（请参见图17.7）。这种方法的问题在于空出的元素变成盲区，所以队列中的可用空间将不断减少。
图17.6 用数组实现队列
图17.7 重新定义队列首端元素
解决盲区问题的一种聪明方法是使队列成为环形（circular）。这意味着将数组的首尾相连。即数组首元素直接跟在末元素后面，这样当到达数组末尾时，如果首元素空出，就可以开始把新添加的项目存放到这些空出的元素中。（请参见图17.8）可以设想在一张条形纸上画出数组，然后将数组的首尾粘起来形成一个环。当然，现在应做一些有趣的标记来确保队列尾端没有超过首端。
图17.8 一个环形队列
另一种方法是使用链表。其优点是删除首项时不需要移动其他所有项，只须重置首指针以指向新的首元素。因为我们已经讨论过链表，所以将遵循这个思路。为了测试我们的想法，我们将从一个整数队列开始。
链表由节点组成，所以下一步定义节点：
对于队列来说，需要保存首尾项的地址，这可以通过使用指针来实现。也可以使用一个计数器来保存队列中的项目个数。因此，该结构需要有两个指针成员和一个int类型的成员。
注意Queue是含有3个成员的结构，所以前面使用指向队列的指针代替整个队列来作为函数参数的决定节省了时间和空间。
下面考虑队列的大小。链表的大小由可用内存的数量限制，但是往往比这小得多的链表更符合实际情况。比如，您可以使用队列模拟飞机等待在机场着陆。如果等待的飞机数太多，新到的飞机就应该改在其他机场着陆。我们把队列最大长度设为10。程序清单17.6含有队列接口的定义和原型。它把Item类型的确切定义留给用户。在使用该接口时，您可以为您的特定程序插入合适的定义。
程序清单17.6 queue.h接口头文件
实现接口函数
现在我们开始编写接口的实现代码。首先，把队列初始化为空意味着设置首尾指针为NULL并设置项数（items成员）为0：
然后，items成员使得对满列和空列的检查以及返回队列中的项数变得简单：
向队列中添加项目包括下列步骤：
1．创建新节点。
2．把项目复制到新节点。
3．设置节点的next指针为NULL,表明该节点是列表中的最后一个节点。
4．设置当前尾节点的next指针指向新节点，从而将新节点链接到队列中。
5．把rear指针设置为指向新节点，以便找到最后的节点。
6．项目个数加1。
函数还需要处理两种特殊情况。首先，如果队列为空，front指针也应该设为指向新节点。因为如果只有一个节点，那么这个节点既是队首也是队尾。第二，如果函数不能给节点获取所需的内存，就需要执行一些动作。因为我们假设使用小型队列，这样的情况应该很少见，所以如果程序运行的内存不足，我们只是让函数中止程序。EnQueue（）的代码如下：
CopyToNode（）函数是把项目复制到节点中的静态函数：
从队列首端删除项目包括下列步骤：
1．把项目复制到一个给定的变量中。
2．释放空闲节点使用的内存。
3．重置首指针，使其指向队列中的下一项。
4．如果最后一项被删除，把首尾指针均重置为NULL。
5．项目数减1。
下面是完成这些步骤的代码：
关于指针有些事项必须注意。第一，在删除最后一项时，代码没有明确设置front指针为NULL。因为它已经把front指针设置为被删除节点的next指针。如果这个节点是最后的节点，其next指针就为NULL，所以front指针就被设置为NULL。第二，代码使用临时指针pt来保存被删除节点的位置。因为指向第一个节点的正式指针（pq->front）被重置为指向下一个节点，所以如果没有临时指针，程序将不知道该释放哪个内存块。
我们可以使用DeQueue（）函数清空一个队列。循环调用DeQueue（）直到队列为空：
