3.3 栈（教学课件）信息技术浙教版2019选择性必修1

第3节 栈（1课时） 第3章 字符串、队列和栈 浙教版（2019） 选修一 栈的概念与特性 01 栈的基本操作 02 学习目录 依据解决问题的需要，从问题中提炼出栈结构。 01 通过具体任务的实践活动，体验用栈解决问题的基本流程，逐步形成运用栈结构解决问题的思维方式和学科方法。 03 能够总结出栈的特性，领会栈的相关操作。 02 学习目标 PART 01 栈的概念与特性 新课导入 看 看 一 汉诺塔游戏 新课导入 想 想 一 1.有三根杆子A,B,C。A杆上有若干碟子； 2.每次移动一块碟子,小的只能叠在大的上； 3.把所有碟子从A杆全部移到C杆。 游戏规则 完成游戏，分析各个环移动的特征。 提问 新课导入 弹匣中子弹的装弹和出弹、桶型消毒柜中餐盘的取放等都只能在某一端进行操作；网页浏览器上有一个“后退”键，点击后可以按访问顺序的逆序加载浏览过的网页。 上述事件都具备栈结构的特点：后进先出。 什么是栈？ 栈的概念与特性 一 概念 栈是一种先进后出的操作受限的线性表，仅允许在表的一端进行插入或删除。 栈底元素 位于栈底位置的元素。 01 03 02 04 队列 栈 底 不进行操作的一端。 栈顶 进行插入或删除操作的一端。 栈顶元素 位于栈顶位置的元素。 栈的概念与特性 一 特性 先进后出、后进先出 （1） 由于栈仅允许在表的一端进行插入和删除操作，因此栈具备“先进后出，后进先出”的特点。 (元素的入栈顺序和出栈顺序相反) 元素的入栈顺序和出栈顺序相反 栈的概念与特性 一 特性 （2） 有限序列性 同队列一样，栈中的元素也是有限的。栈可以是空的，也可以包含多个元素。栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。     3 2 1 0     A 3 2 1 0   B  3 2 1 0 C    3 2 1 0 D   3 2 1 0 空栈 top=-1 top top top 满栈 字母“A”“B”“C”“D”按序入栈的过程 栈的概念与特性 一 只需知道数据之间相互链接的顺序 探讨与讨论 一 栈与队列有什么相同点和不同点? 数据结构 队列 栈 相同点 都是一种操作受限的线性表，都具有有限序列性的特点。 不同点 两端开放:队尾入队，队首出队 一端开放:栈顶入栈出栈 先进先出、先进后出 栈的概念与特性 一 只需知道数据之间相互链接的顺序 探讨与讨论 一 有1个栈，从栈顶到栈底依次为元素a、b、c并且已知元素d已入栈并出栈，则这四个元素的入栈顺序可能为（ ） A.a,b,c,d B.b,d,c,a C.c,d,b,a D.d,a,b,c C 解析：因为d已经入栈并且出栈，因此其入栈的顺序对于我们是未知的，而a、6、c三个元素的相对顺序是确定的，所以他们之间的入栈顺序也是确定的，依次为c、b、a，而d可任意穿插在其中。故选:C。 栈的基本操作 二 栈，一般按顺序结构存储，可用数组实现。 03 02 01 01 基本操作 建栈 入栈 出栈 ①图为栈结构，②图为用数组st存储该栈。当top=0时，st[top]存储栈底元素“A”；当top=1时，st[top]存储栈中第2个元素“B”；当top=2时，st[top]存储栈顶元素“C”。 栈的基本操作 二 拓展链接 栈的链式存储结构 D C B A ^ top 利用链式存储方式实现的栈称为链栈。它可以用单链表的方式实现。 如右图所示，栈顶指针top为链栈的头指针。链栈的优点在于它克服了用数组实现的顺序栈空 间利用率不高的缺点，但是要为每个栈元素分配额外的指针空间。 栈的链式 存储结构 栈的基本操作 二 01 建栈 在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。 要 使4个 字 母“A”“B”“C”“D”按序入栈、出栈，该如何操作？ 建一个长度为4的栈st，元素初始值均为空串。为了操作方便，把指向栈顶元素的指针变量top值设置为–1。 Python代码实现如下 top=–1 st=[""]*4 栈的基本操作 二 02 入栈、出栈 入栈又叫压栈操作，把数据元素压入栈顶。 每次入栈时，栈顶指针变量top值加1，再给st[top]赋值。     3 2 1 0 下标     A 3 2 1 0   B  3 2 1 0 C    3 2 1 0 D   3 2 1 0 空栈 top=-1 top top top 满栈 字母“A”“B”“C”“D”按序入栈的过程 栈的基本操作 二 02 入栈、出栈 Python代码实现如下： 代码 top=top+1 #top=0 st[top]="A" #字母A入栈 top=top+1 #top=1 st[top]="B" #字母B入栈 top=top+1 #top=2 st[top]="C" #字母C入栈 top=top+1 #top=3 st[top]="D" #字母D入栈 出栈时把栈顶元素取出，同时top值减1。如果栈中没有元素时，即top=–1，不能进行出栈操作。 栈的基本操作 二 只需知道数据之间相互链接的顺序 探讨与讨论 1.编号为1、2、3、4的4列火车，按顺序开进一个栈式结构的站点。问:开出火车站的顺序有多少种?请写出所有可能的出栈序列。 可能的出栈序列有14种; 出栈的序列分别是 1234;1243;1324;1342;1432; 2134;2143;2314;2341;2431; 3214;3241;3421;4321。 [解析]①列车4辆全部进站后顺序出站的情况(1种):4321 ②列车3辆车进站后开始出站(3种):3421，3241，3214 ③列车2辆车进站后开始出站(5种):2431，2341，2134，2143，2314 ④列车1辆车进站后开始出站(5种):1432，1324，1342，1234，1243 栈的基本操作 二 括号匹配 在一个数学计算式“(a÷(b–c)+d)×e”中，位置1和位置4有左括号“(”，位置8和位置11有右括号“)”。位置1的左括号与位置11的右括号相匹配，位置4的左括号与位置8的右括号相匹配。而对于数学计算式“a÷(b–c))”，位置8的右括号没有可匹配的左括号。设计一个程序，判断输入的数学计算式中的括号（只有小括号）是否匹配。 抽象与建模 1 数学计算式中既有数字，又有加减乘除等运算符号，判断括号是否匹配时，可以忽略这些括号以外的数字和运算符号。 括号序列 栈的基本操作 二 若左右括号的数量相等并且位置匹配，则括号匹配；否则，括号不匹配。判断左右括号的数量与位置时，可以采用栈结构进行设计：遇到左括号时，入栈；遇到右括号时，则把处于栈顶的左括号出栈。 3 2 1 栈空，出现右括号时，不匹配。 扫描结束，栈中还有左括号时，不匹配。 扫描结束，栈空，则匹配。 分以下三种情况，判断数学计算式中的括号是否匹配： 栈的基本操作 二 设计算法 2 设置一个栈st和栈顶指针top，从左往右逐步处理数学计算式。若是左括号，栈顶指针top值加1，并将其压入栈中。若是右括号：如果top大于–1，那么栈中有元素，把栈顶的左括号弹出，top值减1，表示该右括号与弹出的左括号相匹配；如果top等于–1，栈为空，表示没有与该右括号相匹配的左括号，是不匹配的数学计算式。如果数学计算式处理完毕，栈中还有左括号，那么它也是不匹配的数学计算式。 （ 下标 top 1 0 （ （ top 1 0 （ top 1 0 （ （ top=-1 1 0 ①”(” ②”(” ③”)” ④”)” 数学计算式“(a+(b-c)+d)xe”的入栈及出栈过程 栈的基本操作 二 编写程序 3 程序： 测试结果： 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("括号不匹配") 请输入数学计算式: (((a+b)*(c-d)-e)/f) 输出: 括号匹配 请输入数学计算式: ((a+b)*c)-d)+(e 输出: 括号不匹配 栈的基本操作 二 拓展链接 用列表自带的函数和方法实现的栈 Python中用列表自带的函数和方法可以实现建栈、入栈、出栈、栈中元素个数的统计等操作。 代码 注释 stacklist=[] #建立一个空栈list stacklist.append("A") #字母A入栈 stacklist.append("B") #字母B入栈 print(stacklist[1]) #输出栈顶元素，为字母B print(len(stacklist)) #输出栈中元素的个数，为2 stacklist.pop() #弹出栈顶元素 print(len(stacklist)) #输出栈中元素的个数，为1，是字母A 栈的基本操作 二 1.有一个空栈,规定用I表示一个元素入栈,用O表示一个元素出栈。现经过IIOIOOIO系列操作后,元素的出栈顺序是4,1,3,2,则元素的入栈顺序是（ ） A.1,3,4,2 B.3,4,1,2 C.2,3,1,4 D.1,4,3,2 B 输出s 课堂小练 三 1.下列关于队列和栈的说法，不正确的是（ ） A.队列是一种先进先出的线性表，可在队尾进行插入操作 B.栈的特性是“先进后出，后进先出” C.某栈的入栈的顺序为“abe”，出栈顺序只有3种 D.队列和栈都是线性数据结构，都可以用数组来实现 2.某序列为a，b，c，d，经过入栈、出栈、入栈、入栈、出栈、出栈操作后，则出栈的序列是（ ） A.a,b,c B.a,c,b C.b,c,d D.b,a,c C B 小结 四 小 结 栈的概念与特性 栈的基本操作 栈 1.建栈 2.入栈、出栈 1.栈的概念 2.栈的特性 ①先进后出、后进先出 ②有限序列性 谢谢观看 第3节 栈 浙教版（2019） 选修一 $$