和栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。假设队列为q=（a1,a2,…,an），那么，a1就是队头元素，an则是队尾元素。队列中的元素是按照a1,a2,…,an的顺序进入的，退出队列额只能按照这个次序依次退出，也就是说，只有在a1,a2,…,an-1都离开队列之后，an才能退出队列。

队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出作输出操作。凡是申请输出的作业都是从队尾进入队列。队列的操作与栈的操作类似，也有8个，不同的是删除时在表的头部进行。

下面给出队列的抽象数据类型定义：

InitQueue(&Q)

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

DestroyQueue(&Q)

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

操作结果：队列Q被撤销，不再存在。

ClearQueue(&Q)

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

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

QueueEmpty(Q)

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

操作结果：若Q为空队列，则返回TURE，否则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（）失败，则操作失败。

}ADT Queue

  凌阳教育，全国唯一一家原厂式嵌入式培训机构，专业从事嵌入式人才培训13年，最近新开课程信息安全工程师培训，想了解更多嵌入式资料下载或者是凌阳教育的动态，请访问凌阳教育官网www.sunplusedu.com。