队列（Queue）是只允许在一端删除、在另一端插入的顺序表。允许删除的一端叫作队头（Front），允许插入的一端叫作队尾（Rear），如图1-3所示。

 

（1）队列的运算

当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…,an，也就是说队列的修改是按先进先出的原则进行的。因此队列亦称为先进先出的线性表，或后进后出的线性表。

1）入队操作：往队列队尾插入一个元素称为入队运算。

2）出队操作：从队列队头删除一个元素称为出队运算。

（2）循环队列的运算

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

在循环队列中，用队尾指针Rear指向队列中的队尾元素，用队头指针Front指向排头元素的前一个位置。因此，从排头指针Front指向的后一个位置直到队尾指针Rear指向的位置之间的所有元素均为队列中的元素。

在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（Queuesize-l）时，其加1操作的结果是指向向量的下界0。

由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过Front=Rear来判断队列是空还是满。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志值，其定义如下：当s=0时表示队列空，当s=1时表示队列非空。

入队运算：入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进1（即Rear=Rear+1），且当Rear=m+l时置Rear=1；然后将新元素插入到队尾指针指向的位置。当循环队列非空（s=l）且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。

出队运算：出队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进1（即From=Front+1），且当Front=m+1时置Front=1，然后将排头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行出队运算，这种情况称为“下溢”。