中小学教育资源及组卷应用平台 第三单元 特殊的线性表 项目四 探索电子排队预订功能的实现 ———队列的应用 第一课时 分析问题 ?教材分析 本节的主要内容是分析问题。通过以探索电子排队预订功能的实现为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课从分析电子排队预定功能中先来先服务的思想入手，结合活动帮助学生理解队列的概念以及“进队”“出队”。通过本节课的学习能培养学生的信息意识和计算思维能力。 ?教学目标 1.理解队列的概念和特征； 2.理解队首、队尾指针的作用； 3.理解顺序队列、链式队列存储的原理和特点； 4.能用循环队列解决顺序队列可能出现的“假队满”和“假队空”问题； 5.培养学生的信息意识和计算思维能力。 ?教学重点 1.理解队列的概念和特征。 2.理解顺序队列、链式队列存储的原理和特点； ?教学难点 1.能用循环队列解决顺序队列可能出现的“假队满”和“假队空”问题。 2.培养学生的信息意识和计算思维能力。 ?教学方法 体验法、讲授法、讨论法、示例法 ?教学准备 计算机教室、多媒体设备、多媒体广播软件、教学课件、Python编程环境、学生上机练习的程序文件，预先编制的Python程序文件等。 ?教学过程 一、新课导入 日常生活中，商品和服务需求大于供给的情况时有发生，例如限量商品发售、医院专家门诊号等。为了避免商场、医院或营业厅里人潮拥挤，等候的客户排起长龙，一些企事业单位在相应网站或手机App上提供了预约服务，如图3-1所示。客户输入身份、账号信息提交后自动进入电子排队预订系统。你知道电子排队预订系统是如何实现排队预约的吗？ 图3-1电子排队预订系统 二、分析问题 电子排队预订系统是计算机自动控制的排队系统，排队的特点是先来先服务，那计算机是怎么实现自动排队的呢？当客户在电子排队预订系统提交信息后，客户的预订数据就进入队列，称为进队(也称人队)，即在队尾(rear)插入个客户账号数据；当正式购买商品时就到队列中取出客户账号数据，称为出队，即在队首(front)取出一个客户账号数据(客户账号数据暂用A0001形式替代)，如图3-2所示。 图3-2预订一购买队列 用先进先出的数据结构来存储排队的客户账号数据，就可以方便地实现先来先服务，这种数据结构称为队列。 思考与讨论 生活中还有其他类似的先进先出的例子吗？ 生活中需要排队的问题，如医院挂号看病、加油站排队加油、小孩子排队滑滑梯、一队人过独木桥等。 核心概念 队列( queue)是一种只允许在表的前端(队头)进行删除操作，而在表的后端(队尾)进行插入操作的线性表。队列又称为先进先出( first in first out,fifo)表。 小贴士 队列是一种操作上受限制的线性表，只允许在队首和队尾进行操作。 三、队列 排队的队伍在计算机中称为队列，队列是一种只能在表的首端取出数据，在表的尾端添加数据的线性表，即队列是操作上有限制的线性表，队列是一种先进先出数据结构。 队列的抽象数据类型表示如下： ADT Queue 数据对象：D={ ai｜ai ∈ ElemSet,i=1,2,…,n,n>=0} 数据关系：R={
｜ai-1,ai∈D,i=2,…,n} 基本操作: def_init_(self) #初始化一个空队列 def QEmpty(self) #若队列空，则返回True,否则返回 False def QLength(self) #返回队列的元素个数 def GetHeac(self) #返回队列的队头元素 def EnQueue(self.e) #e元素进队 def OutQueue(self) #元素出队 队列有两种存储方式，一种是用数组存储，这种方式存储的队列称为顺序队列；另一种用链表存储，这种方式存储的队列称为链队列，如图3-4所示。元素插入队尾称为进队队首元素取出称为出队。队首用front指针指示，队尾用rear指针指示。 图3-4链队列 用数组存储队列元素时，会遇到指针溢出问题。即当队满时，再有元素进队，就会 ... ... 