4.1《队列结构及其实现》

4.1队列结构及其实现 高中信息技术/教科版/选择性必修1 目录 1.情景导入， 引入新课 2.体验活动，初识队列 3.探究队列抽象数据类型及其应用 4.用顺序存储实现队列 5.用链式存储实现队列 6.课堂小结 1.情景导入，引入新课 ”利用假期时间去游览祖国各地的名读万卷书，行万里路。'胜古迹，既可以放松紧张的心情，又可以学到很多知识。在旅游风景区，排队是不可避免的现象。 本节围绕“排队买票”项目展开学习，通过项目活动认识生活中的队列，学习利用抽象数据类型定义队列，编写代码实现队列的基本操作。本节主要包含“体验排队买票”和“编程实现排队买票”两个任务。 2.体验活动，初识队列 任务一体验排队买票 活动1认识生活中的队列 如果我们将排队买票的人抽象成一个数据元素 a，那么排队买票的队列可以用图4.1.2表示。 队首 队尾 a1 a2 a3 …… an 图4.1.2 排队买票 任务一体验排队买票 活动1认识生活中的队列 根据图4.1.2所示，分析排队买票的情况，完成以下问题。 (1)购票的行为发生在队列的 ， 完成购票的人离开队列后，队列有什么变化? (2)新来的买票人排在队列的 购票的人增加后，队列有什么变化? 填一填 队首 队尾 队列是一种操作受限制的线性结构，只允许在表的前端(队首)进行数据元素删除操作，在表的后端(队尾)进行插入操作在队列中插入一个数据元素称为入队，从队列中删除一个数据元素称为出队。因为队列只允许在队尾插入、在队首删除，所以先进入队列的元素先从队列中删除，故队列又称为先进先出线性表。 队列 3.探究队列抽象数据类型及其应用 任务一体验排队买票 活动2观察排队买票 (1)7:50，售票窗口前没有人排队。 (2)7:55，售票窗口前有5个人(用p1，p2，p3，p4，p5表示)依次在排队。 (3)8:00，开始售票，有3个人 (pl，p2，p3) 陆续买票离开又来了4个人 (p6，p7，p8，p9) 依次排入队中 根据上述观察，思考并回答下面的问题。 (1) 最先进入队列的是 . (2)p3买完票离开后，排在队首的人是 ，队列里有 个人在排队。 p1 p4 6 任务一体验排队买票 活动2观察排队买票 ADT Queue: Queue（）：创建一个空队列，返回值是一个空的队列。 enQueue(item)：将数据元素item添加到队尾，无返回值 deQueu（）：从队首删除数据元素，返回队首数据元素 siz（）：返回队列中数据元素的个数。 isEmpty（）：判断是否为空队列，返回布尔值 队列抽象数据类型 任务一体验排队买票 活动2观察排队买票 假设有5个人 (用p1，p2p3，p4，p5表示) 依次前来排队买票，完成排队买票的过程如下。请根据操作描述补全下面的代码。 01. ticketLine=Queue( ) #创建空队列 02.ticketLine.enQueue(p1) #p1入队 03.ticketLine.enQueue(p2) #p2入队 04. . #p3入队 05. . #p4入队 06. . #p5入队 ticketLine.enQueue(p3) ticketLine.enQueue(p4) ticketLine.enQueue(p5) 任务一体验排队买票 活动2观察排队买票 假设有5个人 (用p1，p2p3，p4，p5表示) 依次前来排队买票，完成排队买票的过程如下。请根据操作描述补全下面的代码。 07.ticketLine.deQueue( ) #p1出队 08.ticketLine.deQueue( ) #p2出队 09.num=ticketLine.size( ) #统计当前排队人数 10. #p3出队 11. #p4出队 12. #p5出队 13. #查看队列是否为空 ticketLine.deQueue( ) ticketLine.deQueue( ) ticketLine.deQueue( ) ticketLine.deQueue( ) 4.用顺序存储实现队列 任务二 编程实现排队买票 活动1用顺序存储实现队列 队列抽象数据类型主要包括创建队列、入队、出队、统计队列数据元素个数、判断队列是否为空等操作接口。队列的顺序存储实现可以用Python列表数据类型来实现。 (1)创建队列。 创建空队列，就是建立一个空的列表，用属性items 来保存队列中的数据元素。请补全下面的代码。 01. class Queue: 02. def __init__(self): #创建队列 03.self.items= #空列表 [ ] 任务二 编程实现排队买票 活动1用顺序存储实现队列 (2) 入队。 入队操作就是在列表items的最后添加一个新的数据元素item。例如，p6入队的过程如图4.1.3 所示。 p1 p2 p3 p3 p4 p5 队首 原队尾 新队尾 根据图4.1.3 所示，补全enQueue方法的实现代码。 04.def enQueue(self,item): #入队 05.self.items.append( ）#队尾增加一个数据元素 图4.1.3 p6入队 item 任务二 编程实现排队买票 活动1用顺序存储实现队列 (3)出队。 出队操作就是移除并返回列表items中的第一个数据元素。例如，p1出队的过程如图4.1.4所示。 p1 p2 p3 p3 p4 p5 原队首 队尾 根据图4.1.4所示，补全deQueue方法的实现代码 06.def deQueue(self): #出队 07.return self.items .pop( ）#移除队首元素并返回 图4.1.4 p1出队 新队首 0 任务二 编程实现排队买票 活动1用顺序存储实现队列 （4）统计队列数据元素个数。 08.def size(self): 09.return len(self.items) #返回队列的数据元素个数 (5)判断队列是否为空。 10.def isEmpty(self): 11.return self.items==[] #返回队列是否为空的判断值 任务二 编程实现排队买票 活动1用顺序存储实现队列 队列是一种要求先进先出的数据结构，需要在表的一端插入数据元素，在另一端删除数据元素。用列表实现队列存在两种情况:一种情况是队首放在列表头;另一种情况是队首放在列表尾。两种不同的情况，在实现入队和出队的操作中也存在差别，如表所示。 列表实现的不同方案 任务二 编程实现排队买票 活动1用顺序存储实现队列 将队列抽象数据类型的顺序存储实现代码输入到文件中，保存为queue.py，利用排队买票测试各个接口的效果。例如，小明和小梅来排队买票，小明买到票出队，统计当前队列中的排队总人数。请补全下面的代码。 01. from queue import Queue #导入队列 02.ticketLine= #创建队列对象 03.ticketLine.enQueue("小明") #小明入队 04. #小梅入队 05. #小明出队 06.print(ticketLine.size()) #显示当前排队总人数 Queue( ) ticketLine.enQueue("小梅") ticketLine.deQueue( ) 5.用链式存储实现队列 任务二 编程实现排队买票 活动2用链式存储实现队列 (1) 创建空队列。 创建空队列，也可以称为队列的初始化，将队首节点引用和队尾节点引用都指向空，如图4.1.5所示。 图4.1.5 队列初始化 ^ head rear 根据图4.1.5 的提示，补全队列初始化代码。 01. class Queue(): 02.def __init__(self): 03.self.head=None #队首指向空节点 04.self.rear= #队尾指向空节点 None 任务二 编程实现排队买票 活动2用链式存储实现队列 (2) 入队。 入队操作就是在链表的队尾插入一个节点。例如，p5入队的过程如图4.1.6和图4.1.7所示。 p1 p2 p3 p4 ^ rear head 队首 队尾 图4.1.6 插入节点前 p1 p2 p3 p4 rear head 队首 原队尾 p5 ^ 新队尾 图4.1.7 插入节点后 任务二 编程实现排队买票 活动2用链式存储实现队列 根据图4.1.6 和图 4.1.7 的提示，补全enQueue方法的实现代码。 05.def enQueue(self，item): #将元素item加入队列，入队06.p=Node( ) #生成新节点 07.if self.head==None: #判断队首节点是否为空 08.self.head=p #队首指向新节点 09.self.rear= #队尾指向新节点 10.else: 11.tp=self.rear #获取当前队尾节点 12.tp.next=p #当前队尾指向新节点 13.self.rear= #队尾指向新节点 item p p 任务二 编程实现排队买票 活动2用链式存储实现队列 (3)出队。 出队操作就是在链表的首端删除一个节点，修改头节点引用。例如，p1出队的过程如图4.1.8所示。 p1 p2 p3 p4 rear head 原队首 p5 ^ 队尾 新队首 图4.1.8 删除节点 任务二 编程实现排队买票 活动2用链式存储实现队列 根据图4.1.8的提示，补全deQueue方法的实现代码。 14.def deQueue(self): #删除队首元素，出队 15.if self.head==None: #判断队列是否为空 16.return None #返回空 17.result= #获取队首节点数据元素 18.self.head= #重新设置队首节点 19.return result #返回节点数据 self.head.data self.head.next 任务二 编程实现排队买票 活动2用链式存储实现队列 (4)统计队列数据元素个数。 统计队列数据元素个数，就是要遍历链表中的每一个节点，补全size方法的实现代码。 20.def size(self): #统计队列的数据元素个数 21.current=self.head #获取队首节点 22.count= #初始化数据元素个数统计变量 23.while current!=None: #判断当前节点不为空节点 24.count= #数据元素个数增加一个 25.current=current.next #获取下一个节点 26.return count #返回队列的数据元素个数 0 count+1 任务二 编程实现排队买票 活动2用链式存储实现队列 (5)判断队列是否为空。 27.def isEmpty(self): #判断队列是否为空 28.return self.head==None 相对于列表实现而言，利用链表实现队列时，由于链表方式采用了对象引用来表示数据元素之间的关系，使得入队和出队操作更具灵活性。但对于统计队列元素个数，由于需要遍历链表中的每一个节点，其操作效率较低。 6.课堂小结 本节我们学习了队列的基本概念、队列的后抽象数据类型的定义、队列的顺序存储实现方法和链式存储实现方法。 请同学们认真完成教材中的拓展练习哦！ 下节课见！ $$