《队列的建立和实现PPT课件》由会员分享，可在线阅读，更多相关《队列的建立和实现PPT课件（24页珍藏版）》请在金锄头文库上搜索。
1、前情回顾1.简要描述栈的概念和特点2.判断顺序栈（最多结点数为m）为栈满和栈空的条件分别是什么？3.如果入栈序列有组成, 请问输出序列可能有哪些? 3.2 队列队列示意图 an a2 a1队头(Front)队尾(Rear) 1.定义队列 (Queue)是仅在表尾进行插入操作，在表头进行删除操作的线性表。表尾即an端，称为队尾；表头即a1端，称为队头。例如：队列 Q= (a1, a2, a3 , , an-1, an )队头队尾 队列的概念与同线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队更常见。表尾插入元素称为入队；表头删除元素称为出队；访问结点时依照先进先出（FIFO）的原则。 3.
2、存储结构4.运算规则2.逻辑结构 队列的概念v头、尾指针和队列中元素之间的关系frontfronta1a4a3a2(2) a1入入队rear3210rearfrontrear新建空队列时，令front=rear=0在队尾插入新元素，“尾指针增1”删除队列头元素，“头指针增1”在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。 顺序队列32103210(1) 空空队列列(3) a2, a3, a4入入队, a1出出队，队满v顺序队列操作可能出现的问题rearfront初态fronta1a2a3reara1,a2,a3入队rearfronta4a5a6rearfron
3、trearfront再有元素再有元素进队会怎会怎样？ 顺序队列a1,a2,a3出队a4,a5,a6入队a4,a5,a6出队 顺序队列顺序队列的出队和入队操作v队满的三种情况1、所有单元都有元素；2、部分单元有元素；3、所有单元均无元素。当队满时再要插入元素，称为上溢。假溢出:队空间中还有存储单元未使用，但不能再插入元素;假溢出原因:头、尾指针值总是不断增加，已使用过的单元无法再使用。 顺序队列v解决假溢出的方法1.将队中元素依次向队头方向移动。 缺点：浪费时间。每移动一次，队中元素都要移动。2.将队空间设想成一个循环循环的表，即分配给队列的个存储单元可以循环使用，当rear为m时，若向量的开始
4、端空着，又可从头使用空着的空间。当front为m时，也是一样。fronta1a2anrear 循环队列循环队列的入队和出队操作演示 循环队列使用循环队列应注意的问题：front012345rear空循环队列a6a7a8a5a4a3012345frontrear满循环队列队空条件：front = rear;队满条件：(1) 规定队列中还有一个空的存储单元时为队满，即为 front=(rear+1)MOD maxsize(MOD为取余运算符）(2) 设置一个计数器size记录队列中元素的个数。 size = 0 队空 size = maxsize 队满实现方法：模(mod) 运算。插入元素： $L
5、$rear = $e; $rear = ($rear+1) $ maxsize;删除元素： $x = $L$front； $front=($front+1) $ maxsize；循环队列：循环使用为队列分配的存储空间。 循环队列 循环队列入队操作 循环队列出队操作o链队列的概念链队列-指用链表实现的队列。通常用带头节点带头节点的单链表实现；并设置头指针、尾指针，分别指向队列的队头和队尾。 链式队列 链式队列空队列：头指针和尾指针均指向空的头结点 链式队列入队链式队列入队：（1）将队尾rear的后继设为新结点s;（2）将队尾指针rear后移，即rear = rear-next; 链式队列出队链式队列出队：（1）保存头结点指示队头元素;（2）设置头结点的后继元素为队首元素的后继元素
