[计算机二级公共基础知识总结]2017年计算机二级公共基础知识学习教程：栈和队列

　　（四）栈和队列

　　1．栈及其基本运算

　　1）栈

　　栈是一种特殊的线性表，它是限定在一端进行插入和删除的线性表。它的插入和删除只能在表的一端进行，而另一端是封闭的，不允许进行插入和删除操作。

　　在栈中，允许插入和删除操作一端称为栈顶，不允许插入和删除操作的一端则称为栈底。栈顶的元素总是最后被插入的元素，也是最先被删除的元素。它遵循的原则是：先进后出或后进先出。

　　堆栈指针总是指向栈顶元素的。

　　2）栈的顺序存储及其运算

　　在栈的顺序存储空间S（1：m）中，S（bottom）通常为栈底元素，S（top）为栈顶元素。Top=0表示栈空；top=m表示栈满。

　　1）入栈运算

　　即在栈的顶部插入一个新元素。操作方式是：将栈顶指针加1，再将元素插入至指针所指的位置。

　　2）退栈运算

　　退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是：先将栈顶元素赋给指定的变量，再将栈顶指针减1。

　　3）读栈顶元素

　　将栈顶元素赋给某一指定变量，但栈顶指针不变。

　　2．队列及其基本运算

　　1）队列

　　队列即是允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个尾指针指向队尾；允许删除的一端称为队首，通常用一个队首指针指向排队元素的前一个位置。

　　队列遵循的规则是：先进先出或后进后出

　　2）循环队列及其运算

　　队列的顺序存储结构一般采用循环队列的形式。

　　循环队列，即是次队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

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

　　循环队列的初始状态为空，即rear=front=m。这里m即为队列的存储空间。

　　循环队列的基本运算：入队运算和退队运算。

　　入队运算：每进行一次入队运算，队尾指针加1。当队尾指针rear=m+1时，即表示队列空间的尾部已经放置了元素，则下一个元素应该旋转到队列空间的首部，即rear=1

　　退队运算：每退队一个元素，排头指针加1。当排头指针front=m+1时，即排头指针指向队列空间的尾部，退队后，排头指针指向队列空间的开始，即front=1。

　　在队列操作时，循环队列满时，front=rear，队列空时，也有rear=front，即在队列空或满时，排头指针和队尾指针均指向同一个位置。要判断队列空或满时，还应增加一个标志，s值的定义：

　　判断队列空与队列满的条件下：

　　队列空的条件：s=0

　　队列满的条件：s=1、front=rear

　　（1）入队运算

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

　　当循环队列非空（s=1），且front=rear时，队列满，不能进行入队操作。此情况称“上溢”。

　　（2）退队操作

　　即将队首的元素赋给一个指定的变量。该运算也有两个基本操作：首先，将排头指针加1，即front=front+1，当front=m+1时，置front=1，然后，将排头指针指向的元素赋给指定的变量。

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

本文来源：https://www.wddqw.com/dZUO.html