5.1《栈结构及其实现》

5.1栈结构及其实现 高中信息技术/教科版/选择性必修1 目录 1.引入与车辆调度探究 2.问题抽象：栈及其ADT 3.课堂实践，实现栈数据类型 4.课堂小结 1.引入与车辆调度探究 同学们，上一单元我们学习了一种数据结构——队列，它有什么特点？ 队列是一种受限的线性结构。它只能在一端添加元素，而在另一端只能删除元素，添加元素叫入队，删除元素叫出队。 对线性表的操作限制可不仅只有这一种，我们再来考察另外一种。一条单行道，因为突发原因堵车了。请大家阅读教科书第 124 页至第 127 页的内容，并完成教科书上的问题。 任务一体验单行道车辆调度 活动1记录车辆停放信息 道路被大树堵塞后，交通协管员被立即派往新华路负责疏散车辆和行人。通过查看道路监控录像得知，大树倒下的时间大概为早上8点，车牌号为A101的黄色轿车8:05驶入新华路，2分钟后车牌号为B102的绿色轿车停靠在黄色轿车后面，随后车牌号为 C102的蓝色轿车8:08驶入新华路，2分钟后红色轿车D102停靠在其后。 图5.1.1 新华路交通状态 任务一体验单行道车辆调度 活动1记录车辆停放信息 根据轿车停放时间的先后顺序，完成图5.1.2。 填一填 图5.1.2 新华路车辆信息1 C102 D102 任务一体验单行道车辆调度 活动2根据路况更新车辆停放信息 红色轿车司机等了半个小时后，还是不见前方车辆有启动的迹象，便于8:40倒车驶回主路，选择其他路线。请用笔画掉已驶出的车辆，更新图5.1.2中的信息，得出图5.1.3。 图5.1.3 新华路车辆信息2 C102 D102 任务一体验单行道车辆调度 活动2根据路况更新车辆停放信息 8:42分在主路行驶的车牌号为E201的黑色轿车进入新华路，减速慢行后停在蓝色轿车后面。请根据新华路路况更新图 5.1.4。 图5.1.4新华路车辆信息3 C102 E201 栈是一种出入有序的数据集合。作为一种操作受限的线性结构，数据元素的插入和删除都仅发生在同一端，这一端为栈顶 ( Top)，相应地，另一端则为栈底(Bottom)。数据元素的插入操作一般称为入栈(Push)，又称进栈;删除操作则称为出栈(Pop)，又称退栈。 栈的概念 2.问题抽象：栈及其ADT 任务一体验单行道车辆调度 活动3新华路车辆调度操作 交通协管员被告知事故现场短时间内无法清理完毕，建议出行者选择其他的行车路线。与四位司机沟通后，他们选择规划新路线去往目的地。下一步新华路上的车辆该如何进行指挥调度呢? 请填写下面的车辆调度信息。 第一步:车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，下一辆即将驶出的轿车车牌号为 . 第二步车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，下一辆即将驶出的轿车车牌号为 . E201 4 C102 C102 2 B102 任务一体验单行道车辆调度 活动3新华路车辆调度操作 请填写下面的车辆调度信息。 第三步:车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，下一辆即将驶出的轿车车牌号为 . 第四步车牌号为 的轿车倒车驶出新华路，这时新华路还停有 辆轿车，道路已被清空。 分析以上调度过程，思考并回答下面的问题。 (1) 最早驶入新华路的车辆为 ，最晚驶出新华路的车辆 . (2)最晚驶入新华路的车辆为 ，最早驶出新华路的车辆 . A101 1 B102 A101 0 A101 A101 E201 E201 任务一体验单行道车辆调度 活动3新华路车辆调度操作 数据元素入栈和出栈的次序正好相反并且所有操作都是对栈顶数据元素进行。距离栈底越近的数据元素，留在栈中的时间就越长，而最新加入栈的数据元素会被最先移除，这种特点通常称为“后进先出”，即Last InFirst Out，简称LIFO。 栈的特征 任务一体验单行道车辆调度 活动3新华路车辆调度操作 栈抽象数据类型的接口如下。 ADT Stack: Stack0:创建并返回一个不包含任何数据元素的空栈 push(item):将数据元素item压入栈顶，无返回值。 pop( ):弹出并返回栈顶的数据元素。 peek( ):查看、返回但不移除栈顶的数据元素·isEmpty0:判断是否为空栈，返回布尔型的值; size( ):计算并返回栈中数据元素的个数。 栈抽象数据类型 任务一体验单行道车辆调度 活动4实现车辆调度过程 了解了栈抽象数据类型的基本操作，我们可以利用栈来实现新华路车辆调度过程。用车牌号来表示轿车，补全下面的代码。 01.s=Stack( ) #建栈类的实例s 02.s.push("A101") #车牌号为A101的黄色轿车入栈s 03. #车牌号为B102的绿色轿车人栈s 04. #车牌号为C102的蓝色轿车入栈s 05. #车牌号为D102的红色轿车入栈 s 06. #查看栈中轿车数量 07. #车牌号为D102的红色轿车出栈s s.push("B102") s.push("C102") s.push("D102") print (s.size( )) s.pop( ) 任务一体验单行道车辆调度 活动4实现车辆调度过程 了解了栈抽象数据类型的基本操作，我们可以利用栈来实现新华路车辆调度过程。用车牌号来表示轿车，补全下面的代码。 08. #查看栈顶是什么轿车 09. #车牌号为E201的黑色轿车入栈s 10. #车牌号为E201的黑色轿车出栈s 11. #车牌号为C102的黑色轿车出栈s 12. #车牌号为B102的黑色轿车出栈s 13. #车牌号为A101的黑色轿车出栈s 14. #查看是否为空栈 print (s.peek( )) s.push("E201") s.pop( ) s.pop( ) s.pop( ) s.pop( ) print (s.isEmpty( )) 3.课堂实践，实现栈数据类型 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈 栈抽象数据类型主要包括创建栈、入栈、出栈、判断栈是否为空、查看栈顶数据元素和返回栈中数据元素个数。用Python内置的数据类型列表来实现栈的操作如下所示。 (1)创建空栈。 创建空栈，就是建立一个空的列表，用items来保存栈中的数据元素。 01.#创建stack类 02. class Stack: 03.def __init__(self): #栈初始化为空列表 04.self.items=[] 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈 (2)判断栈是否为空。 05.def isEmpty(self): #判断是否为空栈 06.return self.items==[] (3)入栈 入栈就是在栈顶 (列表末尾) 加入新的数据元素。例如，车牌号为F201的轿车驶入单行道。请补全下面的代码。 07.def push(self，item): #入栈操作 08.self .items. . append(item) 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈 (2)判断栈是否为空。 05.def isEmpty(self): #判断是否为空栈 06.return self.items==[] (3)入栈 入栈就是在栈顶 (列表末尾) 加入新的数据元素。请补全下面的代码。 07.def push(self，item): #入栈操作 08.self .items. . append(item) 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈 (4)出栈 出栈是将栈顶数据元素弹出并返回。 09.def pop(self): 10.if self.isEmpty(): 11.return self.items 12.else: 13.return self.items . .pop() 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈 (5) 查看栈顶数据元素 列表的最后一项即为栈顶数据元素。请补全下面的代码。 14.def peek(self): #查看栈顶数据元素 15.if self.isEmpty(): 16.return self.items 17.else: 18.return self.items[ ] -1 (6)计算并返回栈中数据元素的个数 19.def size(self): 20.return len(self.items) #返回栈中数据元素的个数 任务二 编程实现单行道车辆调度 活动1用顺序存储实现栈 将实现栈抽象数据类型顺序存储的代码输入到文件中，保存为stack.py,利用单行道车辆调度测试各个接口的效果。请补全下面的代码。 01. from stack import Stack #导入栈类 02.s= #创建栈对象 03.s.push("A101") #车牌号为A101的轿车驶入单行道 04. #车牌号为B102的轿车驶入单行道 05. #车牌号为B102的轿车驶出单行道 06. print( )#显示当前单行道车辆总数 Stack () s.push("B102") s.pop( ) s.size( ) 栈的列表实现可以将列表的任意一端 (index=0 或者-1)设置为栈顶，上面的活动我们选用列表的末端(idex=-1)作为栈顶，栈的操作通过列表的append和pop方法实现。 若选用列表的首端(index=0)为栈顶，则栈的操作需要用列表的insert和pop 方法来实现。 栈的顺序存储实现 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈 根据链表的特征分析链表实现栈的基本操作并补全下面的代码。 (1)创建空栈。 栈的初始化，栈顶节点引用为空。 01.class Stack: #创建栈类 82.def __init__(self): 03.self.head=None #栈初始化为空链表 (2)判断栈是否为空 通过判断栈顶节点引用是否指向空来判定栈是否为空 04..def isEmpty(self): #判断栈是否为空 05return self.head==None 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈 (3)入栈操作。 入栈的链表实现是通过在栈顶加入新节点完成的。例如，车牌号为E201的轿车驶入单行道，如图所示 新栈顶 原栈顶 栈底 06. def push(self，item): #入栈 07.temp=Node(item) #生成新节点 08. #新节点引用指向原栈顶节点 09.self.head=temp #栈顶节点引用指向新节点 temp.next=self.head 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈 (4)出栈操作。 出栈的链表实现是通过弹出栈顶节点完成的。例如，车牌号为E201的轿车驶出单行道，如图所示。请补全下面的代码。 原栈顶 新栈顶 栈底 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈 10.def pop(self): #出栈 11.if self.isEmpty(): #判断栈是否为空 12.print("Can't pop from empty stack.") 13.else: 14.temp=self.head.data #保存原栈顶节点数据元素 15. #栈顶节点引用指向下一个节点 16.return temp #返回原栈顶节点数据元素 self.head=self.head.next 任务二 编程实现单行道车辆调度 活动2用链式存储实现栈 (5) 查看栈顶数据元素 17.def peek(self): #查看栈顶数据元素 18.if not self.isEmpty(): 19.return self.head.data (6)查看栈中数据元素的个数。 20.def size(self): #查看栈中数据元素的个数 21.count=0 22.index=self.head 23.while index!=None: #判断节点是否为空 24.count+=1 25.index=index.next 26.return count 栈的另一种实现方式是基于节点引用的链式存储方式。数据元素被存放在节点对象中，每个节点对象除了拥有存储数据元素的数据域外，还包括对下个节点的引用。显然，当节点为栈底时，引用为空。 栈的链式存储实现 6.课堂小结 本节课我们学习了栈的抽象数据类型的定义、栈的顺序存储和链式存储两种实现方法。作为只在同一端进行数据元素的插入和删除操作的特殊线性结构栈的操作并不会发生大量的数据移动。 作业布置：请同学们认真完成教材中的拓展练习哦！ 下节课见！ $$