3.3 队列及其应用
队列也称作队。队列和栈一样也是一种特殊的线性表，其运算规则较一般线性表有更多的约束和限制，称作限定性数据结构。本节将讨论队列的结构特点、循环队列的基本运算及应用。
3.3.1 队列的基本概念和结构特征
队列（Queue）是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出（Fist In Fist Out，FIFO）的特性。这与日常生活中的排队是一致的，最早进入队列的人最早离开，新来的人总是加入到队尾。
在队列中，允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。假设队列为q＝（a1，a2，…，an），那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…，an的顺序进入的，退出队列也必须按照同样的次序依次出队。也就是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列，如图3-9所示。
图3-9 队列示意图
队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。凡是申请输出的作业都从队尾进入队列。
为了队列的操作方便，同时为避免占用过多的存储空间，通常开辟一个连续的存储空间来存储队列中的元素，并设想这一连续的存储空间是一个首尾相接的圆环。把这种队列的存储方式形象地叫做循环队列，如图3-10所示。
图3-10 循环队列示意图
在队列的入队、出队操作中，设定front始终指向队头元素前面的一个位置，rear指向队尾元素，最后一个元素出队后，front＝＝rear，因此，程序中把front＝＝rear当作队空的判断条件。队列初始化操作中，front和rear赋相同的值。
在循环队列中，设队列的最大存储空间为Maxsize。入队操作时，rear需要加1后移一位，其值在0～Maxsize-1中循环出现，赋值语句为rear＝（rear＋1）%Maxsize，同样出队操作，front加1后移的语句为front＝（front＋1）%Maxsize。
在循环队列中，如果设队满时数据元素个数达到Maxsize，队满时rear＝＝front，这个条件和判断队空条件一样，出现了混淆。为了区分队空和队满两种状态，设队满时数据元素的个数为Maxsize-1，把（rear＋1）%Maxsize＝＝front当作队满的条件，牺牲一个存储空间，就把队空和队满的条件区别开来。这样，在出队操作前，首先判断队列是否为空，判断条件为front＝＝rear；在入队操作前，首先判断队列是否已满，判断条件为（rear＋1）%Maxsize＝＝front。
3.3.2 队列的基本运算
假设队列得到元素个数最大不超过整数Maxsize-1，所有的元素个数都具有同一数据类型DataType。变量front指向队列的头部，变量rear指向队列的尾部。
1.定义队列类型queue
2.循环队列的入队enq（QU，x）
将整数x插入到QU队列中的函数：
3.循环队列的出队deq（QU，x）一个QU队列尾部元素出队的函数：
4.读循环队列的头元素gethead（QU，x）
读取循环队列QU的队列头元素的函数：
5.判断循环队列是否为空isEmpty（QU）
判断循环队列QU是否为空的函数：
3.3.3 队列的应用
人们在日常社会生活中时常会通过排队以得到各种社会服务。例如，银行业务系统、各种票证出售系统等。这种服务系统设有若干窗口，用户可以在营业时间内随时前去。如果当时有空闲窗口，可以立即得到服务；若窗口均有用户占用，则需排在人数最少的队列后面。由于用户的到达时间、服务时间等均为随机的事件，特别是用户到达的时间是离散的，故称为离散事件。现要编制一个程序来模拟这种活动，并计算一天中用户在此逗留的平均时间。为了计算平均时间，要求掌握每个用户的到达时间和离开时间。
1.具体问题
假设服务系统有4个窗口对外接待客户，在营业时间内不断有客户进入并要求服务。由于每个窗口只能接待一个客户，因此进入该服务系统的客户需在某一窗口前排队。如果窗口的服务员忙，则进入的客户需排队等待，闲则可立即服务，服务结束则从队列中撤离，并计算一天中进入服务系统的客户的平均逗留时间。
2.分析
为了模拟4个窗口服务系统必须有4个队列与每一个窗口相对应，并能反映每一窗口当前排队的客户数。当有一个客户到达时，则排在队列最短的窗口等待服务。当有一个客户服务完毕，则离开相应的窗口，从队列中撤离。
为了计算平均逗留时间，则必须记录客户的到达时间和离开时间。
因此，影响系统队列变化的原因有以下两种：
1）新客户进入服务系统，该客户加入到队列最短的窗口队列中。
2）4个队列中有客户服务完毕而撤离。
这两种原因共有5种情况，我们把这5种情况称为事件。由于这些事件是离散发生的，故称为离散事件。这些事件的发生是有先后顺序的，依次构成事件表。
在该服务系统中，某一时刻有且仅有一个事件（5种事件中的一个）发生。一旦某一事件发生，则需改变系统状态（队列状态），因此整个服务系统的模拟就是按事件表的次序，依次根据事件来确定系统状态的变化，即事件驱动模拟。
3.模拟程序应如何运行
假设事件表中最早发生的是新客户到达，则随之应得到两个时间：一是本客户处理业务所需时间；二是下一客户到达服务系统的时间间隔。此时模拟程序应做的工作有：
1）比较4个队列中的客户数，将新到客户插入到最短队列中。若队列原来是空的，则插入的客户为队头元素，此时应设定一个新的事件——刚进入服务系统的客户办完业务离开服务系统的事件插入事件表。
2）设定一个新的到达事件——下一客户即将到达服务系统的事件插入事件表。若发生的事件是某队列中的客户服务结束离开服务系统，则模拟程序应做两件工作：①从队头删除客户，并计算该客户在服务系统中的逗留时间；②当队列非空时（用户离开后），应把新的队头客户设定为一个新的离开事件，计算该客户离开服务系统的时间，并插入事件表。当服务系统停止营业后，若事件表为空，则程序运行结束。
4.数据结构考虑
在该仿真（模拟）程序中，主要应设置4个队列和一个有序事件表。此处用到3.4节讲到的链表知识。
队列采用单链表来实现，其中单链表中的每个结点代表一个客户应有两个数据：客户的到达时间和服务时间。该链队列有一个队头结点，包括的数据是队列中的客户数。
事件表用单链表来实现，其中的每个结点代表一个事件，包括的数据项有：事件发生时间和事件类型。事件类型为0、1、2、3、4，其中0表示客户到达事件，1、2、3和4分别表示4个窗口的客户离开事件。事件表中最多有5个事件，当事件表为空时程序运行结束。
根据上面的讨论，其数据结构说明如下：
5.仿真程序的实现
根据以上的分析，以下给出该仿真程序的关键部分。有兴趣的读者可以据此写出完整的仿真程序。
