1.4 栈和队列 考点10 栈及其基本运算 1什么是栈 栈实际也是线性表,只不过是一种特殊的线性表。栈(Stack)是只能在表的一端进行插入和删除运算配线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈(栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。 假设栈S=(al,a2,a3,…,an),则a1,称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…,an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为先进后出表(FILO,First In Last Out),或“后进先出”表(LIFO,Last In First Out),如图1-7所示。
2栈的顺序存储及其运算 (l)入栈运算:入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1),然后将元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈“上溢”错误。如图1-8所示。 (2)退栈运算:退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针减一(即t叩减1)。当栈顶指针为。时,说明栈空,不可进行退栈操作。这种情况称为栈的“下溢”错误。 (3)读栈顶元素:读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素,只是将它赋给一个变量,因此栈顶指针不会改变。当栈顶指针为0时,说明栈空,读不到栈顶元素。 考点11 队列及其基本运算 1什么是队列 队列(queue)是只允许在一端删除,在另一端插入的顺序表,允许删除的一端叫做队头(front),允许插入的一端叫做队尾(rear), 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…,an之后,a1是队头元素,an是队尾元素。显然退出队列的次序也只能是a1,a2,…,an也就是说队列的修改是依先进先出的原则进行的。因此队列亦称作先进先出(FIFO,First In First Out)的线性表,或后进后出(LILO,Last In Last Out)的线性表。往队列队尾插入一个元素称为入队运算,从队列的排头删除一个元素称为退队运算,如图1-10所示。 一个队列币。删除个儿素后的队列间插入元素E后的队列 2循环队列及其运算 在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间 在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置。因此,从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。 可以将向量空间想象为一个首尾相接的圆环,如图1-12所示,并称这种向量为循环向量,存储在其中的队列称为循环队列( Cireular Queue)。在循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(Queuesize-l)时,其加1操作的结果是指向向量的下界0。 由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,我们无法通过front=rear来判断队列“空”还是“满”。 在实际使用循环队列时,为了能区分队列满还是队列空,通常还需增加一个标志、,、值的定义如下:当s=0时表示队列空;当s=1时表示队列非空。 (l)入队运算 入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进一(即rear=rear 1),并当rear=m l时置rear=1;然后将新元素插入到队尾指针指向的位置。当循环队列非空(s=l)且队尾指针等于队头指针时,说明循环队列已满,不能进行入队运算,这种情况称为“上溢”。