3.2 队列-教学设计（表格式）

教学设计
课程基本信息
课题 3.2队列
教学目标
1.依据解决问题的需要，恰当的选择数据结构队列。 2.通过项目的实践活动，体验用队列解决问题的基本流程，逐步形成运用队列结构解决问题的思维方式和学科方法。
教学内容
教学重点： 1.队列的应用是3.2队列的概念、特性及基本操作的延续，是在学习了队列相关的操作的基础上，在现实问题中，恰当的选择队列来解决问题。 2.从实际问题中,能恰当地选择队列结构，
教学难点： 1.抽象与建模、设计算法的过程，并用队列的基本操作进行编程实现，可以采用教材中提供的“银行排队叫号系统”实列，参考教材，逐步体验抽象与建模、设计算法、编程实现等过程。
教学过程
一、情景导入 ： 【展示生活中的队列，以生活队列为例进行导入】 教师：我们在生活中去超市购物、影院取票都需要排队。去银行、医院办理业务时，取号机能按照到达时间的先后顺序，合理地安排办事次序。这些事件对数据的处理都具有先到先处理的特性，可以使用队列来解决。 学生：看图片思考生活中的队列应用 目的：引出本课课例的队列内容，引发学生对生活中的思考。
二、知识点讲解 【讲解清楚队列的概念、特性】 教师：队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。队列元素：就像同学们按学号排队，学号1是该队的队首，学号6是队尾，学号1-6都是队列元素。队列能实现队尾入队，队首出队。 队列的第一特性：由概念可知，队列具备“先进先出、后进后出”的特点。出队时，队首元素a1优先出队，紧接着是a2,a3,……,an-1 ，队尾元素an最后出队。 第二特性是有限序列性，队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 三、课中小练习 学生做练习，老师讲解 1. 幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适（ ） A.链表 B.字典 C.字符串 D.队列 2.下列事件执行过程与队列特征不相符的是（ ） A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 四、对列的基本操作以及基础代码讲解 教师：接下来，我们一起来学习一下队列的基本操作。队列一般按顺序结构存储，可以用数组来实现，也可以用链式存储结构存储，这被称为链队列,head纪录链表的头节点,tail纪录链表的队尾节点。 下面队列程序的模拟采用数组来实现。例如要“A”“B”“C”“D”按顺序入队、出队时候，可以创建一个队列que，长度为5，由于操作中队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾指针变量tail。python代码如下。 通过建队操作生成好之后，字母“A”“B”“C”“D”可以按顺序入队的python代码如下，que[tail] =“A”，A入队，tail指针后移准备下一个元素入队，依次重复，让ABCD都入队， 注意：tail到达最大下标时不能再增加，队列已满！ 队列中最多存储n-1个元素。由此可得，那队列为空是什么呢？非常好，head==tail时候队列为空。队列已满的时候tail指向最后索引值的位置，即tail==n-1；聪明的你肯定发现了，head记录队首元素所在的位置，tail记录队尾元素的下一个位置.字母“A”“B”“C”“D”按顺序出队时，排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空。所以来一起看一下while的条件，11111111111是不是应该在这里填上head ！= tail ，表示队列非空时候要循环做出队操作。 五、假溢出引出循环队列以及队列个数计算公式推导 教师：根据上面的操作，我们发现此时在顺序队列中tail=4,已经无法在插入数据，但实际上que[0]的数据已经出队，存储空间可用，这种情况便称之为“假溢出”。对于存储空间有限的情况，可以使用循环队列增加存储空间的利用率。循环队列就是将队列的队首和队尾连接起来，形成逻辑上的环状结构。队列为空时候head==tail，入队tail+1，出队head+1，循环队列满的时候，为了避免队空和满的条件都为head==tail，会在队尾留一个空闲的数据单元，循环队列最多可放n-1个数据元素。 我们来看一个列表，队列中有两个元素CD，tail已经指向最后一个位置，若让顺序队列在添加一个元素E，tail就出界报错，但是在循环队列中E入队，tail会循环到开头位置，甚至还能再添加一个元素F入队。循环队列的代码填空，若要队伍未满的时候可让E入队，if的条件应该怎么填呢？注意看最后这句tail=（tail+1）%n循环队列实现空间利用需要使用%形成环，所以当head!=(tail+1)%n指的是队伍未满。来看看第二个填空,若队伍非空，说明由元素可以出队，head指针移动可以参考刚刚入队时候tail的变化。那顺序队列和循环队列里面怎么根据head和tail计算出队列里面的元素个数呢 首先我们一起来看一下顺序队列,head=3,tail=6,那个数就是3个,所以顺序队列元素的个数就是tail-head个,而循环结构我们分成两个情况,一种是headtail的时候,来看一个例子,这个循环列表长度为8,tail=3,head=5,个数是6个,我们不难发现这种情况下个数为tail-head+n,所以我们可以一起总结通用个数的公式为(tail-head+n)%n python自带的队列模块讲解 队列知识点复习 老师注意可以强化的点： 1. 面对生活中的问题，如何恰当的选择数据结构； 2. 面对问题，如何分析问题、设计算法； 3. 在编写程序时，如何使用队列的入队、出队等操作。如何从实际问题中恰当的选择数据结构，抽象并建模，结合入队、出队等操作，设计“银行排队系统”的算法。时间有多的同学，可以编写程序，实现“银行排队系统”的功能。