1.1.3 栈和队列

栈和队列都是特殊的线性表，其定义符合线性表的定义，其操作也类似于线性表的操作，只不过增加了一些限定而已。

1.栈的定义与操作

栈（Stack）是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶（Top），另一端为栈底（Bottom），如图1-2所示。当表中没有元素时称为空栈。栈顶元素总是后插入的元素，也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才能被删除的元素。

假设栈S=（al,a2,a3,…,an），则a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,a3,…,an的次序进栈，退栈的第一个元素应为栈顶元素，换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为先进后出表（First In Last Out，FILO），或后进先出表（Last In First Out，LIFO）。

栈的操作主要有入栈运算、退栈运算（出栈）和读栈顶元素。

1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加1（即Top加1），然后将元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不能再进行入栈操作，这种情况称为栈“上溢”错误。

2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减1（即Top减1）。当栈顶指针为0时，说明栈空，不可进行退栈操作，这种情况称为栈的“下溢”错误。

3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。

2.队列的定义与操作

队列（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）时，不能进行出队运算，这种情况称为“下溢”。