数据结构-队列.ppt.ppt

第二章队列 吉林大学计算机学院谷方明fmgu2002 例子 电话号码 向计算机专业的同学要电话号码 他 她 不会直接给你的 原因你懂的 他 她 会告诉你一串加密过的数字 同时告诉你解密的规则 规则是这样的 首先将第1个数删除 紧接着将第2个数放到这串数的末尾 再将第3个数删除并将第4个数放到这串数的末尾 直到剩下最后一个数 把这个数也删除 按删除的顺序将删除的数连在一起 就是电话号了 例如 58659146 1 队列的定义 队列 queue 是一种操作受限的线性表 它的所有插入都在表的一端进行 所有的删除都在表的另一端进行 例子食堂窗口进程调度队列的特性 先进先出 栈也称作后进先出表 FirstInFirstOut FIFO 队头 front 进行删除的一端 队尾 rear 进行插入的一端 空队列 没有元素的队列 插入 入队删除 出队 术语 队列的基本操作 1 队列初始化 2 入队 插入 3 出队 删除 4 读取队首元素 5 判断队列是否空 6 确定队列中元素个数 7 置空队列 2 队列的顺序存储 按顺序存储方式存放队列元素 称为顺序队 存放队列元素的数组 Tqlist MaxQSize front队首元素的下标rear队尾元素的下标加1队列空 front rear队列满 rear MaxQSize 插入队尾元素 rear rear 1 删除队首元素 front front 1 假溢出 循环队列 插入元素 rear顺时针移动一位 rear rear 1 MODMaxQSize 删除元素 front顺时针移动一位 front front 1 MODMaxQSize 循环队列 front指定队首位置 删除一个元素就将front顺时针移动一位 rear指向元素要插入的位置 插入一个元素就将rear顺时针移动一位 count存放队列中元素的个数 当count等于MaxQSize时 不可再向队列中插入元素 队空 count 0队满 count MaxQSize 顺序队列类AQueue的类声明templateclassAQueue private intfront 队首所在数组元素下标intrear 新元素要插入的位置 下标 intcount 队列中元素个数T QArray 存放队列元素的数组intSize 存放队列的数组规模public AQueue intMaxQueueSize 10 构造函数 AQueue delete QArray 析构 voidQInsert constT 清空队列 插入算法ADL描述 算法QInsert A item 在队列A中将元素item插入队尾QI1 队列满 IFcount sizeTHEN PRINT 队列已满无法插入 RETURN QI2 元素插入 A rear item 将新元素插入队尾QI3 更新 rear MOD rear 1 size 更新队尾下标count count 1 更新队列长度 C 实现 templatevoidAQueue QInsert constT 删除算法ADL描述 算法QDelete A item 删除队列A的队首元素 并将其元素值赋给变量itemQD1 队列空 IFcount 0THEN PRINT 队列空无法删除 RETURN QD2 出队 item A front 将队首元素保存至itemQD3 更新 front MOD front 1 size 更新队首元素下标count count 1 更新队列长度 C 实现 templatevoidAQueue QDelete T 取队首算法ADL描述 算法QFront A item 读取队列A的队首元素值 并将其赋给变量itemQF1 队列空 IFcount 0THEN PRINT 队列空无法读取 RETURN QF2 存取 item A front 将队首元素保存至item C 实现 templateTAQueue QFront const returnQArray front 验证 include aqueue h intmain intn i x AQueues 100 cin n for i 1 i n i s QInsert i for i 1 i n i s QDelete x cout x endl 队列运行示意图 3 队列的链接存储 templateclassNode Tdata Node next 链队LQueue的类定义 templateclassLQueue private Node front rear 指向队首和队尾的指针public LQueue void front rear NULL 构造函数 LQueue void QClear 析构函数 voidQInsert constT 清空队列 插入算法ADL描述 算法QInsert item 将元素item插入队尾QI1 创建新结点 s AVAIL data s item next s NULL 为新结点申请空间 令其字段值为item 指针域为空QI2 队空 IFfront NULLTHENfront s 若队列为空 令队首指针指向sELSEnext rear s 若队列非空 令表尾结点的next指针指向sQI3 更新队尾指针 rear s 更新表尾指针 C 实现 voidLQueue QInsert constT 删除算法ADL描述 算法QDelete item 删除队首结点并将其字段值存于itemQD1 队列空 IFfront NULLTHEN PRINT 队列为空 RETURN QD2 出队 q front item data q 令指针q指向队首 并保存其字段值front next front 令队首指针指向原队首结点之后继结点AVAIL q 释放原队首结点的存储空间QD3 出队后队列空 IFfront NULLTHENrear NULL 若删除队首结点后队列为空 则令队尾指针修为空 C 实现 templatevoidLQueue QDelete T 取队首算法ADL描述 算法QFront item 读取队首元素值 并将其赋给变量itemQF1 队列空 IFfront NULLTHEN PRINT 队列空无法读取 RETURN QF2 存取 item data front 将队首元素保存至item C 实现 templateTLQueue QFront const if front returnfront data 验证 include lqueue h intmain intn i x LQueues cin n for i 1 i n i s QInsert i for i 1 i n i s QDelete x cout x endl 顺序队列与链式队列的比较 在空间复杂性上 顺序队列必须初始就申请固定的空间 当队列不满时 必然造成空间的浪费 链式队列所需空间是根据需要随时申请的 其代价是为每个元素提供空间以存储其next指针域 在时间复杂性上 对于队列的基本操作 入队 出队和存取 顺序