4.3.1 什么是队列

队列严格按照“先来先得”原则，这一点和排队差不多。例如，在银行办理业务时都要先取一个号排队，早来的会先获得到柜台办理业务的待遇；购买火车票时需要排队，早来的先获得买票资格。计算机算法中的队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作。队列是一种比较有意思的数据结构，最先插入的元素也是最先被删除的；反之，最后插入的元素是最后被删除的，因此队列又称为“先进先出”（First In-First Out，FIFO）的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列和栈一样，只允许在断点处插入和删除元素，入队算法如下。

（1）tail=tail+1。

（2）如果tail=n+1，则tail=1。

（3）如果head=tail，即尾指针与头指针重合，则表示元素已装满队列，会施行“上溢”出错处理；否则Q(tail)=X，结束整个过程，其中X表示新的入队元素。

队列的抽象数据类型定义是ADT Queue，具体格式如下所示。

ADT Queue{
D={ai|ai∈ElemSet, i=1,2,…,n,  n≥0        //数据对象
R={R1},R1={i-1,ai>|ai-1,ai∈D, i=2,3,…,n } //数据关系
…基本操作
}ADT Queue

队列的基本操作如下。

· InitQueue(&Q)

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

· DestroyQueue(&Q)

初始条件：队列Q已存在。

操作结果：销毁队列Q。

· ClearQueue(&Q)

初始条件：队列Q已存在。

操作结果：将队列Q重置为空队列。

· QueueEmpty(Q)

初始条件：队列Q已存在。

操作结果：若Q为空队列，则返回True，否则返回False。

· QueueLength(Q)

初始条件：队列Q已存在。

操作结果：返回队列Q中数据元素的个数。

· GetHead(Q,&e)

初始条件：队列Q已存在且非空。

操作结果：用e返回Q中的队头元素。

· EnQueue(&Q,e)

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。

· DeQueue(&Q, &e)

初始条件：队列Q已存在且非空。

操作结果：删除Q的队头元素，并用e返回其值。

· QueueTraverse(Q, visit())

初始条件：队列Q已存在且非空。

操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()，一旦visit()失败，操作也就失败。