《数据结构》课程教学资源（教案设计）04 循环队列

编号：005 课程 章节 课程讲 数据结构 第三章栈和队列 45分钟 名称 名称 3.4队列 授学时 学习要求 知识点 熟练 识记理解 掌握 应用 分析 综合 队列的抽象数据类型定义 栈与队列的此较 课堂 顺序队列的假溢出现象 教学 队列的链式表示和顶序表示 循环队 目的 到 态度积极主动学习 熟练掌握队列这两种抽象数据类型的特点，并能在应用问题中正确选 能力 择使用哪种数据结构； 熟练掌握队列这两种结构的顺序表示和链式表示，会应用它们的基本 操作算法，学会分析算法的时间复杂性和空间复杂性； 教学内容（教学过程设计） 教学安排 复习及导入新课 复习：线性表的插入和删除操作，栈的相关操作 2分钟 导入新课队列 5分钟 3.4队列 给出队列的定义，通过实例说明队列的操作特性，给出队列抽象数据类 10分钟 型的定义 队列的分类：一端进、另一端出的队列：双端队列 10分钟 用图示意说明队列的特点 10分钟 提出问题：如何存储都队列？引出队列的顺序存储结构和链接存储结构 改造顺序表，得出循环队列的存储方法 3分钟 提出问题：如何判断循环队列的队空和队满？分析各种方案。在解决了 循环队列的关键问题后，基本操作的实现路讲 5分钟 提出问题：如何改造单链表实现队列的链接存储？引出链队列的存储方

编号：005 课程 名称 数据结构 章节 名称 第三章 栈和队列 3．4 队列 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 队列的抽象数据类型定义 √ 栈与队列的比较 √ √ √ √ 顺序队列的假溢出现象 √ √ √ 队列的链式表示和顺序表示——循环队 列 √ √ √ √ 态度 积极主动学习 能力 ➢ 熟练掌握队列这两种抽象数据类型的特点，并能在应用问题中正确选 择使用哪种数据结构； ➢ 熟练掌握队列这两种结构的顺序表示和链式表示，会应用它们的基本 操作算法，学会分析算法的时间复杂性和空间复杂性； 教学内容（教学过程设计） 教学安排 复习及导入新课 复习：线性表的插入和删除操作，栈的相关操作 ↓ 导入新课- -队列 ↓ 3．4 队列 给出队列的定义，通过实例说明队列的操作特性，给出队列抽象数据类 型的定义 队列的分类：一端进、另一端出的队列；双端队列 用图示意说明队列的特点 ↓ 提出问题：如何存储队列？引出队列的顺序存储结构和链接存储结构 改造顺序表，得出循环队列的存储方法 ↓ 提出问题：如何判断循环队列的队空和队满？分析各种方案。在解决了 循环队列的 关键问题后，基本操作的实现略讲 ↓ 提出问题：如何改造单链表实现队列的链接存储？引出链队列的存储方 2 分钟 5 分钟 10 分钟 10 分钟 10 分钟 3 分钟 5 分钟

链队列的出队算法要注意边界情况，其他基本操作的实现可以略讲 引导学生比较循环队列和链队列 队列的应用举例 教学提示 >队列是程序设计中常常用到的一种数据结构，学会使用队列对后面的学 习十分有益 注意将队列与线性表、栈做比校，根据生活中的实例深刻理解队列的操 作特点 >注意通过循环队列的引入过程启发学生的逻辑思维能力 重点： (1)队列的操作特性： 重点 (2)队列基本操作的实现。 与 难点 难点 循环队列的组织及队空和队满的判定条件。 教学策略： 对策 在授课过程中采用多煤体教学，首先还原问题的本来面目一 提出问题，引导学生 积极参与一尝试解决问题，在讨论的基础上给出结论一一讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 教学方法：导入，配合图形、实例讲解，提问、讨论 方法 教学手段：PPT课件，板书，动画演示 与 作业： (1)假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点 (注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法. 作业 (2)假设以数组Q[m网存放循环队列中的元素，同时设置一个标志tag,以ag 及 =0和tag==1来区别在队头指针(ron0和队尾指针(rea相等时，队列状态为 课外 “空还是满”，试编写与此结构相应的插入(enqueue)和删除dlqueue)算法。 推荐 (3)如果允许在循环队列的两端都可以进行插入和册除操作。要求： 资源 ①写出循环B队万列的类型定义： ②写出“从队尾别除”和"从队头插入”的算法。 课后导速： 回顾C语言中学过的函数嵌套调用，深入理解函数调用时系统的工作

法 链队列的出队算法要注意边界情况，其他基本操作的实现可以略讲 ↓ 引导学生比较循环队列和链队列 ↓ 队列的应用举例 ↓ 教学提示： ➢ 队列是程序设计中常常用到的一种数据结构，学会使用队列对后面的学 习十分有益 ➢ 注意将队列与线性表、栈做比较，根据生活中的实例深刻理解队列的操 作特点 ➢ 注意通过循环队列的引入过程启发学生的逻辑思维能力 重点 与 难点 对策 重点： （1）队列的操作特性； （2）队列基本操作的实现。 难点： 循环队列的组织及队空和队满的判定条件。 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： (1）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点 (注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 （2）假设以数组 Q[m]存放循环队列中的元素, 同时设置一个标志 tag，以 tag == 0 和 tag == 1 来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为 “空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 (3）如果允许在循环队列的两端都可以进行插入和删除操作。要求： ① 写出循环队列的类型定义； ② 写出“从队尾删除”和“从队头插入”的算法。 课后导读： ➢ 回顾 C 语言中学过的函数嵌套调用，深入理解函数调用时系统的工作

关于栈与队列的实现，《数据结构与算法》（齐德昱编著清华大学出版社） 中有用面向对象方法实现的 在《数据结构》（刘大友等高等教育出版社）中对递归和汉诺塔问题进行 了更深入的介绍 教学 后记

➢ 关于栈与队列的实现，《数据结构与算法》（齐德昱编著 清华大学出版社） 中有用面向对象方法实现的 ➢ 在《数据结构》（刘大友等 高等教育出版社）中对递归和汉诺塔问题进行 了更深入的介绍 教 学 后记