数据结构课件队列.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构课件队列.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 队列
- 资源描述:
-
1、n队列的应用队列的应用3.4 3.4 队列队列3.4.1 3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义 也是一种运算受限的线性表。它也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为删除。允许删除的一端称为,允许,允许插入的一端称为插入的一端称为。(a0,a1,.,ai-1,ai,ai+1,an-1 )插入插入删除删除例如:排队购物。操作系统中的作业排队。先例如:排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦进入队列的成员总是先离开队列。因此队列亦称作称作先进先出先进先出(
2、First In First Out)(First In First Out)的线性表,的线性表,简称简称FIFOFIFO表。表。a a0 0 a a1 1 a a2 2 a an-1n-1rearrear队队头头队队尾尾frontfront队队 列列 的的 示示 意意 图图队列的特点队列的特点先进先出先进先出说明:说明:第一个入队的元素在队头,第一个入队的元素在队头,最后一个入队的元素在队尾,最后一个入队的元素在队尾,第一个出队的元素为队头元素,第一个出队的元素为队头元素,最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素队列的抽象数据定义见书59队列的基本运算队列的基本运算 队列可定
3、义如下五种基本运算:队列可定义如下五种基本运算: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是否为空,若为空返回1,否则返回0。3.4.2 3.4.2 非循环队列和循环队列非循环队列和循环队列 分配一块连续的存储区域来存放队列里
4、的元素。由分配一块连续的存储区域来存放队列里的元素。由于队列的队头和队尾的位置是变化的,因而要设两个于队列的队头和队尾的位置是变化的,因而要设两个指针和分别指示队头和队尾元素在队列中的位置。指针和分别指示队头和队尾元素在队列中的位置。它们的初始值在队列初始化时均应置为。入队时它们的初始值在队列初始化时均应置为。入队时将新元素插入所指的位置,然后尾指针加。出队将新元素插入所指的位置,然后尾指针加。出队时,删去所指的元素,然后头指针加并返回被删时,删去所指的元素,然后头指针加并返回被删元素。由此可见,元素。由此可见,当头尾指针相等时队列为空当头尾指针相等时队列为空。在非空队列里,头指针始终指向队头
5、元素,而尾指在非空队列里,头指针始终指向队头元素,而尾指针始终指向队尾元素的下一位置。针始终指向队尾元素的下一位置。0 1 2 3FrontrearabcFront rear(a)(a)队列初始为空(队列初始为空(b b)A,B,CA,B,C入队入队 b c front rear front rear(c)a出队出队 (d)b,c出队,队为空出队,队为空#define MAXQSIZE 100typedef struct ElemType dataMAXQSIZE;int front;/*队头位置队头位置*/int rear;/*队尾位置队尾位置*/SqQueue;队列的顺序存储结构定义:队列
6、的顺序存储结构定义:SqQueue QQ-front 存放即将要被删除的元素的下标。存放即将要被删除的元素的下标。Q-rear 存放即将要被插入的元素(目前不在队列中)存放即将要被插入的元素(目前不在队列中)的下标。的下标。Q-data Q-front和和Q-data Q-rearn初始化:初始化:Q.front=Q.rear=0n队空:队空:Q.front=Q.rearn队满:队满:Q.rear=maxsize(假溢出)(假溢出)n求队长:求队长:Q.rear-Q.frontn 入队:新元素按入队:新元素按 rear 指示位置加入,再指示位置加入,再将队尾指针加一将队尾指针加一,即,即 re
7、ar=rear+1n 出队:将出队:将front指示的元素取出,再将队头指示的元素取出,再将队头指针加一,即指针加一,即front=front+1非循环队列非循环队列注意:注意:入队应考虑队满;出队应考虑队空。入队应考虑队满;出队应考虑队空。为充分利用向量空间,克服上述假上溢现象,可以为充分利用向量空间,克服上述假上溢现象,可以将向量空间想象为一个首尾相接的圆环,并称这种将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量,存储在其中的队列称为向量为循环向量,存储在其中的队列称为循环队列循环队列(Circular Queue)。在循环队列中进行出队、入。在循环队列中进行出队、入队操作时,
8、头尾指针仍要加队操作时,头尾指针仍要加1,朝前移动。只不过,朝前移动。只不过当头尾指针指向向量上界(当头尾指针指向向量上界(QueueSize-1)时,其)时,其加加1操作的结果是指向向量的下界操作的结果是指向向量的下界0。显然,因为循环队列元素的显然,因为循环队列元素的空间可以被利用,除非向量空间空间可以被利用,除非向量空间真的被队列元素全部占用,否则真的被队列元素全部占用,否则不会上溢。因此,除一些简单的不会上溢。因此,除一些简单的应用外,真正实用的顺序队列是应用外,真正实用的顺序队列是循环队列(环形队列)。循环队列(环形队列)。由于入队时尾指针向前追赶头指针,出队由于入队时尾指针向前追赶
9、头指针,出队时头指针向前追赶尾指针,故队空和队满时时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,我们无法通过头尾指针均相等。因此,我们无法通过Q-f=Q-r来判断队列来判断队列“空空”还是还是“满满”。frontfront5 54 04 03 13 12 2J6J6J7J7J8J8J4J4J5J5rearrear012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态初始状态J4,J5,J6出队出队J7,J8,J9入队入队队空:队空:front=rear队满:队满:front=rear解决方案:解决方案
10、:1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间:队空:队空:Q-front=Q-rear 队满:队满:(Q-rear+1)%M=Q-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循环队列循环队列【例】【例】设循环队列的容量为设循环队列的容量为4040(序号从(序号从0 0到
11、到3939),现经过一系列的入队和出队运算后,有),现经过一系列的入队和出队运算后,有 front=11 front=11,rear=19;rear=19;front=19 front=19,rear=11rear=11;问在这两种情况下,;问在这两种情况下,循环队列中各有元素多少个?循环队列中各有元素多少个?答:用队列长度计算公式:答:用队列长度计算公式:(Q.rear-Q.front+maxSize)%maxSize L=(401911)%40=8 L=(401119)%40=32 循环队列的基本运算实现循环队列的基本运算实现 1 1、进队列、进队列 1)进队列算法)进队列算法 2)进队列
展开阅读全文