选修1 数据与数据结构4.1 队列结构及其实现课文课件ppt

这是一份选修1 数据与数据结构4.1 队列结构及其实现课文课件ppt，共24页。PPT课件主要包含了任务一体验排队买票等内容，欢迎下载使用。
第4单元 队列及其应用
队列是一种操作受限的线性结构，数据元素只能在一端进，在另一端出，且具有“先进先出”的特征。 队列出现在日常生活各类“排队”活动中，如影院排队入场、商店排队付款和餐厅排除就餐就时都会形成队列。另外，计算机科学中的很多功能，如打印队列、进程调度和键盘缓冲等也都是利用队列结构来实现的。 1.本单元通过“排队买票”项目，理解队列结构的基本概念及特征，学习队列的两种实现方法 2.通过“基数排序”和“餐馆排队取号模拟系统”项目学习并亲历利用队列解决问题的一般方法和过程，体验迭代思想在问题解决中的应用。
4.1队列结构及其实现4.2基数排序4.3排队取号模拟系统
4.1队列结构及其实现
日常生活中，同学们都有哪些排队的经历？
1.食堂排队买饭2.电影院排队买票3.超市排队结账…………
排队的过程会形成一个队列，排在队列最前面的优先处理，后来的必须排在队尾。 计算机在解决问题的过程中也经常会用到队列。
1.理解队列的概念及特征。2.掌握队列抽象数据类型的定义。3.掌握队列的两种实现方法。
队列（queue）是一种操作受限制的线性结构，只允许在表的前端（队首）进行数据元素删除操作，在表的后端（队尾）进行插入操作。 在队列中插入一个数据元素称为入队，从队列中删除一个数据元素称为出队。因为队列只允许在队尾插入、在队首删除，所以先进入队列的元素先从队列中删除，故队列又称为先进先出（First In First Out,FIFO）线性表。
如果我们将排队买票的 人抽象成一个数据元素a，那么排队买票的队列可以用图4.1.2表示。
根据图4.1.2所示，分析排队买票的情况，完成以下问题。（1）购票的行为发生在队列的 ；完成购票的人离开队列后，队列有什么变化？（2）新来的买票人排在队列的 ；购票的人增加后，队列有什么变化？
活动1 认识生活中的队列
活动2 观察排队买票
暑假期间，小明担任了天文馆售票处的志愿者工作，工作内容是维持游客的买票秩序，在开始售票前后的一段时间内（7：50~8：00），他观察到排队买票的队列发生了以下变化。
（1）7：50，售票窗口前没有人排队。
（2）7：55，售票窗口前有5个人（用p1,p2,p3,p4,p5表示）依次在排队。
（3）8：00，开始售票，有3个人（p1,p2,p3）陆续买票离开，又来了4个人（p6,p7,p8,p9）依次排入队中。
根据上述观察，思考并回答下面的问题。（1）最先进入队列的是 。（2）p3买完票离开后，排在队首的人是 ，队列里有 个人在排列。
p1,p2,p3,p4,p5
为了在程序中使用队列结构来解决问题，我们需要定义队列数据类型（ADT Queue）。根据问题解决需要，我们为队列数据类型定义了如下接口。
ADT Queue:Queue():创建一个空队列，返回值是一个空的队列。enQueue(item):将数据元素item添加到队尾，无返回值。deQueue():从队首删除数据元素，返回队首数据元素。size():返回队列中数据元素的个数。isEmpty():判断是否为空队列，返回布尔值。
活动3 实现排队买票
有了队列抽象数据类型，我们就可以用程序来实现买票人的入队、出队以及统计排队人数的操作了。 假设有5个人（用p1,p2,p3,p4,p5表示）依次前来排队买票，完成排队买票的过程如下。 根据操作描述补全代码。
任务二 编程实现排队买票
活动1 用顺序存储实现队列
队列抽象数据类型主要包括创建队列、入队、出队、统计队列数据元素个数、判断队列是否为空等操作接口。队列的顺序存储实现，可以用Pythn列表数据类型来实现。
（1）创建队列创建空队列，就是建立一个空的列表，用属性items来保存队列中的数据元素。请补全下面的代码。
class Queue(): def __init__(self): #创建队列 self.items = [ ] # 空列表
def enQueue(self, item): # 入队 (item) # 队尾增加一个数据元素
(2)入队 入队操作就是在列表items的最后添加一个新的数据元素item。例如，p6入队的过程如图4.1.3所示。
（3）出队出队操作就是移除并返回列表items中的第一个数据元素。例如，p1出队的过程如图4.1.4所示。
def deQueue(self): # 出队 return (0) # 移除队首元素并返回移除后的队首数据元素 def size(self): return len(self.items) # 返回队列的数据元素个数 def isEmpty(self): return self.items == [] # 返回队列是否为空的判断值
活动2 用链式存储实现队列
除了利用顺序存储实现队列以外，还可以使用另一种方法——基于节点引用的链表方式。 （1）创建空队列 创建空队列，也可以称为队列的初始化，将队首节点引用和队尾节点引用都指向空，如图4.1.5所示。
class Queue(): def __init__(self): self.head = Nne #队首指向空节点 self.rear = Nne #队尾指向空节点
(2)入队 入队操作就是在链表的队尾插入一个节点。例如，p5入队的过程如图4.1.6和图4.1.7所示。
def enQueue(self, item): # 将元素item加入队列，入队 p = Nde(item) # 生成节点 if self.head == Nne: # 判断队首节点是否为空 self.head = p #队首指向新节点 self.rear = p #队尾指向新节点 else: tp = self.rear tp.next = p #队首指向新节点 self.rear = p #队尾指向新节点
(3)出队 出队操作就是在链表的首端删除一个节点，修改头节点引用。例如，p1出队的过程如图4.1.8所示。
def deQueue(self): # 删除队首元素，出队 if self.head == Nne: return Nne result = # 获取队首节点数据元素 self.head = # 重新设置头节点 return result # 返回节点数据
(4)统计队列数据元素个数 统计队列数据元素个数，就是要遍历链表中的每一个节点。
def size(self): # 统计队列的数据元素个数 current = self.head # 获取到头节点 cunt = 0 # 初始化数据元素个数统计变量 while current != Nne: # 判断当前节点不为空节点 cunt = cunt + 1 # 数据元素个数增加一个 current = current.next # 获取下一个节点 return cunt # 返回队列的数据元素个数
(5)判断队列是否为空
def isEmpty(self): # 判断队列是否为空 return self.head == Nne
队列是一种要求先进先出的数据结构，需要在表的一端插入数据元素，在另一端删除数据元素。 用列表实现队列存在两种情况：一种情况是队首放在列表头；另一种情况是队首放在列表尾。两种不同的情况，在实现入队和出队的操作中也存在差别，如表4.1.1所示。
frm queue imprt Queue #导入队列ticketLine=Queue() #创建队列对象ticketLine.enQueue("小明") #小明入队ticketLine.enQueue("小梅") #小梅入队ticketLine.deQueue()#小明出队print(ticketLine.size()) #显示当前排队总人数