队列的建立和实现.pptVIP

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