中小学教育资源及组卷应用平台
第三单元
特殊的线性表
项目五
模拟实现软件的撤消功能
——栈的应用
第一课时
分析问题
?教材分析
本节的主要内容是分析问题。通过以模拟实现软件的撤消功能为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课时是从“撤消字符操作”的实例中分析出后输入的字符先撤消的思想方法，将这一思想方法图形化后，引出另一种受限制的线性结构——“栈”的概念，并通过活动帮助学生加深理解。在这一课时过程中，进一步培养学生的信息意识和计算思维。
?教学目标
1.理解栈的概念和特征；
2.理解栈顶指针的作用；
2.培养学生的信息意识和计算思维能力。
?教学重点
1.理解栈的概念和特征。
?教学难点
1.理解栈的概念和特征。
2.培养学生的信息意识和计算思维能力。
?教学方法
体验法、讲授法、讨论法、示例法
?教学准备
计算机教室、多媒体设备、多媒体广播软件、教学课件、Python编程环境、学生上机练习的程序文件，预先编制的Python程序文件等。
?教学过程
一、新课导入
队列是一种操作受限制的线性表，只允许先进先出。还有一种操作受限制的线性表，即栈，它的特点和队列恰好相反，是后进先出。日常学习和工作中，人们使用的许多应用软件，如办公软件大多提供了“撤消”功能。该功能允许用户撤消有限的操作步骤，方便恢复到误操作之前的状态(图3-6)。而这一功能就可以借助栈来实现。
二、分析问题
要实现撤消功能，首先要思考操作的顺序问题。例如，输入
abcde的操作顺序是先输入a,然后是b,再是c……而撤消的时候是按逆序，先撤消e,再撤消d……可以看出，后输入的先撤消，先输入的后撤消，如图3-7所示。
如果用某种后进先出的数据结构来键入a存储a,b,c,d,e的话，可以方便地实1操作现撤消。这种数据结构称为栈。
图3-7撤消菜单
思考与讨论
生活中是否还有其他类似的后进先出的例子？
弹匣装子弹；“QQ音乐”在顺序播放模式下，最后选入播放列表的歌曲第一个播放，第一个进入列表的最后个播放等。
三、栈
核心概念
栈(
stack)：是一种仅允许在表的一端进行插入或删除操作的线性表。这一端被称为栈顶(top)，栈也称为后进先出(
last
in
first
out,LIFO)线性表。
小贴士
栈属于线性表的一种，是操作上有限制的线性表，只允许在栈顶进行操作。
要理解栈这个概念，首先要明白“栈”这个字的字面意思，如此才能把握本质。“栈”的意思是存储货物或供旅客住宿的地方，可引申为仓库、中转站，所以引入到计算机领域里就是指数据暂时存储的地方，是一种只能在表的一端进行插入(进栈或人栈)和删除(出栈或是退栈)操作的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后进去的一个数据被第一个读出)。日常生活中有很多后进先出的例子，如碗柜里的一叠碗(图3-10)，先放进去的在下面，后放进去的在上面，取碗时只能从上面开始取，即先取到的是最后放上去的；又如冰糖葫芦串(图3-11)，先串进去的冰糖葫芦在下面，后串进去的冰糖葫芦在上面，吃的时候通常是后串进去的冰糖葫芦先吃到，而先串进去的冰糖葫芦后吃到。
图3-10碗柜里的碗
图3-11冰糖葫芦串
栈的抽象数据类型表示如下：
ADT
Stack：
数据对象：D={ai｜ai,∈
ElemSet,i=l,2,…,n,n>=0}
数据关系：R={ai-1,ai>｜ai-1,ai
∈
D,i=2,…,n}
#an为栈顶
基本操作：
def
_init_(self)
#初始化一个空栈
def
SEmpty(self)
#若栈空，则返回True,否则返回False
def
GetTop(self)
#返回栈的栈顶元素
def
Push(self,
e)
#e元素进栈
def
Pop(self)
#返回出栈元素
栈有两种存储方式，一种是用数组存储，这种方式存储的栈称为顺序栈；另一种用链表存储，这种方式存储的栈称为链式栈。一般根据进栈元素个数是否确定来选择存储结构，元素个数确定的用顺序栈，不确定的用链式栈。
四、课堂活动
1.请尝试写出栈的抽象数据类型定义。
2.网上搜索列车调度方法，根据图3-8画出用栈进行调度的过程示意图，并说
明调度的原理。
图3-8列车调度示意
参考答案：
1.
ADT
Stack：
数据对象：D={ai｜ai,∈
ElemSet,i=l,2,…,n,n>=0}
数据关系：R={ai-1,ai>｜ai-1,ai
∈
D,i=2,…,n}
#an为栈顶
基本操作：
def
_init_(self)
#初始化一个空栈
def
SEmpty(self)
#若栈空，则返回True,否则返回False
def
GetTop(self)
#返回栈的栈顶元素
def
Push(self,
e)
#e元素进栈
def
Pop(self)
#返回出栈元素
2.
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://21世纪教育网(www.21cnjy.com)
"
21世纪教育网(www.21cnjy.com)(共24张PPT)
第一课时
分析问题
信息技术沪教版
选择性必修1
第三单元
特殊的线性表
项目五
模拟实现软件的撤消功能
——栈的应用
一、新课导入
二、分析问题
三、栈
四、课堂活动
一、新课导入
队列是一种操作受限制的线性表，只允许先进先出。还有一种操作受限制的线性表，即栈，它的特点和队列恰好相反，是后进先出。日常学习和工作中，人们使用的许多应用软件，如办公软件大多提供了“撤消”功能。
该功能允许用户撤消有限的操作步骤，方便恢复到误操作之前的状态。而这一功能就可以借助栈来实现。
二、分析问题
要实现撤消功能，首先要思考操作的顺序问题。例如，输入abcde的操作顺序是先输入a，然后是b,再是c……而撤消的时候是按逆序，先撤消e，再撤消d……可以看出，后输入的先撤消，先输入的后撤消，如图所示。
思考与讨论
生活中是否还有其他类似的后进先出的例子？
思考与讨论
弹匣装子弹；“QQ音乐”在顺序播放模式下，最后选入播放列表的歌曲第一个播放，第一个进入列表的最后个播放等。
三、栈
栈(
stack)：是一种仅允许在表的一端进行插入或删除操作的线性表。这一端被称为栈顶(top)，栈也称为后进先出(
last
in
first
out,LIFO)线性表。
核心概念
栈属于线性表的一种，是操作上有限制的线性表，只允许在栈顶进行操作。
要理解栈这个概念，首先要明白“栈”这个字的字面意思，如此才能把握本质。“栈”的意思是存储货物或供旅客住宿的地方，可引申为仓库、中转站，所以引入到计算机领域里就是指数据暂时存储的地方，是一种只能在表的一端进行插入(进栈或人栈)和删除(出栈或是退栈)操作的线性表。
它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后进去的一个数据被第一个读出)。
日常生活中有很多后进先出的例子，如碗柜里的一叠碗，先放进去的在下面，后放进去的在上面，取碗时只能从上面开始取，即先取到的是最后放上去的；
日常生活中有很多后进先出的例子，又如冰糖葫芦串，先串进去的冰糖葫芦在下面，后串进去的冰糖葫芦在上面，吃的时候通常是后串进去的冰糖葫芦先吃到，而先串进去的冰糖葫芦后吃到。
栈的抽象数据类型表示如下：
ADT
Stack：
数据对象：D={ai｜ai,∈
ElemSet,i=l,2,…,n,n>=0}
数据关系：R={ai-1,ai>｜ai-1,ai
∈
D,i=2,…,n}
#an为栈顶
基本操作：
def
_init_(self)
#初始化一个空栈
def
SEmpty(self)
#若栈空，则返回True,否则返回False
def
GetTop(self)
#返回栈的栈顶元素
def
Push(self,
e)
#e元素进栈
def
Pop(self)
#返回出栈元素
栈的两种存储方式
用数组存储，这种方式存储的栈称为顺序栈
顺序栈
用链表存储，这种方式存储的栈称为链式栈
链式栈
一般根据进栈元素个数是否确定来选择存储结构，元素个数确定的用顺序栈，不确定的用链式栈。
课堂活动
1.请尝试写出栈的抽象数据类型定义。
2.网上搜索列车调度方法，根据图3-8画出用栈进行调度的过程示意图，并说明调度的原理。
图3-8列车调度示意
ADT
Stack：
数据对象：D={ai｜ai,∈
ElemSet,i=l,2,…,n,n>=0}
数据关系：R={ai-1,ai>｜ai-1,ai
∈
D,i=2,…,n}
#an为栈顶
基本操作：
def
_init_(self)
#初始化一个空栈
def
SEmpty(self)
#若栈空，则返回True,否则返回False
def
GetTop(self)
#返回栈的栈顶元素
def
Push(self,
e)
#e元素进栈
def
Pop(self)
#返回出栈元素
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php
