《数据结构》(C语言版)第三章-栈和队列解析.ppt

*3.4.3循环队列－队列的顺序表示和实现#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//动态分配存储空间intfront;//头指针，若队列不空，//指向队列头元素intrear;//尾指针，若队列不空，指向//队列尾元素的下一个位置}SqQueue;*实现：用一维数组实现base[M]P63图3.12123450空队列rear=0front=0J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrear123450frontJ1,J2,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfrontfront存在问题：当front=0,rear=M时，再有元素入队发生溢出——真溢出当front≠0,rear=M时，再有元素入队发生溢出——假溢出*解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让base[0]接在base[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算入队：base[rear]=e;rear=(rear+1)%M;出队：e=base[front];front=(front+1)%M;队满、队空判定条件*012345rearfrontJ4J5J6012345rearfrontJ3J8J7J3,J4,J5出队J6,J7,J8入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志位以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front3.使用一个计数器记录队列中元素的总数J4J5012345rearfront初始状态J3*StatusInitQueue(SqQueueQ){//构造一个空队列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;returnOK;}*StatusEnQueue(SqQueueQ,QElemTypee){//插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}*StatusDeQueue(SqQueueQ,QElemTypee){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK;否则返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}*第三章作业补充作业：1.设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为push(1)，pop()，push(2），push(3)，pop()，pop()，push(4)，pop()，则出栈的数字序列为什么？（2）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。2.写出检验括号匹配的算法。*3.12写出以下程序段的