6队列的特点及其表示实现.

队列的特点及其表示实现教学目的：1.掌握队列的有关概念和特点。2.熟练掌握循环队列的基本操作（队列初始化、入队列和出队列）实现算法，特别注意队满和队空的描述方法。*3.会在相应的应用问题中正确选用队列，注意理解操作受限的含义。重点难点：队列的操作特点。3.4队列*3.4.1抽象数据类型队列的定义*3.4.2链队列-队列的链式表示和实现3.4.3循环队列-队列的顺序表示和实现教学内容内容回顾栈的特点及其表示实现3.4队列线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n导入队列：队列是一种只允许在表的一端插入，在另一端删除的存取受限的线性表。概念：队尾rear：插入端，线性表的表尾。队头front：删除端，线性表的表头。3.4.1抽象数据类型队列的定义队列(Queue)图示操作特点：先进先出(FIFO：FirstInFirstout)a1a2a3an-1出队列入队列队头队尾……ADTQueue{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾基本操作：}ADTQueue队列的抽象数据类型定义队列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())用链表表示的队列简称为链队列。一个链队列显然需要分别指示队头和队尾的两个指针。为了方便操作，添加一个头结点，并令头指针指向头结点。…a2rearfronta1an∧3.4.2链队列-队列的链式表示和实现(a)非空队Q.frontQ.reara1an∧…a2(b)空队Q.front==Q.rearQ.rearQ.front∧(c)链队中只有一个元素结点Q.frontQ.reara1∧1.基本形态typedefstructQNode{//结点类型QElemTypedata;structQNode*next;}QNode,*QueuePtr;2.链队列——链式映象typedefstruct{//链队列类型QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列StatusInitQueue(LinkQueue&Q){//构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front-next=NULL;returnOK;}StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERRORif(Q.front==Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;//注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。free(p);returnOK;}3.4.3循环队列-队列的顺序表示和实现1、顺序存储：用一组地址连续的存储单元依次存放从队头到队尾的元素，另外还需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。简单说，“数组+头、尾位置”为了在C语言中描述方便，约定：初始化建空队列时令：front=rear=0，每当插入新的队列尾元素时，rear+1，每当删除队列头元素时，front+1，因此，在非空队列中，头指针始终指向队头元素，尾指针始终指向队尾元素的下一个位置。例如：空队列J7J6J56543210Q.front=4Q.rear=7J1J2J3J4相继入队6543210Q.front=Q.rear=06543210Q.front=4Q.rear=4J1J2J3J4相继出队6543210Q.front=0J1J2J3J4Q.rear=4J5J6J7相继入队入队Q.rear=Q.rear+1出队Q.front=Q.front+1假溢出当Q.rear==MAXSIZE时，表示队满，但队列中还有空闲单元，称为“假溢出”解决方法：把队列设想为一个循环的表，将Q.data[0]接在Q.data[MAXSIZE-1]之后，即如果Q.rear=MAXSIZE则令Q.rear=0.入队：Q.rear=(Q.rear+1)%MAXSIZE;出队：Q.front=(Q.front+1)%MAXSIZE;0654321Q.front=0Q.rear=0空队列0654321Q.front=0Q.rear=4J1J2J3J4J1J2J3J4相继入队J1J2J3J4相继出队654321Q.front=4Q.rear=40J5J6J7相继入队J7入队时，Q.rear=(6+1)%71654320Q.front=4Q.rear=0J5J6J7J7J6J56543210Q.front=4J8J9J10J11Q.rear=4J8J9J10J11相继入队6543210Q.front=4Q.rear=0J5J6J7Q.front=06543210J8J9J10J11Q.rear=4J5J6J7相继出队4J14J13J12653210Q.front=0J8J9J10J11Q.rear=0J12，J13，J14相继入队6521Q.front=0Q.rear=00346521Q.front=0Q.rear=0034J8J9J10J11J12J13J14Q.front==Q.rear==0空队列Q.front==Q.rear==0满队列如何判断循环队列的满与空？如何判断循环队列的满与空：1、设一标志位2、空出一个元素的空间3、使用计数器6521Q.front=0Q.rear=6034J1J2J3J4J5J6J1J2----J6相继入队后此时Q.rear=6定为队满即：(Q.rear+1)%7==Q.front约定：以队列头指针在队列尾指针的下一个位置（指环状的下一个位置）上作为队列呈“满”状态的标志。判定循环队列队满(Q.rear+1)%MAXSIZE==Q.front2、类型定义（实际实现）constintMAXSIZE=20;typedefstruct{QElemType*base;//QElemTypebase[MAXSIZE];intfront;//队头指针intrear;//队尾指针}SqQueue;其中队头指针始终指向队头元素，队尾指针始终指向队尾元素的下一个位置。front、rear并不是真正的指针变量，而是两个整型变量，分别存放队头队尾元素的位置（下标）1）初始化StatusInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;returnOK;}3.基本操作实现2）入队列StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}3）出队列StatusDeQueue(SqQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK;否则返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}4）求队列长度IntQueueLength(SqQueueQ){//返回Q的元素个数，即队列的长度}return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;课堂总结主要内容：队列的有关概念和特点，链队列和循环队列的基本操作（队列初始化、入队列和出队列），特别注意队满和队空的描述方法。重点难点：队列的操作特点，循环队列的运算特点。课堂练习1.设栈S和队列Q的初始状态为空，元素e1e2e3e4e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队序列为e2e4e3e6e5e1，则栈S的容量至少应该是多少（即至少能存放的元素个数）？要求写出分析过程（操作）。2.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]栈的应用(上机练习)教学目的：*1.会在相应的应用问题中正确选用栈解决问题，注意理解操作受限的含义。3.2栈的应用举例3.3栈与递归的实现教学内容3.2栈的应用举例例1、数制转换例2、括号匹配的检验例3、行编辑程序问题例4、迷宫求解例5、表达式求值例6、实现递归例1：数制转换算法基于原理：N=(Ndivd)×d+Nmodd如：106=（106div10)×10+106mod10例如（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序voidconversion(){InitStack(S);scanf(%d,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}}//conversion例2：括号匹配括号匹配问题括号匹配{[()]}，((){})，()括号不匹配(()，()]，([)]检查括号匹配的算法设一栈遇到左括号则入栈，遇到右括号时，若栈空，则不匹配(右括号太多)，否则，如果栈顶元素与该右括号匹配，则出栈，否则不匹配(括号不配对)。输入结束后，若栈为空，则匹配，否则不匹配(左括号太多)。检查括号匹配的算法//检查括号匹配的算法boolmatch(){InistStack(S);read(c);while(c!=EOF){switch(c){case'(‘,'[‘,'{':Push(S,c);break;case')‘,']‘,'}':if(StackEmpty(S))returnfalse;Pop(S,e);if(c==')'&&e!='(')returnfalse;if(c==']'&&e!='[')returnfalse;if(c=='}'&&e!='{')returnfalse;break;}read(c);//读下一个字符}if(StackEmpty(S))returntrue;elsereturnfalse;}