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

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

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

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

3、关系：R1|ai-1,aiD,i=2,.,n 约定a1 端为队列头，an 端为队列尾。基本操作：基本操作：ADT Stack4本讲稿第四页，共三十页（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本讲稿第五页，共三十页链链队列队列类型定义：类型定义：typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;结点结点类型定义：类型定义：typedef struct QNode QElemType data;/元素 struct QNode *next;/指向下一结点的指针 Qnode,*QueuePtr;关于整个链队的总关于整个链队的总体描述体描述链队中任一结链队中任一结点的结构点的结构三、队列的表

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

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

7、第九页，共三十页 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本讲稿第十页，共三十页 Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR if(Q.front=Q.rear)return

8、 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本讲稿第十一页，共三十页队列的顺序存储结构如下图所示：队列的顺序存储结构如下图所示：附设两个指针附设两个指针front和和rear分别指示队列头元素的位置和分别指示队列头元素的位置和队列尾元素的下一个位置队列尾元素的下一个位置约定：约定：初始化建空队列时，令初始化建空队列时，令front=rear=0front=rear=0；2.2.顺序队列顺序队列12本讲稿第十二页，共三十页（2 2）

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

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

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

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

13、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本讲稿第十八页，共三十页例例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=519本讲稿第十九页，共三十页例例2.Q02.

15、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本讲稿第二十页，共三十页讨论：循环队列的基本操作如何实现？讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例以建队、入队和出队三种基本操作为例1）初

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

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

18、us 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本讲稿第二十四页，共三十页3 3）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删除队头元素，返回其值 e 分分 析：析：（1）在删除前应当判断队列是否空？在删除前应当判断队列是否空？i

19、f(Q.front=Q.rear)return ERROR;（2）删除动作分析：）删除动作分析：前面约定指针前面约定指针frontfront指向队首元素的位置，故指向队首元素的位置，故：e=Q.base Q.front ;Q.front=(Q.front+1)%MAXQSIZE;队列尺寸队列尺寸先取出元素，后移先取出元素，后移动队头指针动队头指针25本讲稿第二十五页，共三十页Status DeQueue(SqQueue&Q,QElemType&e)/若队列不空，删除循环队列q的队头元素，/由 e 返回其值，并返回OK if(Q.front=Q.rear)return ERROR;/队列空 e=

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

21、中，这样队中，这样Q队列中的队列中的内容发生了逆转。算法如下：内容发生了逆转。算法如下：void reverse(SqQueue&Q)QElemType x;SqStack temps;InitStack(temps);27本讲稿第二十七页，共三十页 while(!QueueEmpty(Q)/初始化初始化temps栈栈 DeQueue(Q,x);Push(temps,x);While(!StackEmpty(temps)Pop(temps,x);EnQueue(Q,x);28本讲稿第二十八页，共三十页本章小结本章小结线性表、栈、队的异同点：线性表、栈、队的异同点：相相相相同同同同点点点点：逻逻

22、辑辑结结构构相相同同，都都是是线线性性的的；都都可可以以用用顺顺序序存存储储或或链链式式存存储储；栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，即即受受限限的的线线性性表表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。运算规则不同：运算规则不同：线性表可任意存取；线性表可任意存取；栈是后进先出表栈是后进先出表LIFOLIFO；队列是先进先出表队列是先进先出表FIFOFIFO。用途不同，用途不同，线性表比较通用；堆栈用于函数线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模调用、递归和简化设计等；队列用于离散事件模拟、拟、OSOS作业调度和简化设计等。作业调度和简化设计等。不同点：不同点：不同点：不同点：29本讲稿第二十九页，共三十页第第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.29 3.29 3.323.3230本讲稿第三十页，共三十页