项目四 探索电子排队预定功能的实现-队列的应用-高中信息技术同步精品课堂（沪科版2019选择性必修1）

项目四探索电子排队预定功能的实现 — 队列的应用 01 02 03 熟练使用python 程序设计算法使用队列数据结构完成预定程序。 了解电子排队预订系统，并理解排队预定遵循的规律。 学习目标 知道队列的定义，并掌握队列遵循的原则。 01 问题导入 导入 日常生活中，商品和服务需求大于供给的情况时有发生，例如限量商品发售、医院专家门诊号等。为了避免商场、医院或营业厅里人潮拥挤，等候的客户排起长龙，一些企事业单位在相应网站或手机 App 上提供了预约服务，如图 3-1 所示。客户输入身份、账号信息提交后自动进入电子排队预订系统。你知道电子排队预订系统是如何实现排队预约的吗？ 图 3-1 电子排队预订系统 1. 分析问题 电子排队预订系统是计算机自动控制的排队系统，排队的特点是先来先服务，那计算机是怎么实现自动排队的呢？当客户在电子排队预订系统提交信息后，客户的预订数据就进入队列，称为进队（也称入队），即在队尾（rear）插入一个客户账号数据；当正式购买商品时就到队列中取出客户账号数据，称为出队，即在队首（front）取出一个客户账号数（客户账号数据暂用 A0001 形式替代），如图 3-2 所示。 图 3-2 预订—购买队列 用先进先出的数据结构来存储排队的客户账号数据，就可以方便地实现先来先服务，这种数据结构称为队列。 活 动 4.1 假设排队预订客户账号数据为 A0001、A0002、A0003、A0004，下面空的队 列中依次 A0001 进队，A0002 进队，A0003 进队，叫号出队，A0004 进队，叫号出队， 叫号出队，叫号出队，画出队列的变化过程。 4.2 请尝试写出队列的抽象数据类型定义。 排队预订的队列变化过程如图 3-3 所示（为图示方便，暂定图中队列空间只有 4 个）。客户预订即为进队，假设A0001 表示第一个客户账号数据，购买即为队首出队。图中 rear 指向队列的尾端，图中 front 指向队列的首端。 队列在计算机里怎样表示呢？队列是操作上有限制的线性表，既可以用数组表示一个队列，也可以用链表表示一个队列。一般若问题规模已知，即总的进队元素个数已知的话，队列可以用顺序存储结构存储，即用数组表示队列；若进队元素个数无法预计，则队列可以用链式存储结构存储，即用链表表示队列。 2. 设计算法 根据上述算法，可以利用学过的编程知识来编程实现排队预订。首先要定义队列的类型并进行初始化（即置空）操作，指针变量要设定初始值。用列表表示队列的类型定义如下： class SqQueue: def __init__(self, size): # 队列初始化 self.size =size # 定义队列长度 self.queue = [ ' ' ]*size # 存储队列元素的列表 self.front=0 # 头指针 self.rear=0 # 尾指针 self.number=0 # 计数器 3. 程序实现 4.4 打开配套资源中“循环顺序队列 .py”程序，补充完整以下代码，并进行运行测试，模拟实现排队预订功能。 def EnQueue(self,e): # 进队程序 if(self.number==self.size): print（ " 队满，不能进 " ） else: self.queue[self.rear]=e self.number=self.number+1 def OutQueue(self): # 出队程序 if self.number==0: print（" 队空 "） return -1 else: e = self.queue[self.front] self.number=self.number-1 return e 活 动 02 知识链接 排队的队伍在计算机中称为队列，队列是一种只能在表的首端取出数据，在表的尾端添加数据的线性表，即队列是操作上有限制的线性表，队列是一种先进先出数据结构。队列的抽象数据类型表示如下： 1.队列 队列有两种存储方式，一种是用数组存储，这种方式存储的队列称为顺序队列；另一种用链表存储，这种方式存储的队列称为链队列，如图 3-4 所示。元素插入队尾称为进队，队首元素取出称为出队。队首用 front 指针指示，队尾用 rear 指针指示。 用数组存储队列元素时，会遇到指针溢出问题。即当队满时，再有元素进队，就会产生指针的溢出（上溢出）；当队空时，再要取出元素，也会产生指针的溢出（下溢出）。另外，还有“假溢出”问题。随着元素的进队和出队，整个队列是向数组下标较大的位置移动。当移动到数组中下标最大的位置后，队列的空间就用尽了。此时，即使数组下