浙教版（2019）高中信息技术 选修1 第3章 3.3.1 栈的概念、特性与基本操作 课件（共26张PPT）

(共26张PPT)
栈（第九课时）
想一想：子弹是如何进出弹匣的呢？它有哪些特点？
栈思想
子弹进出弹匣的过程有下列特点：
①整个装置只有一端开放(最上端)，而且进、出只能在这一端进行。
②弹匣中的子弹成一纵队排列。
③任何子弹进出弹匣的规律是“先进后出、后进先出” 。
栈思想
a4
a3
a2
a1
栈顶
栈底
入栈
出栈
栈的概念
1.栈是一种先进后出的线性表。
2.允许出入、删除的一端称为栈顶，
不能操作的称为栈底。
3.两大特性：
①先进后出，后进先出
②有限序列性
栈思想
生活中还有哪些类似的例子？
栈思想
建栈
top:记录栈顶元素在数组中的位置
栈的基本操作
列表模拟实现
栈思想如何程序实现？
栈的顺序存储结构：利用数组存放元素。
top=-1
st=[“”]*4
3
2
1
0
top
入栈
top
A
top
B
top
C
top
D
栈的基本操作
top+=1
st[top]=“A”
top+=1
st[top]=“B”
top+=1
st[top]=“C”
top+=1
st[top]=“D”
3
2
1
0
top
出栈
A
B
C
D
栈的基本操作
while top>=0:
print(st[top])
top-=1
3
2
1
0
top
思考1：同学们，你能描述出栈的过程吗？
栈的基本操作
1.元素A、C、D、G、K、L、M依次入栈，则不可能的出栈顺序是：
A.CDKGAML B.GDACLMK C.AKGLDMC D.GDLKCAM
答案：B
规律：一个元素出栈后，下一个出栈的元素只能是它已经入栈的相邻元素或者是未入栈的任一个元素。B中的A不可能在C前先出栈。
栈
同学们，栈的思想理解了吗？我们试一试栈的典型应用
栈的典型应用：进制转换
入栈过程:
①top记录栈顶元素在数组中的位置,初始值为-1
②除2取余，若商不为0，余数入栈,商作为新的被除数。
若商为0，余数出栈，输出结果。用栈st存储每次得到
的余数，num存储被除数。
0
1
0
top=0
top=1
top=2
0
1
1
栈的典型应用：进制转换
0
1
0
top=0
top=1
top=2
0
1
1
top=-1
活动1：编写进制转换的程序
栈的典型应用：进制转换
分享：
num=int(input(“输入一个十进制数:"))
sta=[] #空栈
top=-1 #栈顶指针
while num>0: #入栈
a=num%2
sta.append(a)
top+=1
num=num//2
while top>-1: #出栈
print(sta[top],end="")
top=top-1
栈的实践与体验
数学运算表达式在计算机中是如何处理的呢？
例如：3+4*2-7
栈的典型应用
思考2：人是如何计算数学表达式的呢？（完成学习任务单，请描述如何计算）
3
+
4*2
-
7
8
11
4
1.眼睛从左往右扫过表达式
2.发现乘号运算符等级最高，
计算4*2=8
3.比较运算符优先级，计算3+8=11
4.比较运算符优先级，计算11-7=4
实践与体验
思考3：计算机是如何计算表达式的呢？
①.从左到右，逐个遍历算式
3+4*2-7
3
+
4
*
2
-
②.取出运算数3
③.取出运算符+
④.取出运算数4，能不能计算结果
⑤.取出运算符*，比较运算符优先级
⑥.取出运算数2，能不能计算结果
⑦.取出运算符-，比较运算符优先级，比乘号低，先计算乘号。将之前的数重新拿出来。符合了先进后出，后进先出的特点，所以是栈的数据结构
-
实践与体验
为什么使用逆波兰表达式？
①在数学运算表达式中，运算符总是置于与之相关的两个运算对象之间，在计算结果时，要考虑括号、运算符号的优先性。
②为了程序实现的方便，波兰逻辑学家J.Lukasiewicz提出了另一种表示法，将运算符置于其运算对象之后，没有括号，不用考虑运算符号的优先性。这种表达式称为后缀表达式，又叫逆波兰表达式，如表达式“682-2*3÷+”是“6+(8-2)*2÷3”的逆波兰表达式
数学运算表达式
逆波兰表达式
逆波兰表达式的值
转换
计算
实践与体验
如何转换逆波兰表达式？
体验获取3+4*2-7的逆波兰表达式
逆波兰表达式结果是：
实践与体验
动画演示:
体验获取3+4*2-7的逆波兰表达式
运算符栈
表达式：
3
+
4
*
2
7
-
结果：
设计算法：如何将中缀表达式转为后缀表达式（无括号）
1、初始化运算符栈S1
2、依次从数组中取出各个字符，根据字符做不同处理
3、遇到运算数时，将其输出
4、遇到运算符时，比较其与S1栈顶运算符的优先级:
5、重复步骤2至4，直到表达式遍历结束
6、将S1中剩余的运算符依次弹出
实践与体验
活动2：逆波兰式的算法设计
设计算法：如何将中缀表达式转为后缀表达式（无括号）
1、初始化运算符栈S1
2、依次从数组中取出各个字符，根据字符做不同处理
3、遇到运算数时，将其输出
4、遇到运算符时，比较其与S1栈顶运算符的优先级:
如果运算符栈S1为空，则直接将此运算符入栈；否则如果优先级比栈顶运算符的高，也将运算符压入S1；否则将S1栈顶的运算符弹出。再次转到4与S1中新的栈顶运算符相比较。
5、重复步骤2至4，直到表达式遍历结束
6、将S1中剩余的运算符依次弹出
实践与体验
活动3：逆波兰式的算法设计
活动3：体验算术 6+(5*2+8)/9的逆波兰表达式的转化过程
6
*
5
*
2
结果：
9
/
运算符栈
如何转换逆波兰表达式
实践与体验
（
)
活动3：体验算术 6+(5*2+8)/9的逆波兰表达式的转化过程
6
+
5
*
2
结果：
9
/
运算符栈
如何转换逆波兰表达式
实践与体验
（
)
+
8
6 5 2 * 8 + 9 / +
6
5
2
*
8
+
+
+
/
9
(
*
/
+
活动4设计算法：如何将中缀表达式转为后缀表达式（有括号）
1、初始化运算符栈S1
2、依次从数组中取出各个字符，根据字符做不同处理
3、遇到操作数时，将其输出
4、遇到运算符时，比较其与S1栈顶运算符的优先级:
5 、遇到括号时:
6、重复步骤2至5，直到表达式遍历结束
7、将S1中剩余的运算符依次弹出;
实践与体验
活动4设计算法：如何将中缀表达式转为后缀表达式（有括号）
1、初始化运算符栈S1
2、依次从数组中取出各个字符，根据字符做不同处理
3、遇到操作数时，将其输出
4、遇到运算符时，比较其与S1栈顶运算符的优先级:
若S1为空，或栈顶运算符为左括号“(”,则直接将此运算符入栈;否则，若优先级比栈顶运算符的高，也将运算符压入S1(注意必须是高，相同和低于都不行);否则，将S1栈顶的运算符弹出，再次转到4与S1中新的栈顶运算符相比较.
5 、遇到括号时:
如果是左括号“(”，则直接压入S1;如果是右括号“)”，则依次弹出S1栈顶的运算符，直到遇到左括号为止，此时将这一对括号丢弃
6、重复步骤2至5，直到表达式遍历结束
7、将S1中剩余的运算符依次弹出
实践与体验
实践与小结
1.通过子弹进出弹匣理解栈的概念，栈的基本操作
2.通过活动一“进制转换”，实践与体验“转换逆波兰表达式”
理解用栈思想解决问题的过程
栈是一种先进后出，后进先出的线性表