3.3 栈 课件(共22张PPT)2022—2023学年浙教版（2019）高中信息技术选修1

(共22张PPT)
3.3 栈
新课导入
装置只有一端是开放的，所有的操作都只能在这开放的一端进行。
数据具有“先进后出、后进先出”的特征，可采用“栈”这种数据结构。
栈
栈是一种后进先出的线性表，仅允许在表的一端进行插入或删除操作。
进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；另一端称为栈底，位于栈底位置的元素称为栈底元素。
栈顶元素
栈底元素
栈的特性
先进后出、后进先出
有限序列性
元素的个数是有限的，栈可以为空，也可包含多个元素。
栈中元素呈现线性特征，栈顶元素有一个前驱点，栈底元素有一个后继点，其它元素既有一个前驱点又有一个后继点。
栈顶元素
栈底元素
牛刀小试
1.有六个元素按照6,5,4,3,2,1的顺序依次进栈，则出栈顺序不可能是（ ）
5,4,3,6,1,2
4,5,3,1,2,6
3,4,6,5,2,1
2,3,4,1,5,6
2. 一个栈的入栈序列是1,2,3,4,5，其出栈序列为s1,s2,s3,s4,s5，若s2是3，则s1不可能是（ ）
A. 1 B. 2 C. 4 D. 5
C
D
栈的创建：数组创建
栈一般按照顺序结构存储，可以使用数组来实现。
栈顶元素在数组中的位置会发生改变，因此使用top变量来记录栈顶元素在数组中的位置。
栈的创建：链表创建
栈的链式存储称为链栈，设置栈顶指针top为链栈的头指针。
特点：克服了用数组实现的顺序栈空间利用率不高的缺点，但要为每个栈元素分配额外的指针空间。
栈操作（建栈\入栈IN\出栈OUT）
例：有5个字母“a”“b”“c”“d”“e”按序入栈，可创建长度为5的栈st：初始为空串，
栈顶指针top设置为-1
代码示例：
top=-1
st=[“”]*5
栈按顺序结构存储，通过数组实现，所以Python可使用列表创建栈
栈操作（建栈\入栈IN\出栈OUT）
栈顶指针top记录栈顶元素的位置，初始值为-1，进栈一个元素，top指针加1，即st[top]=栈顶元素
栈操作（建栈\入栈IN\出栈OUT）
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的位置
栈操作（建栈\入栈IN总结\出栈OUT）
停止入栈的条件是什么？
st=[“”]*5
top=-1
while ______________
top+=1
st[top]=“*”
top栈操作（建栈\入栈IN\出栈OUT）
出栈，排在栈顶的元素依次出栈，top指针变量依次减1，直至top的值等于-1
栈操作（建栈\入栈IN\出栈OUT）
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 ____________
print(st[top])
st[top]=“”
top-=1
top!=-1:
栈应用1：十进制数转换为二进制数
算法思想：
1）用栈结构存放每次获得的余数
2）根据栈特征输出每次获得的余数
st=[0]*100 #初始值为0
top=-1
num=int(input(“输入十进制数”))
while num!=0:
_____________
______________ #将余数放入栈
num=num//2
while top!=-1:
print(st[top],end=“”)
________________
______________
top+=1
st[top]=num%2
st[top]=“”
top-=1
括号匹配
将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列3种情况：
栈空，出现右括号，不匹配。
扫描结束，栈中还有左括号，不匹配。
扫描结束，栈空，匹配。
数据合并问题
程序 备注
st = [""]*100 # 初始化
top = -1 # 初始化为空栈
flag = True # 标记是否有不匹配的情况
s = input("请输入数学表达式：") 初始化各项数据
for i in range(len(s)):
if s[i] == "(": # 左括号入栈
top += 1
st[top] = s[i]
elif s[i] == ")": # 右括号与栈顶元素比较
if top == -1:
flag = False
break
else:
top -= 1 从左往右逐步处理数学表达式：若为左括号则入栈；若为右括号则与栈顶指针进行匹配。
数据合并问题
程序 备注
if top > 0: # 栈中还有剩余元素
flag = False 栈中还有剩余元素，即左括号数量大于右括号。
if flag:
print("括号匹配")
else:
print("括号不匹配") 请输入数学表达式：(((a+b)*(c-d)-e)/f)
括号匹配
请输入数学表达式：((a+b)*c)-d)+(e
括号不匹配
字母A、B、C、D、E、F依次入栈，然后依次出栈并输出
for i in "ABCDEF":
top += 1
st[top] = i
while top > -1:
print(st[top], "出栈")
top -= 1
st = []
for i in "ABCDEF":
st.append(i)
print(len(st))
for i in range(len(st)):
print(st.pop(), "出栈“)
用列表自带函数和方法实现栈
逆波兰表达式
逆波兰表达式（后缀表达式）：将运算符置于其运算对象之后，没有括号，无需考虑运算符号的优先级。
中缀表达式转后缀表达式：表达式中加入括号；将所有运算符移到对应括号的右边；删除所有的括号。
逆波兰表达式计算：从左往右扫描逆表达式，遇到数字入栈；遇到运算符号，将栈中最上方的两个元素依次出栈并用运算符计算，将计算结果压入栈中。重复上述过程直至表达式扫描结束。
表达式 第一步 第二步 第三步
a+b*c (a+(b*c)) (a(bc)*)+ abc*+
6+(8-2)*2/3 (6+(((8-2)*2)/3)) (6(((82)-2)*3)/)+ 682-2*3/+
a/b-c+d*e-a*c ((((a/b)-c)+(d*e))-(a*c)) ((((ab)/c)-(de)*)+(ac)*)- ab/c-de*+ac*-
表达式 第一步 第二步 第三步
a+b*c
6+(8-2)*2/3
a/b-c+d*e-a*c
表达式 结果
6+(8-2)*2/3 10
感谢聆听
Thanks to listen