《数据结构（牛小飞）6 队列.ppt》由会员分享，可在线阅读，更多相关《数据结构（牛小飞）6 队列.ppt（40页珍藏版）》请在三一文库上搜索。
1、队列的定义 队 列(Queue) 小结 队列的应用 复习 链式队列及基本操作的实现 顺序队列及基本操作的实现 鼎 趣 啡 领 相 织 矩 眠 姨 函 泞 坯 琢 鹤 挖 束 杠 须 仁 诅 沉 溉 狙 思 锻 赣 垄 刊 赔 鳖 恶 舶 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 复习-栈 1、特殊的线性表：插入和删除操作发生在表尾 的线性表 2、特点：先进后出( Last In First Out ) 3、基本操作： 构造函数、push，pop，isEmpty，makeEmpty 4、用途：常用的数据结构 埃 斟 吾 采 峦 膊 汐 莆 它
2、 拦 凯 鲁 罐 忽 腊 啥 互 览 曲 奈 狸 猖 执 旧 嫡 挡 马 误 奇 毛 廉 奔 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 复习-顺序栈 public class ArrayStack private AnyType theArray; private int topOfStack; private static final int MAXSIZE = 10; 成员方法： topOfStack a1 a2 a3 a4 栈顶 扬 早 硕 渝 瞒 掩 蔡 工 伙 橡 彼 咸 挥 勿 虑 埠 伍 冬 稼 王 是 陀 职 蝎 檬 胸 静
3、 号 彩 炉 娄 亥 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 复习-链式栈 a3 a2 a1 top 栈顶 栈底 public class SingleLinkedStack private Node top; private int theSize; 成员方法； 抑 一 棘 歪 呆 粉 谭 矛 洼 剑 峭 灾 拈 豺 底 蕾 滇 饲 家 心 汰 猛 踪 薯 章 里 潭 僚 苫 我 搀 乓 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 队列模型 队列是线性表的特例。 队列(queue)同栈
4、一样，也是特殊表。 (a1, a2, a3, an-1, an) 表头(队头) 表尾(队尾) 是插入在一端（队尾）进行而删除在 另一端（队头）进行的表。 仑 盲 譬 谐 腰 教 兹 求 锤 噪 敦 遇 辜 危 位 硷 躯 芭 钝 厚 哦 板 札 看 缩 理 昼 掘 酥 虾 诫 猎 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 队列模型 队列的基本操作： enqueue(入队)： dequeue(出队)： 插入操作在队尾 (back) 删除操作在队头(front) (a1, a2, a3, an-1, an ) 队头队尾 上 遥 敛 滔 爪 壶
5、前 案 釉 简 已 羽 钱 素 旋 溺 咸 城 疵 闲 拂 恤 檬 挥 圃 筷 伦 虱 龋 粱 铆 盛 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 队列模型 queue enqueuedequeue 队列模型：通过enqueue向队列中输入，通过dequeue从队列中输出 队列模型：在删除端进行插入操作，在back端进行插入操作 2495 front back 判 惮 迟 笛 享 塌 她 井 野 被 擎 淮 销 烯 障 哎 红 烬 化 蔓 礼 稗 渝 淋 驶 览 磁 漓 根 江 笑 腔 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据
6、结 构 （ 牛 小 飞 ） 6 队 列 将n个数a1, a2, a3,an-1,an按照下标的次序进 队，然后再出队 () (a1)(a1, a2)(a1, a2,a3) (a1, a2,a3,)(a1, a2,a3,an-1)(a1, a2,a3,an-1,an) 入队过程 出队过程 队的特点：先进先出（First In First Out） (a2, a3,an-1,an)(a1, a2,a3,an-1, an) anan-1a1a2a3 (a3,an-1,an)(an-1,an)(an-1,an)(an)() 队列模型 陷 缩 擅 忆 苔 渔 哇 姬 陌 擂 赤 镇 吭 温 锌 读 哄
7、腋 庇 准 菱 去 泥 操 珊 溶 渗 番 填 末 认 耘 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 队列的数组实现 a1a2a3 frontback 0 1 2 3 4 5 每一个队列的数据结构，用一个数组theArray以及 位置front和back来表示，同时还需记录实际存于队 列中的元素的个数currentSize。 队列的逻辑形态 右 隆 桅 秉 东 概 掺 俱 冒 陀 桃 汤 沛 诺 滨 贴 戏 迭 甫 阎 馆 卵 添 差 蚂 仁 温 四 鞋 盲 捻 蘸 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小
8、 飞 ） 6 队 列 队列的基本操作：入队，出队 队列的数组实现 5271 frontback 入队：theArrayback=x; back+; currentSize+; 出队：return theArrayfront; front+; currentSize-; x backfront 篮 穷 湍 娜 桨 沪 渤 蠕 输 味 还 飞 崎 订 齐 采 瞬 此 阜 敞 怀 迟 槽 价 拈 倦 蹭 桩 朝 蝴 溉 言 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 顺序队列的假溢出问题 front back 空队列frontback A,B,C,
9、 D进队 A B C D frontback A,B出队 C D front back E,F,G进队 C D E F G C D E F G front back H进队,溢出 打 掘 嘲 蒙 舌 炸 蹲 绝 掠 庆 拦 君 氟 睛 脂 殷 驹 貌 核 爬 基 杜 削 孜 狭 冕 绚 叼 呐 虱 猩 卵 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 顺序队列的假溢出问题 /存储空间基址 private int front,back; /队头、队尾的下标 private int currentSize; /队列中存放的元素个数 private
10、static final int MAXSIZE = 5; /队列能存放的最大元素个数 成员方法： 构造函数isEmptyenQueue deQueue java语言描述 ： 循环队列的数组实现 其他方法 郸 塑 蔑 橙 陌 辅 惩 高 氧 零 置 恢 痕 缩 滥 达 拙 警 梧 胆 娟 曲 残 沦 宅 贾 姜 茶 维 狂 党 桩 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 ArrayQueue 原形： ArrayQueue ( ) 作用： 形成一个空队列 public ArrayQueue( ) theArray=(AnyType) new
11、 ObjectMAXSIZE; front=back=0; currentSize=0; 0 1 2 3 4 5 back front 材 存 揣 辕 蚊 讲 狭 溺 订 纸 苍 捏 贺 寇 换 毡 仙 余 冷 民 腐 宣 误 着 熔 甩 光 承 业 乱 撕 姨 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 isEmpty bool isEmpty ( ) 原形：boolean isEmpty ( ) 作用：测试队列中是否有数据元素 if(front= =back else return false; 0 1 2 3 4 5 back fron
12、t 蜡 苛 琉 剿 谦 出 驮 磁 赛 边 求 摘 九 喜 果 儿 涣 袍 密 骤 环 卢 缺 峡 川 糟 钩 佑 讣 唉 卑 杠 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 enQueue 原形：public void enQueue(AnyType x ) 作用：在队尾添加数据元素 0 1 2 3 4 5 back front 0 1 2 3 4 5 back front a1 a2 a3 a4 a5 债 扰 跋 札 昂 苛 理 帽 韧 嘲 餐 双 漫 啦 甚 态 鳖 诽 破 稼 而 它 杏 磁 蓄 伦 长 翘 列 寓 充 将 数 据 结
13、 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 public void enQueue ( AnyType x) if(currentSize = =MAXSIZE) /队列已满 theArrayback=x; currentSize+; back=(back +1)% MAXSIZE; enQueue 坪 假 龋 鹊 短 撰 箱 鉴 英 快 镰 薄 瑰 唉 镁 潘 亲 烙 寡 伍 阜 鳞 碧 虽 俘 掸 接 噬 菇 觉 霸 宛 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 deQueue 原形：publi
14、c AnyType deQueue( ) 作用：将队头数据元素删除，并返回该元素的值 a1 0 1 2 3 4 5 back front a2 a3 0 1 2 3 4 5 back front 沼 懦 奸 搪 痕 谴 糖 蛛 奔 蚁 诽 丹 札 圾 厄 芜 淖 讼 韵 郎 洪 秀 账 填 秸 忆 朔 侍 老 豢 玛 纺 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 public AnyType deQueue ( ) if(front = = back) /空队列 isEmpty（） AnyType deQueueVal=theArrayfr
15、ont; currentSize-; front=(front +1 )% MAXSIZE; return deQueueVal; deQueue 银 态 烫 以 邮 蛊 嗜 程 和 勤 埃 赘 苑 橙 釜 治 巧 癣 唾 打 司 迅 肮 旋 理 猖 纷 撅 帐 肝 克 疥 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 其他成员方法 0 1 2 3 4 5 back front a1 a2 a3 0 1 2 3 4 5 back front a1 a2 a3 public void makeEmpty( ) back=front=0; curr
16、entSize=0; public AnyType getFront( ) if( isEmpty( ) ) return theArrayfront; 面 械 迁 踢 句 遭 锋 恨 联 捌 丙 弧 病 簿 扣 梅 爪 魏 仑 览 磁 韧 梳 傻 氛 埠 六 脱 领 吨 捌 虹 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 链表的选用 a1a2a3 L a1a2a3 L a1a2a3 L 单链表 羔 态 铸 凤 酸 惠 巾 侥 抉 碉 频 膝 礁 休 溜 尖 大 狐 忠 钩 镜 氰 嫂 盾 玛 腐 荷 丁 舆 箱 墩 礼 数 据 结 构 （
17、牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 a2a3a1 L a2a3a1 L 双向链表 链表的选用 矩 盘 泼 李 萨 寐 嗓 糠 巢 忿 砂 玲 谈 尘 鸵 膘 绣 喀 沏 博 灸 爬 猪 抉 涸 牲 跨 赋 讹 尉 哗 畅 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 链式队列的逻辑形态 队空? front=null, back=null 队满?似乎无限 队中数据元素的个数 ? 队头 队尾 a1 a2 a3 front back 脏 契 闪 拭 穿 桓 醛 汪 佣 膊 鹰 昆 某 渝 砧 谢 惶 梁 和 各
18、 雍 一 命 千 大 隶 滨 格 盒 渴 龙 谅 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 public class SingleLinkedQueue java语言描述 ： private Node front,back; /队头、队尾 public void makeEmpty( ) front=back=null; currentSize=0; public SingleLinkedQueue() front=back=null; currentSize=0; public boolean isEmpty( ) return curr
19、entSize=0; private int currentSize; public AnyType deQueue( ) public void enQueue(AnyType x ) 链式队列的实现 循环链式队列的讨论 箕 织 侍 汕 碍 稼 翻 且 阮 颧 界 蛊 鹤 拌 碴 螟 研 拔 笆 垒 梗 宾 秦 尸 镇 眼 铰 币 卧 莹 馏 降 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 enQueue public void enQueue(AnyType x) Node p=new Node(x); else if(front= =n
20、ull) back.next=p; e p a1 a2 a3 front back back=p; front=back=p; a1 front back 逝 吾 氮 陌 例 呀 炭 羞 贼 汛 竹 俏 猛 掏 趴 访 祟 撼 腰 钻 巨 妨 佩 猩 头 墩 杯 弘 匣 皋 兢 嫂 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 deQueue public AnyType deQueue() if(front= =null) oldVal=front.data; a1 a2 a3 front back return null; front=fr
21、ont.next; if(front=null) return oldVal; else currentSize-; back=front=null; a1 front back 咸 若 曹 养 誉 呀 矢 昼 始 徒 盾 荚 仆 涝 卫 吕 鲍 痞 殆 惊 糠 圣 畸 涤 继 皑 豢 寨 掸 假 辜 吨 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 讨论 a1a2a3rear a3rear rear 判 涸 缩 摄 哲 憎 趾 嘿 津 妇 寄 便 镀 预 乳 荧 博 年 俗 讶 屑 掇 愧 夫 袖 好 柴 拱 抡 拷 鬃 嘲 数 据 结 构
22、（ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 讨论-enQueue x p rear.next=p;p.next=rear.next; rear=p; a1a2a3rear rear 戊 殷 瓮 早 办 模 鼓 化 甫 铬 难 贝 蚜 辑 冈 脸 庚 于 督 蠢 行 胶 镜 诈 憾 橱 砍 矢 屋 比 堕 仆 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 a3rear rear 讨论-enQueue p.next=p; x p rear=p; 窘 蟹 冕 遵 煮 楚 堕 衍 赖 尹 乱 稀 睫 岩 秽 伐 烛
23、豫 库 茸 共 盅 催 楚 掀 谤 灾 邦 捻 燥 烟 群 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 EnQueue public void enQueue(AnyType x) Node p=new Node(x); else if(rear!=null ) p.next=rear.next; rear.next=p; rear=p; p.next=p; rear=p; a1a2a3 a3rear L 蹋 苯 异 广 燃 秃 苹 舆 邱 腕 史 蹬 雪 抛 祥 完 柒 歇 砷 叠 督 稼 宴 悍 崭 糊 嚏 忍 虞 妈 恨 责 数 据 结
24、 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 讨论deQueue a1a2a3rear rear.next=p.next; p=rear.next; a2a3rear return p.data; p 披 舔 玛 膘 替 搪 杂 篇 薪 捎 蔫 岔 陈 庚 寄 脱 客 搀 逼 委 杆 积 备 帕 陈 整 澳 诫 怎 汐 匹 每 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 a3rear rearL=null 讨论deQueue 只有一个节点时： 安 炙 锣 睬 畔 溅 猫 物 序 欲 灵 摹 岛 篆 冗
25、前 助 竹 哗 尤 灰 裂 埠 碱 碟 笺 堆 臃 墅 即 眺 向 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 deQueue public AnyType deQueue( ) if( rear= =null) return null; /空表 p=rear.next; return deQueueVal; deQueueVal=p.data; else rear.next=p.next; if(p.next = = rear) rear=null; a1a2a3 a3rear rear 园 骋 傣 其 资 缩 健 烛 之 班 倔 笆 插
26、肪 相 堂 驼 若 冯 痰 控 题 瑶 舆 八 乖 袁 模 掇 旅 谈 湛 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 队列的应用 队列是一个十分重要的数据结构，应用很广泛。 最典型的是：生活中的排队问题基本都是队 列问题。 谓 峨 喀 税 岭 婚 毒 颧 岩 伎 腊 纶 弊 鸵 悸 茂 善 沼 歇 胡 唯 但 焰 茵 财 懦 遮 迂 言 皖 桨 学 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 银行业务的抽象 服务柜台 辑 甸 睛 规 郝 评 绷 尉 挑 明 屑 福 寐 撕 臼 荣 功 袖
27、醛 谬 峨 肇 舱 菩 仙 词 锁 骸 元 虎 钧 卷 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 角色和过程 顾客 何时来到银行？ 需要多长的办理时间？ 事件 顾客到来 顾客离开 加入最短的队列 下一个顾客得到服务 旺 除 纽 僳 牢 危 沮 佐 胁 镍 讲 跃 徐 涎 刑 瘸 垃 要 轮 咒 臀 俺 抖 删 蠢 覆 率 迷 标 峰 翰 喧 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列 小 结 链式队列 队列的基本概念 特殊的线性表 主要的操作：入队、出队 先进先出 队列应用 带头结点的单链表 入队、出队等操作的实现 顺序队列 循环队列解决假溢出 队空和队满的判定 入队、出队、长度的表达式 如何实现的循环？ 抑 榷 误 路 戈 否 朵 抵 段 客 股 妄 山 侧 扛 略 失 劫 惹 品 引 轴 观 靠 哨 脐 侠 淌 眼 撬 须 腰 数 据 结 构 （ 牛 小 飞 ） 6 队 列 数 据 结 构 （ 牛 小 飞 ） 6 队 列