队列的定义及抽象数据类型

3.4　队列的定义及抽象数据类型

队列（queue）是另一种特殊的线性表。在这种表中,删除运算限定在表的一端进行,而插入运算则限定在表的另一端进行。约定把允许插入的一端称为队尾（rear）,把允许删除的一端称为队首（front）。位于队首和队尾的元素分别称为队首元素和队尾元素。

图3－5　队列的示意图

假设线性表S＝（a,b,c,d,e）是一个队列数据结构,并且规定只能在末尾进行插入操作,在起始端进行删除操作,则该线性表的尾端为队尾,起始端为队首。则线性表S中元素e为队尾元素,元素a为队首元素,如图3－5所示。队列最大的特点在于利用这种数据结构能够将元素按照插入的顺序进行输出。例如:将一列元素按照a,b,c,d,e的顺序依次插入到队列中,则从队列中取出这些元素的顺序仍然是a,b,c,d,e。可以发现队列的特点为,先进入队列的元素先出来,后进入队列的元素后出来,因为队列的这一特性,故又将其称为先进先出的线性表（first in first out,简称为FIFO）。现实生活中很多活动都具有队列的特性,例如,等待服务的顾客总是按先来后到的次序排成一队,先得到服务的顾客是站在队首的先来者,而后到的人总是排在队列的末尾等待。

队列在计算机程序设计中也经常被使用。例如,操作系统中的输出队列就是一个例子。在一个允许多道程序运行的计算机系统中,有多个作业同时运行,而且运行的结果都要通过唯一的通道输出。若通道尚未完成输出,则后来的作业应等待,并按请求输出的先后顺序排队。当通道传输完毕可以接受新任务时,排头的作业便从队列中退出,进入通道并输出。所以,排头的作业总是下一次准备输出的作业,而排尾的作业总是刚刚进入队列的作业。当然,这里指的是没有优先级（priority）的情况。

队列的基本操作除了插入和删除之外,还包括队列的初始化、判空及获取队首元素等。队列的抽象数据类型定义如下。