3.4.2 队列的抽象数据类型

队列的抽象数据类型定义了队列的数据对象、数据关系及基本操作。队列的抽象数据类型定义如下：

ADT Queue

{

数据对象：D={a_i|a_i∈ElemSet，i=1，2，…，n，n≥0}

数据关系：R={<a_i-1,a_i>|a_i-1，a_i∈D，i=2，3，…，n}

约定a₁端为队列头，a_n端为队列尾。

基本操作：

（1）InitQueue（&Q）

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

操作结果：建立一个空队列Q。

这就像日常生活中，火车站售票处新增加了一个售票窗口，这样就可以新增一队用

来排队买票。

（2）QueueEmpty（Q）

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

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

这就像售票员查看窗口前是否还有人排队买票。

（3）EnQueue（&Q,e）

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

操作结果：插入元素e到队列Q的队尾。

这就像排队买票时，新来买票的人要排在队列的最后。

（4）DeQueue（&Q,&e）

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

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

这就像排在队头的人买过票后离开队列。

（5）Gethead（Q,&e）

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

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

这就像询问排队买票的人是谁。

（6）ClearQueue（&Q）

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

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

这就像排队买票的人全部买完了票，离开队列。

}ADT Queue