中小学教育资源及组卷应用平台
第三单元
特殊的线性表
项目四
探索电子排队预订功能的实现
——队列的应用
第一课时
分析问题
?教材分析
本节的主要内容是分析问题。通过以探索电子排队预订功能的实现为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课从分析电子排队预定功能中先来先服务的思想入手，结合活动帮助学生理解队列的概念以及“进队”“出队”。通过本节课的学习能培养学生的信息意识和计算思维能力。
?教学目标
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链队列
用数组存储队列元素时，会遇到指针溢出问题。即当队满时，再有元素进队，就会产生指针的溢出(上溢出)；当队空时，再要取出元素，也会产生指针的溢出(下溢出)。
另外，还有“假溢出”问题。随着元素的进队和出队，整个队列是向数组下标较大的位置移动。当移动到数组中下标最大的位置后，队列空间就用尽了。此时，即使数组下标较小的位置处还有空闲空间，元素也无法进队了，这种现象就叫“假溢出”。
解决以上问题可以有两种方法：一是每次队首元素出队后面的元素都向前移动一次。但这种做法会使出队效率较低。另一种方法是采用循环队列，即把队列的首尾相连，当队尾指针超出数组长度时，就将其设回到最初的队首位置(数组下标为0)。如图3-5所示图中为8个空间的队列形成的循环。为了能实现循环，可以采用指针加1除队列空间数后取余，替代指针加1的方法，即rear=(rear+
1)%size(队尾指针循环)，front(
(front+1)%size(队首指针循环)，其中，%就是取余运算，size为队列的空间数。
图3-5
循环队列
四、课后活动
1.假设排队预订客户账号数据为A001、A002000、A000下面空的队列中依次A0001进队，A0002进队，A003进队，叫号出队，A004进队，叫号出队，叫号出队，叫号出队，画出队列的变化过程。
(2)
(3)
(5)
(6)
2.请尝试写出队列的抽象数据类型定义。
活动答案参考：
1.
2.
ADTQueue：
数据对象：D={ai
｜ai,
∈
ElemSet,
i=1,
2,
3,…,n,
n>=0}
数据关系：R={｜ai-1,ai∈D,i=2,…，n}
基本操作：
def
InitQueue(self)
#建立一个空队列
def
QEmpty(self)
#若空队列，则返回True,否则返回
Flase
def
QLength(self)
#返回队列的元素个数
def
GetHead(self)
#返回队列的队头元素
def
EnQueue(self,e)
#e元素进队
def
OutQueue(self)
#元素出队
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://21世纪教育网(www.21cnjy.com)
"
21世纪教育网(www.21cnjy.com)(共25张PPT)
第一课时
分析问题
信息技术沪教版
选择性必修1
第三单元
特殊的线性表
项目四
探索电子排队预订功能的实现
——队列的应用
一、新课导入
二、分析问题
三、队列
四、课后活动
一、新课导入
电子排队预订系统
日常生活中，商品和服务需求大于供给的情况时有发生，例如限量商品发售、医院专家门诊号等。为了避免商场、医院或营业厅里人潮拥挤，等候的客户排起长龙，一些企事业单位在相应网站或手机App上提供了预约服务，如图3-1所示。客户输入身份、账号信息提交后自动进入电子排队预订系统。你知道电子排队预订系统是如何实现排队预约的吗？
银行
医院
税务
其它
电子排队预订系统
二、分析问题
电子排队预订系统是计算机自动控制的排队系统，排队的特点是先来先服务，那计算机是怎么实现自动排队的呢？
当客户在电子排队预订系统提交信息后，客户的预订数据就进入队列，称为进队(也称人队)，即在队尾(rear)插入个客户账号数据；当正式购买商品时就到队列中取出客户账号数据，称为出队，即在队首(front)取出一个客户账号数据(客户账号数据暂用A0001形式替代)，如图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)
#元素出队
队列有两种存储方式
一种是用数组存储，这种方式存储的队列称为顺序队列
顺序队列
另一种用链表存储，这种方式存储的队列称为链队列
链队列
元素插入队尾称为进队队首元素取出称为出队。队首用front指针指示，队尾用rear指针指示。
用数组存储队列元素时，会遇到指针溢出问题。即当队满时，再有元素进队，就会产生指针的溢出(上溢出)；当队空时，再要取出元素，也会产生指针的溢出(下溢出)。
另外，还有“假溢出”问题。随着元素的进队和出队，整个队列是向数组下标较大的位置移动。当移动到数组中下标最大的位置后，队列空间就用尽了。此时，即使数组下标较小的位置处还有空闲空间，元素也无法进队了，这种现象就叫“假溢出”。
一是每次队首元素出队后面的元素都向前移动一次。但这种做法会使出队效率较低。
另一种方法是采用循环队列，即把队列的首尾相连，当队尾指针超出数组长度时，就将其设回到最初的队首位置(数组下标为0)。
解决以上问题可以有两种方法：
如左图所示图中为8个空间的队列形成的循环。为了能实现循环，可以采用指针加1除队列空间数后取余，替代指针加1的方法，即rear=(rear+
1)%size(队尾指针循环)，front(
(front+1)%size(队首指针循环)，其中，%就是取余运算，size为队列的空间数。
四、课后活动
1.假设排队预订客户账号数据为A001、A002000、A000下面空的队列中依次A0001进队，A0002进队，A003进队，叫号出队，A004进队，叫号出队，叫号出队，叫号出队，画出队列的变化过程。
（1）
（6）
（2）
（3）
（4）
（5）
2.请尝试写出队列的抽象数据类型定义。
2.请尝试写出队列的抽象数据类型定义。
ADTQueue：
数据对象：D={ai
｜ai,
∈
ElemSet,
i=1,
2,
3,…,n,
n>=0}
数据关系：R={｜ai-1,ai∈D,i=2,…，n}
基本操作：
def
InitQueue(self)
#建立一个空队列
def
QEmpty(self)
#若空队列，则返回True,否则返回
Flase
def
QLength(self)
#返回队列的元素个数
def
GetHead(self)
#返回队列的队头元素
def
EnQueue(self,e)
#e元素进队
def
OutQueue(self)
#元素出队
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php