队列的定义表示实现精选PPT.ppt

《队列的定义表示实现精选PPT.ppt》由会员分享，可在线阅读，更多相关《队列的定义表示实现精选PPT.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、队列的定义表示实现第1页，此课件共30页哦3.2 3.2 队列队列只能在表的一端进行插入运算，在表的只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。另一端进行删除运算的线性表。1.1.1.1.定义定义一、概念：一、概念：例如：队列例如：队列 Q=(a1 ,a2 ,a3 ,，an)在队尾插入元素称为在队尾插入元素称为入队入队入队入队；在队首删除元素称为在队首删除元素称为出队出队出队出队。队头元素队头元素队尾元素队尾元素允许插入的一端为队尾，允许删除的一端允许插入的一端为队尾，允许删除的一端为队头。为队头。2第2页，此课件共30页哦与线性表相同，仍为一对一关系。与线性表相同，仍为一对

2、一关系。顺序队顺序队或或链队链队，以，以循环顺序队循环顺序队更常见。更常见。只能在只能在队首队首和和队尾队尾运算，且访问结点时依运算，且访问结点时依照照先进先出（先进先出（FIFOFIFO）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现操作，具体实现依顺序队或链队的不同而不同。依顺序队或链队的不同而不同。3.存储结构：存储结构：4.运算规则：运算规则：5.实现方式实现方式：2.2.逻辑结构：逻辑结构：3第3页，此课件共30页哦二、队列的抽象数据类型定义二、队列的抽象数据类型定义ADT Queue 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0

3、 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 约定a1 端为队列头，an 端为队列尾。基本操作：基本操作：ADT Stack4第4页，此课件共30页哦（1 1）初始化队列）初始化队列 InitQueue(&Q)InitQueue(&Q)（2 2）入队）入队 EnQueue(&Q,e)EnQueue(&Q,e)（3 3）出队）出队 DeQueue(&Q,&e)DeQueue(&Q,&e)（4 4）获取队头元素内容）获取队头元素内容 GetHead(Q,&e)GetHead(Q,&e)（5 5）判断队列是否为空）判断队列是否为空 QueueEmpty(Q)QueueEmpty(Q)基

4、本操作基本操作:建队列、判断队列是否为空、入队、出队、建队列、判断队列是否为空、入队、出队、读队头元素值，等等。读队头元素值，等等。5第5页，此课件共30页哦链链队列队列类型定义：类型定义：typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;结点结点类型定义：类型定义：typedef struct QNode QElemType data;/元素 struct QNode *next;/指向下一结点的指针 Qnode,*QueuePtr;关于整个链队的总关于整个链队的总体描述体描述链队中任一结链队中任一结点的结构点

5、的结构三、队列的表示和实现三、队列的表示和实现1.1.单链队列单链队列/-队列的链式存储结构队列的链式存储结构-6第6页，此课件共30页哦a1anQ.frontQ.rearQ.frontQ.rear空队列空队列为了操作方便，添加一个头结点，令头指针指向头结点。为了操作方便，添加一个头结点，令头指针指向头结点。Q.front=Q.rear7第7页，此课件共30页哦 Status InitQueue(LinkQueue&Q)/构造一个空队列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失

6、败 Q.front-next=NULL;return OK;/-基本操作的算法描述基本操作的算法描述-建队操作建队操作构造空队列构造空队列构造空队列构造空队列Q Q Q Q8第8页，此课件共30页哦Q(队尾队尾)(队首队首)fronta1a2a3rearp链队会满吗？链队会满吗？一般不会，因为删除时有一般不会，因为删除时有freefree动作。除非动作。除非内存不足！内存不足！入队（尾部插入）：入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：出队（头部删除）：p=front-next;front-next=p-next;free(p);Se链队列的入队和出队操作链队列

7、的入队和出队操作9第9页，此课件共30页哦 Status EnQueue(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败 p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;10第10页，此课件共30页哦 Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR if(Q.fron

8、t=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;11第11页，此课件共30页哦队列的顺序存储结构如下图所示：队列的顺序存储结构如下图所示：附设两个指针附设两个指针front和和rear分别指示队列头元素的位置和队分别指示队列头元素的位置和队列尾元素的下一个位置列尾元素的下一个位置约定：约定：初始化建空队列时，令初始化建空队列时，令front=rear=0front=rear=0；2.2.顺序队列顺序队列12第

9、12页，此课件共30页哦（2 2）空队列的特征？空队列的特征？约定：约定：front=rearfront=rear问题：（问题：（1 1）怎样实现入队和出队操作？）怎样实现入队和出队操作？核心语句如下：核心语句如下：入队入队(尾部插入尾部插入)：Qrear=e;rear+;Qrear=e;rear+;出队出队(头部删除头部删除)：e=Qfront;front+;e=Qfront;front+;（3 3）队列会满吗？）队列会满吗？极易装满！极易装满！因为数组通常有长度限制，而其前因为数组通常有长度限制，而其前端空间无法释放。有假溢出现象。端空间无法释放。有假溢出现象。如图：如图：13第13页，此

10、课件共30页哦解决假溢出的途径解决假溢出的途径采用循环队列采用循环队列在顺序队中，当尾指针已经到了数组的上界，不在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但实际上数组中还有空位置，能再有入队操作，但实际上数组中还有空位置，这就叫这就叫“假溢出假溢出”。讨论：什么叫讨论：什么叫“假溢出假溢出”？如何解决？如何解决？将存储队列元素的一维数组首尾相接，形将存储队列元素的一维数组首尾相接，形成一个环状。成一个环状。14第14页，此课件共30页哦a3a2a10123N-1rearfront循环队列（臆造）循环队列（臆造）顺序队列顺序队列a3a2a1frontrear 0 1 2 3 .N

11、-115第15页，此课件共30页哦新问题：新问题：在循环队列中，队空时在循环队列中，队空时 front=rear；队满时也会；队满时也会有有 front=rear；判决条件将出现；判决条件将出现二义性二义性！解决方案有二：解决方案有二：使用一个计数器记录队列中元素个数（即队列长度）；使用一个计数器记录队列中元素个数（即队列长度）；人为浪费一个单元，约定：队列头指针在队列尾指针的人为浪费一个单元，约定：队列头指针在队列尾指针的 下一位下一位置上作为队列呈置上作为队列呈“满满”状态的标志。则队满特征可改为状态的标志。则队满特征可改为front=(rear+1)%N front=(rear+1)%N

12、（N N为最大队列长度）为最大队列长度）；实际中常选用方案实际中常选用方案2 2（人为人为浪费一个单元）浪费一个单元）16第16页，此课件共30页哦建队核心语句：Q.base=(QElemType*)malloc(sizeof(QElemType）*MAXQSIZE);/分配空间关于整个顺序队关于整个顺序队的总体描述的总体描述#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base;/队列的基址 int front;/队头指针 int rear;/队尾指针 SqQueue/-循环队列循环队列队列的顺序存储结构队列的顺序存储结构-17

13、第17页，此课件共30页哦队空条件队空条件:front=rear (初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1+1)%N (N=MAXQSIZE)队列长度：队列长度：L=（Nrearfront）%N J2 J3J1 J4 J5frontrear问问3 3：在具有在具有N N个单元的循环队个单元的循环队列中，队满时共有多少个元素列中，队满时共有多少个元素？N-1个个6 问问1 1：左图中队列左图中队列MAXQSIZE N=MAXQSIZE N=？问问2 2：左图中队列左图中队列长度长度L=L=？518第18页，此课件共30页哦例例1.1.一循环队列如下

14、图所示，若先删除一循环队列如下图所示，若先删除4 4个元素，接着再个元素，接着再插入插入4 4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置?J2 J3J1 J4 J5front=1rear=0解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=1front=1和和rear=0rear=0。删除删除4 4个元素后个元素后front=5front=5；再插入再插入4 4个元素后，个元素后，rear=(0+4)%6=4rear=(0+4)%6=4 front=5J6 J5J7J8 J9rear=4rear=0front=

15、519第19页，此课件共30页哦例例2.Q02.Q01010是一个循环队列，初始状态为是一个循环队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h d,e,b,g,h 入队入队d,e d,e 出队出队i,j,k,l,m i,j,k,l,m 入队入队b b 出队出队n,o,p n,o,p 入队入队20第20页，此课件共30页哦讨论：循环队列的基本操作如何实现？讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基

16、本操作为例以建队、入队和出队三种基本操作为例1）初始化一个空队列）初始化一个空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间算法操作：为队列分配基本容量空间 设置队列为空队列，其特征即：设置队列为空队列，其特征即：front=rear=0（也可为任意单元，如（也可为任意单元，如1，2，）21第21页，此课件共30页哦建队的完整算法：建队的完整算法：Status InitQueue(SqQueue&Q)/初始化空循环队列 Q Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType）);/分配空间 if(!Q.bas

17、e)exit(OVERFLOW);Q.front=Q.rear=0;/置空队列 return OK;/InitQueue;/InitQueue;22第22页，此课件共30页哦算法说明：向循环队列的算法说明：向循环队列的队尾插入队尾插入一个元素一个元素分分 析析：(1)插入前应当先判断队列是否满？插入前应当先判断队列是否满？if(Q.rear+1)%MAXQSIZE)=Q.front)return ERROR;(2）插入动作）插入动作 Q.base Q.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;2）入队操作入队操作队列尺寸队列尺寸先存放元素，后移先存放元素，后移动队尾指

18、针动队尾指针23第23页，此课件共30页哦Status EnQueue(SqQueue&Q,QElemType e)/向循环队列 q 的队尾加入一个元素 e if(Q.rear+1)%MAXQSIZE=Q.front )return ERROR;/队满则上溢 Q.base Q.rear =e;/新元素e入队 Q.rear=(Q.rear+1)%MAXQSIZE;/指针后移 return OK;/EnQueue;入队操作完整算法入队操作完整算法24第24页，此课件共30页哦3 3）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删除队头元素，返回其值 e 分分 析：析：（1）在删除前

19、应当判断队列是否空？在删除前应当判断队列是否空？if(Q.front=Q.rear)return ERROR;（2）删除动作分析：）删除动作分析：前面约定指针前面约定指针frontfront指向队首元素的位置，故指向队首元素的位置，故：e=Q.base Q.front ;Q.front=(Q.front+1)%MAXQSIZE;队列尺寸队列尺寸先取出元素，后先取出元素，后移动队头指针移动队头指针25第25页，此课件共30页哦Status DeQueue(SqQueue&Q,QElemType&e)/若队列不空，删除循环队列q的队头元素，/由 e 返回其值，并返回OK if(Q.front=Q.

20、rear)return ERROR;/队列空 e=Q.base Q.front ;Q.front=(Q.front+1)%MAXQSIZE;return OK;/DeQueue出队操作完整算法出队操作完整算法26第26页，此课件共30页哦例例3：编写一个算法，利用栈和队列的基本运算将指定：编写一个算法，利用栈和队列的基本运算将指定队列中的内容进行逆转。队列中的内容进行逆转。分析：假设为循环队列。建立一个临时栈分析：假设为循环队列。建立一个临时栈temps，将指定队，将指定队列列Q中的所有元素出队并入栈到中的所有元素出队并入栈到temps中，这样队列中，这样队列Q为空，为空，再将再将temps中

21、的所有元素出栈并入队到中的所有元素出栈并入队到Q队中，这样队中，这样Q队列队列中的内容发生了逆转。算法如下：中的内容发生了逆转。算法如下：void reverse(SqQueue&Q)QElemType x;SqStack temps;InitStack(temps);27第27页，此课件共30页哦 while(!QueueEmpty(Q)/初始化初始化temps栈栈 DeQueue(Q,x);Push(temps,x);While(!StackEmpty(temps)Pop(temps,x);EnQueue(Q,x);28第28页，此课件共30页哦本章小结本章小结线性表、栈、队的异同点：线性

22、表、栈、队的异同点：相相同同点点：逻逻辑辑结结构构相相同同，都都是是线线性性的的；都都可可以以用用顺顺序序存存储储或或链链式式存存储储；栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，即即受受限限的的线线性性表表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。运算规则不同：运算规则不同：线性表可任意存取；线性表可任意存取；栈是后进先出表栈是后进先出表LIFOLIFO；队列是先进先出表队列是先进先出表FIFOFIFO。用途不同，用途不同，线性表比较通用；堆栈用于函数调线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、用、递归和简化设计等；队列用于离散事件模拟、OSOS作业调度和简化设计等。作业调度和简化设计等。不同点：不同点：不同点：不同点：29第29页，此课件共30页哦第第3章作业章作业3.3 3.4 3.6 3.10 3.12 3.3 3.4 3.6 3.10 3.12 3.3 3.4 3.6 3.10 3.12 3.3 3.4 3.6 3.10 3.12 3.16 3.17 3.16 3.17 3.16 3.17 3.16 3.17 3.29 3.29 3.323.3230第30页，此课件共30页哦