数据结构-chap3 (2)队列.ppt

《数据结构-chap3 (2)队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3．4队列3.4.1队列的概念3.4.2循环队列——队列的顺序存储和实现3.4.3队列的链式存储和实现3.4.1队列的概念一、什么是队列队列是限定仅能在表头进行删除、表尾进行插入的线性表。（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除4）元素按a1,a2,a3,...,an顺序入队，第一个入队的元素为a1，最后一个入队的元素是an，第一个出队的元素为a1；说明：1）表尾称作队尾，表头称为队头；2）a1为队头元素，an为队尾元素；3）在表尾插入元素操作，称为入队操作；在表头删除元素的操作，称为出队操作；5）队列具有先进先出的特点，又称为先进先出表（FIF

2、O表）。入队列a1a2a3an队头队尾出队列自测题1一个队列的入列序列是1,2,3,4，则队列的输出序列是（）。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1二、队列的抽象数据类型的定义InitQueue(&Q)结果:构造一个空队列Q。数据对象:D={ai

3、ai∈ElemSet，i=1,2,…,n}数据关系:R1={}；约定a1为队头元素，an为队尾元素。基本操作:ADTQueue{}ADTQueueDestroyQueue(&Q)结果:销毁队列Q。条件:队列Q已存在。功能：若队列不空，则删除Q的队头元素，用e返回其值，并返回O

4、K；否则，返回ERROR。队列的基本操作：1）初始化操作InitQueue(&Q)功能：构造一个空队列Q；2）销毁操作DestroyQueue(&Q)功能：销毁已存在队列Q；3）置空操作ClearQueue(&Q)功能：将队列Q置为空队列；4）判空操作QueueEmpty(Q)功能：若队列Q为空，则返回True；否则，返回False；5）取队头元素操作GetHead(Q,&e)功能：取队头元素，并用e返回；6）入队操作EnQueue(&Q,e)功能：将元素e插入Q的队尾；7）出队操作DeQueue(&Q,&e)在队列的顺序存储结构中，用一组连续存储单元依次存储从队头到队尾

5、的数据元素.此外，还需附加两个变量：3.4.3队列的顺序存储和实现一、队列的顺序存储结构队头指针front：指示队头元素的位置；队尾指针rear：指示队尾元素的位置。空队列Q.rearQ.front012345Q.rearQ.frontJ1J2J3J1,J2和J3相继入队Q.rearQ.frontJ3J1和J2相继出队J4、J5和J6相继入队之后,J3和J4出队Q.rearQ.frontJ5J6问题：如何解决“假上溢”现象?将顺序队列设想为首尾相连的环状空间。当Q.rear值超出队列空间的最大位置时，令Q.rear=0，使队列空间能“循环”使用。J6J4J5Q.rearQ

6、.front312405543210Q.rearQ.frontJ6J5J41、循环队列循环使用空间的队列。循环队列操作示意图2）在（a)状态下，J6、J7、J8依次入队，队列如图（c），这时也有Q.front=Q.rear。540312J5Q.frontQ.rearJ4J3(a)Q.rear540312Q.frontJ5J6J7J8J3J4(c)队满2、队空、队满的判别1）在（a）状态下，J3、J4、J5依次出队，队列状态如图（b），这时有Q.front=Q.rear;仅凭Q.front=Q.rear是否成立，无法判断队列是空还是满。Q.frontQ.rear540312

7、J3J4J5(b)队空2）少用一个存储单元，即当队列达到图(d)所示状态时，就认为队列已满，这时的条件是Q.front=(Q.rear+1)%6。如何判断循环队列队空、队满？？Q.rear540312Q.frontJ5J6J7J3J4（d）两种方法：1）另设一个标志位以区分队空、队满。自测题2循环队列的优点是什么，如何判断“空”和“满”。【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中，我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满：即当队尾指针加1（取模）等于队头指针时，表示队列满。也有

8、使用全部单元，通过设标记来解决“空”和“满”的。3、循环队列的类型定义#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//初始化时动态分配存储空间的基址intfront;//队头指针，指向队头元素（队列不空）intrear;//队尾指针，指向队尾元素的下一个位置（队列不空）}SqQueue;只是称为指针，实现时不一定用指针变量设Q为SqQueue类型的变量，用于存储队列。设为队列Q分配空间大小为MAXQSIZE=6。初始建队时，令Q.front=Q.rear=0。