队列及其基本运算

2.4.2　队列及其基本运算

1．什么是队列

在计算机系统中，如果一次只能执行一个用户程序，则在多个用户程序需要执行时，这些用户程序必须先按照到来的顺序进行排队等待。这通常是由计算机操作系统来进行管理的。

在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：

①初始时线性表为空；

②当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；

③当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。

由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。

队列（queue）是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（front）指向排头元素的前一个位置。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”（FIFO，First In First Out）或“后进后出”（LILO，Last In Last Out）的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针rear与排头指针front共同反映了队列中元素动态变化的情况。如图2-10所示是具有6个元素的队列示意图。

图2-10　具有6个元素的队列示意图

往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。

如图2-11所示是在队列中进行插入与删除的示意图。由如图2-11所示可以看出，在队列的末尾插入一个元素（入队运算）只涉及队尾指针rear的变化，而要删除队列中的排头元素（退队运算）只涉及排头指针front的变化。与栈类似，在程序设计语言中，用一维数组作为队列的顺序存储空间。

图2-11　队列运算示意图

2．循环队列及其运算

在实际应用中，队列的顺序存储结构一般采用循环队列的形式。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。如图2-12所示。

在循环队列结构中，当存储空间的最后一个位置已被使用而要再进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

循环队列的初始状态为空，即rear=front=m。如图2-12所示。

图2-12　循环队列存储空间示意图

循环队列主要有两种基本运算：入队运算与退队运算。

每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1。

每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=l。

如图2-13（a）所示是一个容量为8的循环队列存储空间，且其中已有6个元素。如图2-13（b）所示是在如图2-13（a）所示的循环队列中又加入了2个元素后的状态。如图2-13（c）所示是在如图2-13（b）所示的循环队列中退出了1个元素后的状态。

图2-13　循环队列运算例

从如图2-13所示中循环队列动态变化的过程可以看出，当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：

由此可以得出队列空与队列满的条件如下：

队列空的条件为s=0；

队列满的条件为s=1且front=rear。

下面具体介绍循环队列入队与退队的运算。假设循环队列的初始状态为空，即：s=0，且front=rear=m。

（1）入队运算

入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针进一（即rear=rear+1），并当rear=m+1时置rear=1；然后将新元素插入到队尾指针指向的位置。

当循环队列非空（s=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。

（2）退队运算

退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基本操作：首先将排头指针进一（即front=front+1），并当front=m+1时置front=1；然后将排头指针指向的元素赋给指定的变量。

当循环队列为空（s=0）时，不能进行退队运算，这种情况称为“下溢”。