《第4周栈和队列第3讲-队列的定义和顺序队.pdf》由会员分享，可在线阅读，更多相关《第4周栈和队列第3讲-队列的定义和顺序队.pdf（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、队列简称队列简称队队，它也是一种运算受限的，它也是一种运算受限的线性表。线性表。 3.2.1 队列的定义队列的定义 队列只能队列只能选取一个端点进行插入操作，另一个端点进行选取一个端点进行插入操作，另一个端点进行 删除操作删除操作 端点端点1端点端点2 线线 性性 表表 把把进行插入的一端称做进行插入的一端称做队尾队尾（rear）。）。 进行进行删除的一端称做删除的一端称做队首队首或或队头队头（front）。）。 向向队列中插入新元素称为队列中插入新元素称为进队进队或或入队入队，新元素进队后就成为新，新元素进队后就成为新 的队尾的队尾元素。元素。 从从队列中删除元素称为队列中删除元素称为出队出
2、队或或离队离队，元素出队后，其后继元素，元素出队后，其后继元素 就成为队首元素。就成为队首元素。 队尾队尾队头队头 队列示意图队列示意图 出队出队 进队进队 队列的几个概念队列的几个概念 队列队列的主要特点是先进先出，所以又把队列称为的主要特点是先进先出，所以又把队列称为先进先出表先进先出表。 假如假如5个人个人 过独木桥过独木桥 只能按上桥的只能按上桥的 次序过桥次序过桥 这里独木桥就是一个队列这里独木桥就是一个队列 例如：例如： 队列的基本运算如下：队列的基本运算如下： InitQueue( 顺序队类型顺序队类型SqQueue定义如下：定义如下： 因为队列两端因为队列两端都在变化，所以需要
3、两个指针来标识队列的都在变化，所以需要两个指针来标识队列的 状态。状态。 队列队列 (a1, a2, ,ai, , an ) 映射映射 a1anf MaxSize-1 ff+1r data front 顺序顺序队队的示意图的示意图 逻辑结构逻辑结构 存储结构存储结构 0 r rear 例如：例如：MaxSize=5 4 3 2 1 0 rear （a）空队）空队（b）a进队进队 （c）b、c、 d、e进队进队 （d）全部出队）全部出队 总总 结结 约定约定rear总是指向队尾元素总是指向队尾元素 元素进队，元素进队，rear增增1 约定约定front指向当前队中队头元素的前一位置指向当前队中队
4、头元素的前一位置 元素出队，元素出队，front增增1 当当rear=MaxSize- -1时不能再进队时不能再进队 front 4 3 2 1 a0 front rear e4 d3 c2 b1 a0 front rear4 3 2 1 0 front rear 顺序队顺序队的的4要素要素（初始时（初始时front=rear=- -1）：）： 队队空条件空条件：front = rear 队队满条件满条件：rear = MaxSize1 元素元素e进队：进队：rear+; datarear=e; 元素元素e出队：出队：front+; e=datafront; 队列的各种状态队列的各种状态 4
5、3 2 1 0 rear front 4 3 2 1 a0 front rear e4 d3 c2 b1 a0 front rear4 3 2 1 0 front rear （a）空队）空队（b）a进队进队 （c）b、c、d、 e进队进队 （d）全部出队）全部出队 1、 顺序顺序队中队中实现队列的基本运算实现队列的基本运算 （1）初始化队列）初始化队列InitQueue(q) 构造构造一个空队列一个空队列q。将。将front和和rear指针均设置成初始状态即指针均设置成初始状态即- -1值。值。 void InitQueue(SqQueue * q-front=q-rear=-1; 4 3 2
6、 1 0 rear front （2）销毁队列）销毁队列DestroyQueue(q) 释放队列释放队列q占用的存储空间。占用的存储空间。 void DestroyQueue(SqQueue * （3）判断队列是否为空）判断队列是否为空QueueEmpty(q) 若若队列队列q满足满足q- -front=q- -rear条件，则返回条件，则返回true；否则返回；否则返回false。 bool QueueEmpty(SqQueue *q) return(q-front=q-rear); （4）进队列）进队列enQueue(q,e) 若队列不满，将若队列不满，将队尾指针队尾指针rear循环增循环
7、增1，然后将元素添加到该位置。，然后将元素添加到该位置。 bool enQueue(SqQueue * q-rear+; q-dataq-rear=e; return true; 4 3 2 1 a0 front rear 4 3 2 1 0 rear front 空队：空队： 元素元素a进队进队 （5）出队列）出队列deQueue(q,e) 若若队列队列q不空，不空，将队首指针将队首指针front循环增循环增1，并将该位置的元素值赋给，并将该位置的元素值赋给e。 bool deQueue(SqQueue * q-front+; e=q-dataq-front; return true; 4
8、d3 c2 b1 0 front rear出队一出队一个元素个元素b 4 d3 c2 1 0 front rear 2、环形、环形队列（或循环队列）中实现队列的基本运算队列（或循环队列）中实现队列的基本运算 c4 b3 a2 1 0 front rear 这这是因为采用是因为采用rear=MaxSize- -1作为队满条件的缺陷作为队满条件的缺陷。当当 队满条件为真时队满条件为真时，队中可能还有若干空位置队中可能还有若干空位置。 这种这种溢出并不是真正的溢出并不是真正的溢出溢出，称为称为假假溢出溢出。 还有两个位置，还有两个位置， 为何不能进队？为何不能进队？ 把把数组的前端和后端连接起来数组
9、的前端和后端连接起来，形成一个环形的顺序表形成一个环形的顺序表，即即 把存储队列元素的表从逻辑上看成一个环把存储队列元素的表从逻辑上看成一个环，称为称为环形队列或循环环形队列或循环 队列队列。 原来如此，简原来如此，简 单！单！ c4 b3 a2 1 0 front rear 0 1 2 3 4 front a b c rear 当当rear = 4时，下一步时，下一步 到位置到位置0，可以进队，可以进队 解决方案解决方案 例 如 例 如 当当rear = 4时时，不能，不能 再进队再进队 0 1 2 3 4 front a b c d rear 实际上内存地址一定是连续的，不可能是环形的，这
10、里是实际上内存地址一定是连续的，不可能是环形的，这里是 通过通过逻辑方式逻辑方式实现环形队列，也就是将实现环形队列，也就是将rear+和和front+改为：改为： rear=(rear+1)%MaxSize front=(front+1)%MaxSize 环形队列：环形队列： 0 1 2 3 4 front rear （a）空队）空队 0 1 2 3 4 front a b c rear （b）a、b、c进队进队 0 1 2 3 4 front b c rear （c）出队一次）出队一次 0 1 2 3 4 front rear （d）出队）出队2次次 现在约定现在约定rear=front为队
11、空，以下两种情况都满足该条件：为队空，以下两种情况都满足该条件： 0 1 2 3 4 front rear 0 1 2 3 4 front rear 初始状态初始状态进队的所有元素均出队进队的所有元素均出队 那么如何那么如何设置队满的条件设置队满的条件呢？呢？ 让让rear=front为为队空条件队空条件，并，并约定约定 (rear+1)%MaxSize=front 为为队满条件队满条件。 进进队一个元素时队一个元素时 到达队头到达队头，就，就认为认为 队满队满了了。 这样这样做会少放一做会少放一 个元素，牺牲一个个元素，牺牲一个 元素元素没关系没关系的。的。 队队空条件空条件：front =
12、 rear 队队满条件满条件：(rear+1)%MaxSize = front 进进队队e操作操作：rear=(rear+1)%MaxSize; 将将e放在放在rear处处 出出队操作队操作：front=(front+1)%MaxSize; 取出取出front处元素处元素e; 环形队列环形队列的的4要素要素： 在在环形队列中环形队列中，实现队列的实现队列的基本运算基本运算算法与非环形队列类似算法与非环形队列类似，只只 是改为上述是改为上述4要素即可要素即可。 【例例3- -5】对于环形队列来说对于环形队列来说，如果知道队头指针和队列如果知道队头指针和队列 中元素个数中元素个数，则可以计算出队尾
13、指针则可以计算出队尾指针。也就是说也就是说，可以用队列可以用队列 中元素个数代替队尾指针中元素个数代替队尾指针。 设计设计出这种环形队列的初始化出这种环形队列的初始化、入队入队、出队和判空算法出队和判空算法。 count=(3- -0)=3 MaxSize5 0 1 2 3 4 front rear a b c 0 1 2 3 4 front rear a b c count=(1- -3)=- -2 count=rear- -front ? 已知已知front、rear，求队中元素个数，求队中元素个数count = ? count=(1- -3+MaxSize)=3 count=(3- -0
14、+MaxSize)=8 count=(3- -0+MaxSize)%MaxSize=3 count=(1- -3+MaxSize)%MaxSize=3 已知已知front、rear，求队中元素，求队中元素个数个数count： count=(rear- -front+MaxSize)%MaxSize 已知已知front、count，求，求rear： rear=(front+count)%MaxSize 已知已知rear、count，求，求front： front=(rear- -count+MaxSize)%MaxSize 解：解：依题意设计的环形队列类型如下：依题意设计的环形队列类型如下： t
15、ypedef struct ElemType dataMaxSize; int front;/队头指针队头指针 int count;/队列中元素个数队列中元素个数 QuType; 该环形该环形队列队列的的4要素要素： 队队空条件：空条件：count0 队队满条件：满条件：countMaxSize 进进队队e操作：操作：rear=(rear+1)%MaxSize; 将将e放在放在rear处处 出出队操作：队操作：front=(front+1)%MaxSize; 取出取出front处元素处元素e; 注意：注意：这样这样的环形队列中最多可放置的环形队列中最多可放置MaxSize个元素。个元素。 vo
16、id InitQueue(QuType * qu-front=0; qu-count=0; 对应的算法如下：对应的算法如下： bool EnQueue(QuType */临时队尾指针临时队尾指针 if (qu-count=MaxSize)/队满上溢出队满上溢出 return false; else rear=(qu-front+qu-count)%MaxSize; /求队尾位置求队尾位置 rear=(rear+1)%MaxSize; /队尾循环增队尾循环增1 qu-datarear=x; qu-count+;/元素个数增元素个数增1 return true; 它是一个局部变量，队列 qu中不保存该值 bool DeQueue(QuType * else qu-front=(qu-front+1)%MaxSize; /队头循环增队头循环增1 x=qu-dataqu-front; qu-count-;/元素个数减元素个数减1 return true; 注意：注意： 本讲完本讲完