队列的建立和实现.ppt

前情回顾 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 2 a1入队 rear 3210 rear front rear 新建空队列时 令front rear 0 在队尾插入新元素 尾指针增1 删除队列头元素 头指针增1 在非空队列中 头指针始终指向队列头元素 而尾指针始终指向队列尾元素的下一个位置 3 2 2顺序队列 3210 3210 1 空队列 3 a2 a3 a4入队 a1出队 队满 顺序队列操作可能出现的问题 再有元素进队会怎样 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时 也是一样 3 2 3循环队列 循环队列的入队和出队操作演示 3 2 3循环队列 使用循环队列应注意的问题 队空条件 front rear 队满条件 1 规定队列中还有一个空的存储单元时为队满 即为front rear 1 MODmaxsize 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后移 即