3.3栈 课件 2021—2022学年浙教版（2019）信息技术选修1（25张PPT）

(共25张PPT)
知识回顾
弹匣的装弹过程（入栈）
栈的示例—弹匣
子弹进出弹匣的过程具有下列特点：
①整个装置只有一端开放（最上端），而且进、出只能在这一端进行。
②弹匣中的子弹成一纵队排列。
③任何子弹进出弹匣的规律是“先进后出、后进先出”，即最先装入弹匣的子弹最后才能被弹出，而最后装入弹匣的子弹则最先被弹出。
CHZX
3.3 栈
浙江省高中信息技术 选择性必修一 《数据与数据结构》
栈的概念与特性
概念
特性
01
概 念：栈是一种先进后出的操作受限的线性表，仅允许在表的一端进行插入或删除。
栈 顶：进行插入或删除操作的一端。
栈顶元素：位于栈顶位置的元素
栈 底：不进行操作的一端。
栈底元素：位于栈顶位置的元素。
栈的概念
zhan de gainian
栈底元素
栈顶元素
先进后出、后进先出：由于栈仅允许在表的一端进行插入和删除操作，因此栈具备“先进后出，后进先出”的特点。
（元素的入栈顺序和出栈顺序相反）
栈的特性
zhan de texing
弹匣的装弹过程（入栈）
有限序列性：栈也是一种线性表结构，元素个数是有限的。
栈可以是空的，也可以包含多个元素。
栈中所有元素呈线性特征，栈顶元素有一个前驱点，栈底元素有一个后继段，其他元素既有一个前驱点，又有一个后继点。
栈的特性
zhan de texing
1、汉诺塔游戏的操作过程中，将圆盘从小到大依次移入某根柱子上，而后又从上面的圆盘开始依次将圆盘从柱子上移走，这个移入和移出的过程与下列数据结构操作类似的是（ ）
A.数组 B.队列
C.字符串 D.栈
练一练
lianyilian
D
2.下列事件操作的原理与栈的特征不相符的是（ ）
A.杂技演员表演叠罗汉时，最后上去的人总是第一个下来
B.在word、photoshop等文档或图像编辑软件中，执行“撤销”操作
C.在火车站排队买票或者在超市排队购票
D.多个函数嵌套调用时，按照“后调用先返回”的原则进行
练一练
lianyilian
C
3.用一个带盖的玻璃桶来存取乒乓球，放、取只能从带盖的一端进行（另一端为封闭状态），且桶的直径只允许一个乒乓球进出。若放入球的编号系列为1,2,3,4，则取出球的编号系列不可能为（ ）
A.1,2,3,4 B.2,3,4,1
C.4,2,3,1 D.3,2,4,1
练一练
lianyilian
C
栈的基本操作
栈的存储结构
建栈
入栈
出栈
02
栈的存储结构：栈一般按顺序结构存储，可以用数组来实现。由于栈顶元素在数组中的位置会发生变化，因此使用top变量来记录栈顶元素在数组中的位置。
栈的基本操作
zhan de jibencaozuo
栈的链式存储结构：栈的链式存储称为链栈，栈顶指针top为链栈的头指针。
栈的基本操作
zhan de jibencaozuo
建栈
在python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。
例如：有4个字母“A”“B”“C”“D”按顺序入栈、出栈时，可以创建一个长度为4的栈st，元素初始值均为空串。
（为了操作方便，把指向栈顶元素的指针变量top设置为-1）
栈的基本操作
zhan de jibencaozuo
top=-1
st=[“”]*4
入栈（压栈）
每次入栈时，栈顶指针变量top值加1，再给st[top]赋值。
字母“A”“B”“C”“D”按顺序入栈过程如下：
栈的基本操作
zhan de jibencaozuo
3
2
1
0
初始状态（空栈）
“A”入栈
top=-1
st=[“”]*4
top+=1
st[top] =“A”
“B”入栈
top+=1
st[top] =“B”
top
3
2
1
0
top
-1
3
2
1
0 A
top
A
B
入栈（压栈）
栈的基本操作
zhan de jibencaozuo
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的位置
top=-1
for i in range(len(st)):
top+=1
st[top]=chr(ord(‘a’)+i)
出栈
出栈时，把栈顶元素取出，同时top减1，如果栈中没有元素时，即top=-1，不能执行出栈操作。
栈的基本操作
zhan de jibencaozuo
3 D
2 C
1 B
0 A
初始状态（满栈）
top
“D”出栈
st[top] =“”
top-=1
top
3
2 C
1 B
0 A
D
全部出栈
top=4
while top！=-1：
st[top] =“”
top-=1
top
3
2
1
0
十进制转二进制
算法思想： 1）用栈结构存放每次获得的余数
2）根据栈特征输出每次获得的余数
应用
yingyong
st=[0]*100 #初始值为0
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
括号匹配
应用
yingyong
一、抽象与建模
将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列3种情况：
（1）栈空，出现右括号，不匹配
（2）扫描结束，栈中还有左括号，不匹配
（3）扫描结束，栈空，匹配
括号匹配
应用
yingyong
二、设计算法
（1）设置一个栈st和栈顶指针top
（2）从左往右处理数学计算式，遇到左括号，top的值加1，并将其压入栈中；若是右括号：
①如果top大于-1，把栈顶的左括号弹出，top的值减1
②如果top等于-1，栈为空，输出不匹配
（3）如果数学计算式处理完毕，top大于-1，栈中还有未匹配的左括号，输出不匹配
括号匹配
应用
yingyong
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("该数学表达式括号不匹配")
括号匹配
拓展
tuozhan
4. 设栈s的初始状态为空，元素a,b,c,d,e,f,g,依次入栈，入栈和出栈可以交替进行，且7个元素的出栈顺序为b,d,c,f,e,a,g,则栈s的容量至少应该为（ ）
A.1 B.2 C.3 D.4
练一练
lianyilian
B
5.在利用栈来判断一个表达式中的括号（只有小括号）是否匹配的过程中，当遇到表达式中的一个左括号时，就让它进栈，遇到一个右括号时，就对栈进行一次出栈操作，当栈最后为空时，表示括号是配对的，否则是不配对的，现有表达式“（a+b）*c+（（d-e）*f+g）*h”，针对该表达式设计栈的大小，至少为（ ）
A.1 B.2 C.3 D.4
练一练
lianyilian
B
练一练
lianyilian
B
练一练
lianyilian