循环队列的基本运算实现课件.ppt

上传人(卖家):晟晟文业 文档编号:4231596 上传时间:2022-11-21 格式:PPT 页数:12 大小:97.56KB
下载 相关 举报
循环队列的基本运算实现课件.ppt_第1页
第1页 / 共12页
循环队列的基本运算实现课件.ppt_第2页
第2页 / 共12页
循环队列的基本运算实现课件.ppt_第3页
第3页 / 共12页
循环队列的基本运算实现课件.ppt_第4页
第4页 / 共12页
循环队列的基本运算实现课件.ppt_第5页
第5页 / 共12页
点击查看更多>>
资源描述

1、也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为,允许插入的一端称为。v队列的修改是依先进先出的原则进行的。队列的基本运算队列的基本运算1初始化队列初始化队列 InitQueue(&Q)将队列Q设置成一个空队列。2入队列入队列 EnQueue(&Q,X)将元素X插入到队尾中,也称“进队”,“插入”。3出队列出队列 DeQueue(&Q,&e)将队列Q的队头元素删除,并用e返回其值,也称“退队”、“删除”。4取队头元素取队头元素 GetHead(Q,&e)得到队列Q的队头元素之值,并用e返回其值。5判队空判队空 QueueEmpty(Q)判断队列Q是否

2、为空,若为空返回1,否则返回0。#define MAXSIZE 100typedef struct ElemType dataMAXSIZE;int front;int rear;SqQueue;顺序队列的操作演示顺序队列的操作演示flash在非空队列里,头指针始终指向队头元素,而尾指针在非空队列里,头指针始终指向队头元素,而尾指针始终指向队尾元素的下一位置。始终指向队尾元素的下一位置。v 为充分利用向量空间,克服上述假上为充分利用向量空间,克服上述假上溢现象,可以将向量空间想象为一个首溢现象,可以将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向尾相接的圆环,并称这种向量为循环向量,存

3、储在其中的队列称为量,存储在其中的队列称为循环队列循环队列(Circular Queue)。v循环队列中进行出队、入队操作时,头循环队列中进行出队、入队操作时,头尾指针仍要加尾指针仍要加1,朝前移动。只不过当,朝前移动。只不过当头尾指针指向向量上界(头尾指针指向向量上界(QueueSize-1)时,其加时,其加1操作的结果是指向向量的下操作的结果是指向向量的下界界0。循环队列的操作演示循环队列的操作演示flash012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空:fr

4、ont=rear队满:front=rear队空、队满无法判断:1.另外设一个标志以区别2.少用一个元素空间:队空:front=rear 队满:(rear+1)%M=front队空:Q.front=Q.rear队满:Q.front=(Q.rear+1)%maxSize入队:Q.rear=(Q.rear+1)%maxSize出队:Q.front=(front+1)%maxSize;求队长:(Q.rear-Q.front+maxSize)%maxSize循环队列循环队列1)进队列算法)进队列算法(1)检查队列是否已满,若队满,则溢出错误;(2)将新元素赋给队尾指针所指单元;(3)将队尾指针后移一个位

5、置(即加1)。2)出队列算法出队列算法(1)检查队列是否为空,若队空,则下溢错误;(2)取队首元素的值。(3)将队首指针后移一个位置(即加1);循环队列的基本运算实现循环队列的基本运算实现ch3_ull*qq.frontq.rear非空队列q.frontq.rearnull空队列*qv链队列示意图 和顺序队列类似,我们也是将这两个指针封装在一起,将链队列的类型LinkQueue定义为一个结构类型:typedef struct queuenode ElemType data;struct queuenode*next;QueueNode;typedef struct QueueNode *fro

6、nt;QueueNode *rear;LinkQueue;链队列的ch3_lqueue.cCPU资源的竞争问题。主机与外部设备之间速度不匹配的问题。服务、排队问题线性表、栈与队的异同点线性表、栈与队的异同点相同点:相同点:逻辑结构相同,都是线性的;都可以用顺逻辑结构相同,都是线性的;都可以用顺序存储或链表存储;栈和队列是两种特殊的线性序存储或链表存储;栈和队列是两种特殊的线性表,即表,即受限的线性表受限的线性表(只是对插入、删除运算加(只是对插入、删除运算加以限制)。以限制)。不同点:不同点:运算规则不同,线性表为随机存取,而栈是只运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入和删除运算,因而是后进先允许在一端进行插入和删除运算,因而是后进先出表出表LIFOLIFO;队列是只允许在一端进行插入、另一;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表端进行删除运算,因而是先进先出表FIFOFIFO。用途不同,线性表比较通用;堆栈用于函数调用途不同,线性表比较通用;堆栈用于函数调用、递归和简化设计等;队列用于离散事件模拟、用、递归和简化设计等;队列用于离散事件模拟、多道作业处理和简化设计等。多道作业处理和简化设计等。

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(循环队列的基本运算实现课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|