3.2 队列（教学设计）信息技术浙教版2019选择性必修1

3.2 队列 1课时（教学设计） 年级 高二年级 授课时间 1课时 课题 3.2 队列 教学 目标 1.依据解决问题的需要，恰当的选择数据结构队列。 2.通过项目的实践活动，体验用队列解决问题的基本流程，逐步形成运用队列结构解决问题的思维方式和学科方法。 教学 重难点 重点： 1.队列的概念、特性及基本操作的延续，是在学习了队列相关的操作的基础上，在现实问题中，恰当的选择队列来解决问题。 2.从实际问题中,能恰当地选择队列结构， 难点： 1.抽象与建模、设计算法的过程，并用队列的基本操作进行编程实现，可以采用教材中提供的“信息的加密”实列，参考教材，逐步体验抽象与建模、设计算法、编程实现等过程。 教学 准备 多媒体课件、多媒体教室 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.展示两张图片：食堂排队打饭、银行取号，抛出问题：分析食堂打饭为什么需要排队，这样做有什么好处?银行取号系统和叫号系统是怎么实现的，试着剖析其实现原理?小组合作、讨论、设计分析算法。 排队和取号机能按照客户或患者到达时间的先后顺序，合理地安排办事次序。 这些事件对数据的处理都具有排队的特性，可以使用队列来解决。 以生活实际为例，吸引学生参与课堂，抛出问题，让学生思考并观看教师的PPT课件上的图片提示，从而引出本堂课的主题。 新 知 讲 授 2、 队列的概念与特性 1.概念 概念： 是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。 2.特性 （1）先进先出、后进后出 入队：在队列中插入一个元素的过程 出队：在队列中删除一个元素的过程 元素入队顺序和元素出队顺序一致。 出队时，队首元素A优先出队，紧接着是B队尾元素C最后出队。 （2）有限序列性 有限序列性：队列是一种线性表结构，元素的个数也是有限的 队首元素：只有一个后驱节点 队尾元素：只有一个前驱节点 （3）课堂练习 ①幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适( D ) A.链表 B.字典 C.字符串 D.队列 ②下列事件执行过程与队列特征不相符的是( C ) A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 三、队列的基本操作 队列按顺序结构存储，可用数组来实现。 数组que中存储了一个队列，共有4个元素，队首元素为a1，队尾元素为a4。 a1 a2 a3 a4 0 1 2 3 队列的存储 在入队和出队的过程中，队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。 如上图，初始时，head指针变量与tail指针变量均记录下标为0的位置。 提示：队列一般按顺序结构存储，可以通过数组实现。 head：记录队首元素所在的位置 tail：记录队尾元素所在位置的下一位置 队列的head、tail指针变化图 元素a1，a2，a3，a4依次入队后，tail值为4，head值为0。 当a1，a2出队后，head记录下标为2的位置，tail值不变。当a3，a4出队后，head与tail的值均为4，队列为空。 拓展链接 队列的链式存储结构 队列的链式存储称为链队列，为了操作方便，可设置队首指针head记录链表的头节点，队尾指针tail记录链表的队尾节点。 队列的链式存储结构 队列的常用操作有建队、入队、出队等。 1.建队 假设我们现在有A”“B”“C”“D”4个字母，如何进行建队呢？ 使用[]来截取字符串。即:序列的索引和切片操作。 需要几个变量？列表长度是多少？ Python代码 head=0 tail=0 que=[""]*5 思考：为什么列表长度是5，而不是4呢？ 2.入队 字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪各元素的入队。 字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪各元素的入队。 入队Python代码如下 que[tail]="A" #字母A入队 tail=tail+1 #tail=1 que[tail]="B" #字母B入队 tail=tail+1 #tail=2 que[tail]="C" #字母C入队 tail=tail+1 #tail=3 que[tail]="D" #字母D入队 tail=tail+1 #tail=4 3.出队 出队时，排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空。 出队Python代码如下 print(que[head]) # 输出A que[head]=“” head=head+1 print(que[head]) # 输出B que[head]=“” head=head+1 print(que[head]) # 输出C que[head]=“” head=head+1 此时head=tail=4，还可以有新元素入队吗？ 假溢出 4.拓展链接 循环队列 循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。 顺序队列的假溢出:随着队首元素出队会慢慢的空出一个个储存单元，但是队尾一直在进，最后导致前面的储存空间未满就队列就满了。 解决办法：将顺序队列做成循环队列！ 某队列分配的最大空间为5，其最后一个位置上的元素为“E”，队首指针变量head的值为4，队尾指针变量tail的值为5（tail超出了队列的边界），此时，数组中存在空闲位置，但新的元素不能入队。将该队列改为循环队列，则在元素“E”入队后， head的值为4，队尾指针重新指向队首（tail的值为0），当新元素“F”入队时，就加入到队首，然后tail的值变为1。用Python实现的程序如下： 5.课堂练习 ①已知队列元素的个数为6，则队首指针 head 和队尾指针 tail 的值不可能的是( D ) A.head=0, tail=6 B. head=6,tail=0 C. head=3,tail=2 D. head=3,tail=8 6.例题 信息的加密 给定一个字符串S1，S2，…，Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…SnS2；接着把S3取出，S4放到字符串的末尾S2后面……直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串。请编写一个加密程序，输入一个字符串（长度小于等于30），输出该字符串的密串。 加密的过程，类似队列的入队、出队操作。先把原字符串中各字符依次入队，得到一个队列，再执行加密的过程：取出队首元素，存到密串中，队列中第二个元素升级为队首元素；再取出队首元素，并把该元素插入队尾。反复操作，直至队列为空，得到密串。 以字符串“STRING”为例，算法步骤如下： ①创建que队列，把字符串“STRING”按序压入队列，tail值为6，head值为0。 ②加密过程。先取出队首元素“S”，并输出，同时head值加1，记录新的队首元素“T”所在的位置。再取出队首元素“T”，并把该元素加入队尾，head值、tail值均加1。 ③重复操作②，直至队列为空。 前两个字母的出队、入队过程如图 用Python实现的程序如下： 7.拓展链接 Python自带的队列模块 Python中自带了队列模块，可以实现队列的建队、入队、出队等操作，代码如下： import queue #引用队列模块 q=queue.Queue(10) #建一个长度为10的队列q q.put("A") #字母A入队 q.put("B") #字母B入队 print(q.qsize()) #输出队列中元素的个数，个数为2 print(q.get()) #队首元素出队，出队元素为A print(q.qsize()) #输出队列中元素的个数，个数为1 四、课堂练习 1.用 python 列表模拟循环队列，并设置队首指针head指向队首元素，队尾指针指向队尾元素的下一个位置,则当列表长度 n=10，head=6，tail=3 时，队列中元素的个数为( C ) A.5 B.6 C.7 D.8 2.已知队列(4，21，55，66，48，24，35，12，78，5)第 一个进入队列的元素是4，请问第3个出队列的元素是( C ) A.35 B.12 C.55 D.5 四、课堂小结 通过实际问题（疯狂动物城中的一张冰淇淋买卖的图片），恰当地展示队列结构，并总结队列的概念。(意图:体现先学后教的理念。） 通过实际问题，恰当地选择队列结构，通过动画显示队列的特性，并总结队列的特性。 通过课堂练习，加深同学们对队列的理解。 通过实际问题，恰当地选择队列结构，并总结队列的基本操作。 通过队列的常用操作：建队、入队、出队的讲解，然后再将队列问题进行抽象化的展示，让学生理解队列如何解决实际中的问题，体验用队列解决问题的基本流程，逐步形成运用队列结构解决问题的思维方式和学科方法。 通过问题延伸：假溢出 ， 再引出循环队列，通过循环队列来解决问题，体验用队列解决问题的基本流程，逐步形成运用队列结构解决问题的思维方式和学科方法。 通过案例讲解：信息的加密， 体验用队列解决问题的基本流程，逐步形成运用队列结构解决问题的思维方式和学科方法。 用练习巩固课堂知识，帮助学生更好地掌握。 课 堂 练 习 （有题有答案有解析） 1.队列是一种先进先出的 ，允许插入的一端称为队尾，允许删除的一端称为 。 2.队列中的数据元素称为 。在队列中插入一个元素称为 ，从队列中删除一个元素称为 。 3.队列的特性: 、 。 4.队列的元素个数是 。 5.队列中所有元素呈 ，队首元素只有一个 ，队尾元素只有一个 。 6.队列一般按 ，可以用 来实现。 7.队列的常用操作有 、 、 等。 8.循环队列是将队列的 ，形成逻辑上的环状结构。 9.幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适( ) A.链表 B.字典 C.字符串 D.队列 10.下列事件执行过程与队列特征不相符的是( ) A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 11.已知队列元素的个数为6，则队首指针 head 和队尾指针 tail 的值不可能的是( ) A.head=0, tail=6 B. head=6,tail=0 C. head=3,tail=2 D. head=3,tail=8 12.用 python 列表模拟循环队列，并设置队首指针head指向队首元素，队尾指针指向队尾元素的下一个位置,则当列表长度 n=10，head=6，tail=3 时，队列中元素的个数为( ) A.5 B.6 C.7 D.8 13.已知队列(4，21，55，66，48，24，35，12，78，5)第一个进入队列的元素是4，请问第3个出队列的元素是( ) A.35 B.12 C.55 D.5 14.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( ) A.栈 B.队列 C.树 D.图 参考答案： 1.线性表、队首 2.队列元素、入队、出队 3.先进先出、后进后出、有限序列性 4.有限的 5.现线性特征、后继点、前驱点 6.顺序结构存储、数组 7.建队、入队、出队 8.队列的队首和队尾连接起来 9.答案：D [解析]链表是存储结构，字段是数据类型，栈和队列是数据结构。排队玩滑滑梯是一头进一头出的队列结构。 10.答案：C [解析]队列数据是一头进一头出，先进先出。C选项是栈的特点，进出只有一头，先进的后出。ABD选项符合队列特点。故选C。 11.答案：B [解析]本题考查的是队列的相关知识。初始时，队列为空，队首指针head和队尾指针tail的值均为0，队列不为空时，队首指针指向队首元素，队尾指针指向队尾元素的下一个位置。选项A中入队6次，出队0次，那么head和tail的值为0，6该项正确;同理分析选项B，选项B，不可能入队0次，出队6次，该项错误。 12.答案：D [解析]head表示队首，tail表示队尾。当head等于tail时表示队列结束。本题意中的队列元素分别是a列表中下标为6，7，8，9，0，1，2，3的元素，共8个元素。故选D。 13.答案：C [解析]队列进出的原则是先进先出，第3个出队列的实在第3个进队列，第一个为4，第3个为55，第3个出队列的就是55。 14.答案：B [解析]为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，该缓冲区的逻辑结构应该是(队列)栈的定义:栈是只准在表尾进行插入和删除的线性表，称为LIOFO(即后进先出表)。允许插入和删除的一端叫栈顶，另一端叫栈底。队列的定义:队列是允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列也称为先进先出表(FIFO)树的定义:树是包含n个结点的有限集合 (n>0)图的定义:图(Graph)是由非空的顶点集合和一个描述顶点之间关系一-边(或者弧)的集合组成。其形式化定义为:G=(V,E)其中G表一个图，V是图G中顶点的集合，E是图G中边的集合。 课 堂 小 结 课堂小结 1.队列的概念与特性 （1）队列的概念 （2）队列的特性 ①先进先出、后进后出 ②有限序列性 2.队列的基本操作 （1）建队 （2）入队、出队 作 业 设 计 1.依次在初始为空的队列中将元素“h”，“e”，“l”，“l”，“o”入队以后，紧接着做了两次删除操作，此时的队首元素是（ ） A.“h” B.“e” C.“l” D.“o” 2.下列对队列的描述，正确的是（ ） A.队列的特点是先进后出 B.在队列中，允许插入的一端称为队首，允许删除的一端称为队尾 C.刚建立的队列，队首指针和队尾指针均为0 D.出队操作时，先将队首指针加1，然后再将队首元素出队 3小王在使用队列解决问题的过程中，初始时，队列为空，队列的首指针和尾指针分为为head、tail，接着小王开始进行了一系列的操作，操作序列为：入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队，则操作结束时head和tail的值分别为（ ） A.4 7 B.4 8 C.5 7 D.5 8 4.有1个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中l个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（ ） A．2，9，5 B.2，5，8 C.5，8，2 D.8，3，2 5.创建一个容量为3的队列，元素2，3，5，1，3，5，2依次等待入队。入队规则为： ①若当前待入队元素已经在队列中，则跳过该元素，否则转② ②若当前队列已满，将队首元素出队列，否则转③ ③将当前待入队元素入队列 操作完成后，队列中的元素为（　　） A．2，3，5，1 B.1，2，3，5 C.2，3，5 D.5，1，2 6.有如下python 程序段，使用长度为3的列表q模拟队列的出队、入队活动： q=[1,2,3] ys=[] for i in range(4,10): ys.append(q[0]) q[0]=q[1] q[1]=q[2] q[2]=i print(ys,q) 程序运行结束后，列表ys中元素的数量为_____________。 7.有如下python程序段： from queue import Queue q=Queue(5) print(“能存放的最多元素个数=”,q.maxsize) #q.maxsize 返回最大元素个数 for i in range(q.maxsize): q.put(3*i) print(“是否满：”,q.full()) #q.full 返回True或False for i in range(q.qsize()): print(“当前实际长度=”,q.qsize()) print(“取出元素：”,q.get()) 从队列中取出的元素依次是____________。 8.银行叫号排队系统：客户去银行办理业务时，需先从取号机上取一张排队号，然后等待叫号系统叫号去柜台办理业务。请设计算法，实现该叫号系统的功能。 （1）思考：取号、叫号的顺序符合__________数据结构的特征？ （2）算法设计： ①建立队列que，队列的初始长度设置为1000，初始值均为-1。设置队首指针变量head，队尾指针变量tail的值均为0。 ②设计输入提示界面，实现多次取号和叫号功能。用x存储输入的数字，如果x=1，实现取号功能；x=2，实现叫号功能；x=3，程序退出。 ③当x=1时，分配一个号码，入队指针tail加1，并显示需要等待的人数。 ④当x=2时，先判断que队列是否为空。若为空，则显示无等待的人员；否则，que队首元素出队，head指针加1，并显示可以办理业务的客户号码。 （3）算法实现，并在划线处填入正确的语句。 que=[-1]*100;head=tail=0 print("1.新到顾客（取号)") print("2.下一个顾客（叫号）") print("3.程序结束") x=int(input("请输入操作编号：")) while x!=3: if x==1: que[tail]=tail print("您当前的号码为：A%d,需要等待的人数为:%d"%( ___①_ ,___②__)) __③_______ if x==2: if ____④_________: print("对不起，没有等待的客户！") else: print("请A%d的客户准备，马上为您办理业务！"% _____⑤___ ) ____⑥_______ x=int(input("请输入操作编号：")) 反 思 评 价 本堂课讲解的是理论方面的知识，比较枯燥，只有通过大量的举例来充实课堂。通过列举实例，分析队列概念和特性，让学生们通过实际问题，恰当地选择队列结构，并总结队列的概念、特性及基本操作。体验用队列解决问题的基本流程，逐步形成运用队列结构解决问题的思维方式和学科方法。最终能够熟练掌握队列的建队、入队、出队等基本操作。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$