(
课件网) 栈（第九课时） 想一想：子弹是如何进出弹匣的呢？它有哪些特点？ 栈思想 子弹进出弹匣的过程有下列特点： ①整个装置只有一端开放(最上端)，而且进、出只能在这一端进行。 ②弹匣中的子弹成一纵队排列。 ③任何子弹进出弹匣的规律是“先进后出、后进先出” 。 栈思想 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 - 结果： 设计算法：如 ... ...
