3.3 栈 课件（共21张PPT） 浙教版（2019）信息技术选修1

(共21张PPT)
3.3 栈
概念特征操作应用
情景创设
汉诺塔游戏，玩法如下: 1.有三根杆子A,B,C。A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上
完成游戏，分析各个环移动的特征
栈概念
是一种“先进后出”的线性表，
仅允许在一端进行插入和删除
允许插入或删除的一端称为栈顶，对应元素称为栈顶元素
另一端叫栈底，对应元素称为栈顶元素
栈特征
（1）先进后出，后进先出
元素入栈顺序和元素出栈顺序相反
（2）有限序列性：栈元素个数有限
栈可以为空，也可以包含多个元素，
栈顶元素只有一个前驱点，
栈底元素只有一个后继点，
其他元素既有一个前驱点，又有一个后继点。
栈操作（建栈）
例：有5个字母“a”“b”“c”“d”“e”按序入栈，可创建长度为5的栈st：初始为空串，
栈顶指针top设置为-1
代码示例：
top=-1
st=[“”]*5
栈按顺序结构存储，通过数组实现，所以Python可使用
列表创建栈
栈操作（入栈）
栈顶指针top记录栈顶元素的位置，初始值为-1，进栈一个元素，top指针加1，st[top]=栈顶元素
top=-1 #初始值
top=top+1 #top=0
st[top]=”a” #a入栈，top指向a的位置
top=top+1 #top=1
st[top]=”b” #b入栈，top指向b的位置
……
top=-1 #初始值
top=top+1 #top=0
st[top]=”a” #a入栈，top指向a的位置
top=top+1 #top=1
st[top]=”b” #b入栈，top指向b的位置
top=top+1 #top=2
st[top]=”c” #c入栈，top指向c的位置
top=top+1 #top=3
st[top]=”d” #d入栈，top指向d的位置
top=top+1 #top=4
st[top]=”e” #e入栈，top指向e的位置
栈操作（入栈）
栈操作（入栈）
入栈过程用算法的什么结构实现？
停止入栈的条件是什么？
st=[“”]*5
top=-1
while toptop+=1
st[top]=“*”
栈操作（出栈）
出栈，排在栈顶的元素依次出栈，top指针变量依次减1，直至top的值等于-1
1.print(st[top])
2.st[top]=“”
3.top=top-1
栈操作（出栈）
top=4 #初始值
st[top]=”” #e出栈
top=top-1 #top=3 ，top指向d的位置
st[top]=”” #d出栈
top=top-1 #top=2 ，top指向c的位置
st[top]=”” #c出栈
top=top-1 #top=1 ，top指向b的位置
st[top]=”” #b出栈
top=top-1 #top=0 ，top指向a的位置
st[top]=”” #a出栈
top=top-1 #top=-1 ，栈空
栈操作（出栈）
出栈过程用算法的什么结构实现？
停止出栈的条件是什么？
top=len(st)-1
while top!=-1:
print(st[top])
st[top]=“”
top-=1
问题与讨论
编号为1、2、3、4的4列火车，按顺序开进一个栈式结构的站点。问：开出火车站的顺序由多少种？请写出所有可能的出栈序列。
以1开头，只能1进1出，剩下2、3、4
以2开头，只能1进2进2出，剩下3、4
以3开头，只能1进2进3进3出，剩下4
以4开头，只能1进2进3进3进4进4出，则出栈序列为：4、3、2、1
算法思想：
用栈结构存放每次获得的余数
根据栈特征输出每次获得的余数
栈应用1：十进制数转换为二进制数
st=[0]*100
top=-1
num=int(input(“输入十进制数”))
while num!=0:
top+=1
st[top]=num%2
num=num//2
while top!=-1:
print(st[top],end=“”)
st[top]=“”
top-=1
输出
栈应用2：括号匹配
一、抽象与建模
将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列3种情况：
（1）栈空，出现右括号，不匹配
（2）扫描结束，栈中还有左括号，不匹配
（3）扫描结束，栈空，匹配
栈应用2：括号匹配
二、设计算法
（1）设置一个栈st和栈顶指针top
（2）从左往右处理数学计算式，遇到左括号，top的值加1，并将其压入栈中；若是右括号：
①如果top大于-1，把栈顶的左括号弹出，top的值减1
②如果top等于-1，栈为空，输出不匹配
（3）如果数学计算式处理完毕，top大于-1，栈中还有未匹配的左括号，输出不匹配
栈应用2：括号匹配
三、编写程序
st=[""]*100
top=-1
flag=True
s = input("请输入数学表达式:")
for i in range(len(s)):
if s[i] == "(":
top=top+1
st[top]=s[i]
elif s[i] == ")":
if top==-1:
flag=False
break
else:
top=top-1
if top>=0:
flag=False
if flag:
print("该数学表达式括号匹配")
else:
print("该数学表达式括号不匹配")
栈应用3：逆波兰表达式
在数学运算表达式中，运算符总是置于与之相关的两个运算对象之间，在计算结果时，要考虑括号、运算符号的优先性。为了程序实现的方便，波兰逻辑学家J.Lukasiewicz提出了另一种表示法，将运算符置于其运算对象之后，没有括号，不用考虑运算符号的优先性。这种表达式称为后缀表达式，又叫逆波兰表达式，如表达式“6 8 2 – 2 * 3 ÷ + ”是“6+（8-2）*2÷3”的逆波兰表达式。
栈知识总结
栈的概念及特征
栈的操作
栈的应用