第三章--栈和队列(第二部分).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,3.4,队列,队尾,队头,a,1,a,2,a,3,入队,出队,队列：一个只能在队首进行删除、队尾进行插入的线性表。,队尾（,rear,）：允许插入的一端。,队头（,front,）：允许删除的一端。,特征：先进先出（,FIFO,）。,3.4,队列,3.4,队列（续）,3.4.1,链队列的表示和实现,3.4.2,顺序队列的表示和实现,链队列的表示和实现,链队列：队列的链式存储结构，它是限制仅在表头删除和表尾插入的单链表。,显然,仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。,front,a,1,a,2,a,n,rear,链队列的表示和实现,链队列的定义,typedef,struct,Qnode,Qelemtype,data;,struct,Qnode,*next;,Qnode,*,Queueptr,;,Typedef,struct,Queueptr,front;,Queueptr,rear;,LinkQueue,;,链队列是否需要头结点,？,为了操作的方便，在链队列中也添加,一个头结点,，并使,队头指针,指向,头结点,。,如何判断队空,？,队空条件为,Q.,front=Q.rear,front,rear,队列的基本操作：,判断队列是否为空,(,QueueEmpty,),入队,(,EnQueue,),出队,(,DeQueue,),判断队空算法,Status,QueueEmpty,(,LinkQueue,Q),if(Q.front,=,Q.rear,)return TRUE;,else return FALSE;,rear,e,p,front,a,1,a,n,rear,front,e,p,rear,rear,入队算法,在队尾插入,算法描述：,Q.rear,-next=p;,Q.rear,=p;,入队算法,在队尾插入（续）,算法描述：,（,1,）在队尾新申请一个结点空间,QNode,，并用指针,p,指向该结点，若申请不到，返回,overflow,；,（2,）分别定义这个结点的数据域为值,e,和指针域为,NULL,；,（,3,）把新申请的结点插入到队尾，并成功返回；,入队算法,在队尾插入（续）,Status,EnQueue,(,LinkQueue,&Q,QElemType,e),p=(,QNode,*),malloc,(,sizeof(QNode,);,if(!p),exit(OVERFLOW,);,p-data=e;,p-next=NULL;,Q.rear,-next=p;,Q.rear,=p;,return OK;,front,a,1,a,2,a,n,rear,p,算法描述：,p=,Q.,front,-next;,Q.,front,-next=p-next;,出队算法,在队头删除,front,a,1,a,2,a,n,rear,p,考虑边界情况：队列中只有一个数据元素？,front,a,1,p,rear,rear,出队算法,在队头删除（续）,算法描述：,if(,Q.rear,=p),Q.rear,=,Q.front,;,出队算法,在队头删除（续）,总结,删除时的三种情况：,删除前队列已空；,删除前结点数,1,；,删除前结点数,=1,，删除后为空队列。,出队算法,在队头删除（续）,算法描述：,（,1,）当链队列为空时，返回,ERROR,；,（,2,）让指针,p,指向第一个结点，用,e,返回要删除结点数据域的值，删除这个结点；,（3,）当删除前结点数只有一个时，修改尾指针,Q.rear,；,（,4,）最后，释放指针,p,所指结点空间，并成功返回。,出队算法,在队头删除（续）,Status,DeQueue(LinkQueue,&Q,QElemType,&e),if(Q.front=Q.rear)return ERROR;,p=Q.front-next;,e=p-data;,Q.front-next=p-next;,if(Q.rear=p),Q.rear,=Q.front;,free(p);,return OK;,请思考：,对于出队算法，在什么情况下需要修改队尾,Q.rear,指针？为什么？,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队，仿照顺序表,n,个元素存放在前,n,个单元中。,a,1,a,2,a,3,a,4,队列的顺序存储结构及实现（顺序队列）,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,1,a,2,a,3,a,4,队列的顺序存储结构及实现（顺序队列）,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,2,a,3,a,4,队列的顺序存储结构及实现（顺序队列）,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,3,a,4,请思考：当队列中有,n,个元素时，出队操作的时间复杂度？,队列的顺序存储结构及实现（顺序队列）,O,(,n,),如何改进出队的时间性能？,放宽队列的所有元素必须存储在数组的前,n,个单元这一条件，只要求队列的元素存储在数组中连续的位置。,设置队头、队尾两个指针,队列的顺序存储结构及实现（顺序队列）,队列的顺序存储结构及实现（顺序队列）,顺序队列：用,一维数组,空间来存放当前队列中的元素。,设,两个指针,和分别指示,队头和队尾,元素在队列中的位置。,队头和队尾指针在队列初始化时，令,front=rear=0,；,队头指针指向当前队头元素；,队尾指针指向当前队尾元素的下一个位置；,每当插入新的队列尾元素时，在队尾指针处插入新的元素后，队尾指针增,1,；,每当删除队列头元素时，取队头指针处的元素值，队头指针增,1,。,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,front rear,队列的顺序存储结构及实现（顺序队列）,入队操作时间性能为,O,(1),0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,a,2,rear,入队操作时间性能仍为,O,(1),front,队列的顺序存储结构及实现（顺序队列）,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,a,2,a,3,rear,入队操作时间性能仍为,O,(1),front,队列的顺序存储结构及实现（顺序队列）,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,a,2,a,3,a,4,rear,入队操作时间性能仍为,O,(1),front,队列的顺序存储结构及实现（顺序队列）,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,1,a,2,a,3,a,4,rear,front,队列的顺序存储结构及实现（顺序队列）,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,2,a,3,a,4,rear,front,出队操作时间性能提高为,O,(1),队列的顺序存储结构及实现（顺序队列）,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,3,a,4,rear,front,队列的顺序存储结构及实现（顺序队列）,假溢出：,当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,继续入队会出现什么情况？,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,队列的顺序存储结构及实现（顺序队列）,循环队列：,将存储队列的数组头尾相接。,如何解决假溢出？,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,rear,a,6,队列的顺序存储结构及实现（顺序队列）,0,1,2,3,4,5,6,7,front,B,C,Drear,一般情况,A,队列的顺序存储结构及实现（顺序队列）,请思考：循环队列的队空和队满的判定条件？,如何判断循环队列队空？,队空的临界状态,0 1 2 3 4,入队,出队,a,3,rear,front,队列的顺序存储结构及实现（顺序队列）,如何判断循环队列队空？,执行出队操作,0 1 2 3 4,入队,出队,a,3,rear,front,队列的顺序存储结构及实现（顺序队列）,如何判断循环队列队空？,执行出队操作,队空：,front=rear,0 1 2 3 4,入队,出队,a,3,front,rear,队列的顺序存储结构及实现（顺序队列）,front,0,1,2,3,4,5,6,7,rear,空队列,front,如何判断循环队列队满？,队满的临界状态,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,a,6,队列的顺序存储结构及实现（顺序队列）,如何判断循环队列队满？,执行入队操作,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,a,6,队列的顺序存储结构及实现（顺序队列）,如何判断循环队列队满？,执行入队操作,队满：,front=rear,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,a,6,rear,a,7,队列的顺序存储结构及实现（顺序队列）,rear,C,0,1,2,3,4,5,6,7,队满,front,rear,D,E,F,G,A,B,C,H,队空、队满的判定条件出现二义性。,如何将队空和队满的判定条件分开？,方法一：,修改队满条件，浪费一个元素空间，队满时队列中还有一个空闲单元,；,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,a,6,队列的顺序存储结构及实现（顺序队列）,C,0,1,2,3,4,5,6,7,队满,front,rear,D,E,F,G,A,B,C,H,C,0,1,2,3,4,5,6,7,队满,(,正确,),front,rear,D,E,F,G,A,B,C,方法二：,设置一个标志,flag,。当,flag=0,表示出队列，此时为空；当,flag=1,时表示入队列，此时为满。,队空、队满的判定条件出现二义性。,如何将队空和队满的判定条件分开？,方法三：,使用一个,计数器,记录队列中元素的个数。附设一个存储队列中元素个数的变量如,num,，当,num=0,时队空，当,num=,MaxSize,时队满。,队列的顺序存储结构及实现（顺序队列）,本章总结,3.1,栈,3.1.1,栈的定义,3.1.2,栈的表示和实现,顺序栈的算法：创建栈、进栈、出栈、取栈顶元素。,要求：会写以上每个算法，明白算法表达的含义,。,3.2,栈的应用举例,3.2.1,数制转换,3.2.2,括号匹配的检验,3.3,栈与递归的实现,阶乘函数、斐波那契数列函数、汉诺塔问题,以上要求：理解以上每个算法，明白算法表达的思想。,3.4,队列,3.4.1,链队列的表示和实现,链队列的算法：,判队列是否为空、入队、出队。,要求：会写以上每个算法，明白算法表达的含义。,3.4.2,顺序队列,循环队列,顺序队列的物理结构？,什么是假溢出？如何解决假溢出？,如何解决队空和队满的判定条件相同的情况？,