栈与队列 编程初级教程

栈与队列西安交通大学计教中心ctec.xjtu.edu.cn栈的定义栈是限制在表的一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。如果多个元素依次进栈，则后进栈的元素必然先出栈，所以堆栈又称为后进先出（LIFO）表。堆栈设有一个栈顶指针标志栈顶位置。栈示意图a1a3a2进栈出栈top堆栈的主要操作有：•创建空栈。•进栈(push)操作:在栈顶插入元素。•出栈(pop)操作:在栈顶删除元素。•读栈顶元素:只是读出栈顶元素，并不改变栈内元素。顺序栈#defineSTACKSIZE100//堆栈最大可分配空间数量classSqStack{public:ElemTypedata[STACKSIZE];//存储元素的数组inttop;//栈顶指针，存储栈顶元素的下标SqStack(){top=-1;}//构造函数voidPush(ElemTypex);//入栈操作voidPop(ElemType&result);//出栈操作voidGetTop(ElemType&result);//取栈顶元素};一般将数组的0下标单元作为栈底，将栈顶元素的下标存储在栈顶指针top中，它随着元素进栈出栈而变化。top为-1表示空栈，top等于stacksize-1则表示栈满。哈罗小说网（1）进栈操作若栈不满，则在栈顶插入元素x作为新的栈顶。voidSqStack::Push(ElemTypex){if(topstacksize-1){top++;data[top]=x;}elsecout”栈满”;}（2）出栈操作若栈不空，则删除栈顶元素，用result返回其值。voidSqStack::Pop(ElemType&result){if(top-1){result=data[top];top--;}elsecout栈空;}（3）取栈顶元素若栈不空，则用result返回栈顶元素。voidSqStack::GetTop(ElemType&result){if(top-1){result=data[top];}elsecout栈空;}链式栈栈的链式存储结构实质上就是一个无头结点、只能在头部插入、删除元素的单链表。typedefstructnode{ElemTypedata;//数据域structnode*next;//指针域}SNode;classLinkStack{public:SNode*top;//栈顶指针LinkStack(){top=NULL;}//构造函数voidPush(ElemTypex);//入栈操作voidPop(ElemType&result);//出栈操作};（1）进栈操作若栈不满，则在栈顶插入元素x作为新的栈顶。voidLinkStack::Push(ElemTypex){SNode*p=newSNode;if(p!=NULL){p-data=x;p-next=top;top=p;}}（2）出栈操作若栈不空，则删除栈顶元素，用result返回其值。voidLinkStack::Pop(ElemType&result);{SNode*p;if(top!=NULL){result=top-data;p=top;top=top-next;deletep;}}举例:后缀表达式求值假定表达式是由加减乘除和数字构成。最简单的表达式为下列形式：(操作数S1)(运算符OP)(操作数S2)三种不同的表示方法：前缀表示法OPS1S2例如6+3写成+63中缀表示法OPS1S2例如6+3写成63+后缀表示法S1S2OP例如6+3写成63+同时，任何表达式都可分解为下列形式：(子表达式E1)(运算符OP)(子表达式E2)它的后缀表示法应写成：(E1的后缀表示)(E2的后缀表示)OP只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式都可写成前缀式或后缀式。例如：2*(6+3)2(6+3)*263+*。(注意：转化为后缀式后括号去掉)中缀式虽然容易理解，但在求值的时候利用前缀式或后缀式更为简单。用后缀式求值的算法为：首先设立一个堆栈，依此读取后缀式中的字符，若字符是数字，则进栈并继续读取，若字符是运算符（记为OP），则连续出栈两次得到数字S1和S2，计算表达式S1OPS2并将结果入栈，继续读取后缀式。当读到结束符时停止读操作，这时堆栈中只应该有一个数据，即结果数据。例如后缀式263+*的计算过程为2、6、3依次入栈，读+号则令3和6依次出栈，计算6+3后将结果9入栈，读*号则令9和2依次出栈，计算2*9后将结果18入栈。这时18就是最终结果。【例2-3】假定表达式是由不超过四个实数进行四则运算构成的算式，要编写一个程序来求解该算式的结果。中缀表达式变成等价的后缀表达式将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。步骤栈中元素输出结果说明1(（进栈2(1输出13(+1+进栈4(+12输出2512++退栈输出，退栈到（止6*12+*进栈7*(12+（进栈8*((12+（进栈9*((12+8输出810*((-12+8-进栈将中缀表达式(1+2)*((8-2)/(7-4))变成等价的后缀表达式。现在用栈来实现该运算，栈的变化及输出结果如下：11*((-12+82输出212*(12+82--退栈输出，退栈到（止13*(/12+82-/进栈14*(/(12+82-（进栈15*(/(12+82-7输出716*(/(-12+82-7-进栈17*(/(-12+82-74输出418*(/12+82-74--退栈输出，退栈到（止19*12+82-74-//退栈输出，退栈到（止2012+82-74-/**退栈并输出队列定义队列是只能在表的一端进行插入、在另一端进行删除操作的线性表。允许删除元素的一端称为队头，允许插入元素的一端称为队尾。显然不论元素按何种顺序进入队列，也必然按这种顺序出队列，所以队列又称为先进先出（FIFO）表。队列有两个活动端，所以设置了对头和队尾两个位置指针。一般队头指针记作front，队尾指针记作rear。abcfrontrear入队出队队列示意图循环队列—队列顺序存储顺序存储的队列中，每次出队列的元素必定是队头元素，因此如果采取与普通顺序表同样的操作方式，则每次出队操作必然将整个队列向前移动，这使得效率大大降低。因此在顺序存储的队列中，出队和入队操作都不移动元素而是移动指针。为方便起见，这里规定队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素所在位置。这样，入队和出队操作的执行步骤都是首先执行指针移动，再进行元素读写。对空队列而言，可假定front和rear的值为-1假溢出ABCfrontrearfrontrear(a)A‚B‚C入队(b)A‚B出队,D‚E入队(c)队列假溢出队列假溢出示意图CDEfrontrear随着元素不断入队列、出队列，rear和front指针会不断向后移动（如图(b)所示），最终会指向数组的最大下标位置（如图(c)所示）。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。循环队列解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。循环队列的基本操作方式为：•入队列时先执行rear=(rear+1)%M，再将新元素在rear指示位置加入；•出队列时先执行front=(front+1)%M，再将下标为front的元素取出。为了将队空和对满的条件加以区分，一般不使用front指针所指的位置。队空条件为front=rear队满条件为(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE(a)循环队列空(b)非空循环队列(c)循环队列满循环队列示意图循环队列描述如下：#defineMAXSIZE100//队列最大可分配空间数量classSqQueue{public:ElemTypedata[MAXSIZE];//存放元素的数组intfront;//队头指针intrear;//队尾指针voidEnQueue(ElemTypex);//入队操作voidDeQueue(ElemType&e);//出队操作voidGetHead(ElemType&e);//取队头元素};•front和rear指针取值均为所指数组单元的下标。•由于队头指针所指单元总是空的，length比实际能存储的元素多一。（1）入队操作若队列不满，则在队尾插入元素x作为新的队尾。voidSqQueue::EnQueue(ElemTypex){if((rear+1)%MAXSIZE==front)cout队列已满;else{rear=(rear+1)%MAXSIZE;data[rear]=x;}}常用算法（2）出队操作若队列不空，则删除队头元素并用e取回该元素的值。voidSqQueue::DeQueue(ElemType&e){if(rear==front)cout队列已空;else{front=(front+1)%MAXSIZE;e=data[front];}}（3）取队头元素若队列不空，则用e取回队头元素的值。voidSqQueue::GetHead(ElemType&e){if(rear==front)cout队列已空;else{inti=(front+1)%MAXSIZE;e=data[i];}}链队列—队列链式存储链队列实质上就是只能在头部删除元素、只能在尾部插入元素的单链表。队头指针front就是单链表的头指针，队尾指针rear则是指向单链表最后一个结点的指针。Qa1an∧frontrear非空链队列链队列的结点可定义如下：structQNode{ElemTypedata;structQNode*next;};链队列有两个指针，因此可采用下面定义:classLinkQueue{public:QNode*front;//队头指针QNode*rear;//队尾指针(下页继续……)(接上页)LinkQueue(){front=newQNode;//建立头结点front-next=NULL;rear=front;//尾指针也指向头结点}intLength();//求队列长度voidEnQueue(ElemTypex);//入队操作voidDeQueue(ElemType&e);//出队操作voidGetHead(ElemType&e);//求队头元素};（1）求队列的长度返回队列的元素个数，即队列的长度。intLinkQueue::Length(){QNode*p=front;intlen=0;while(p!=rear){len++;p=p-next;}returnlen;}（2）入队列操作插入元素x为队列新的队尾元素。voidLinkQueue::EnQueue(ElemTypex){QNode*s=newQNode;//建立新结点ss-data=x;s-next=NULL;rear-next=s;//在队尾插入结点srear=s;//修改队尾指针}（3）出队列操作若队列不空，则删除队头元素，用e返回其值。voidLinkQueue::DeQueue(ElemType&e){QNode*p;if(front==rear)cout队列已空;else{p=front-next;e=p-dat