(
课件网) 基础教育精品课 栈 2 栈的基本操作 1 栈的概念与特性 3 栈的应用实例 学习内容 大学 论语 中庸 孟子 将4本书依次放入收纳箱 中庸 大学 孟子 论语 将4本书依次从收纳箱取出 弹匣中子弹装弹过程（入栈） 文字处理软件的“撤销 ”操作 网页浏览器的“ 后退 ”键 消毒桶中餐盘的取放 中庸 大学 孟子 论语 栈的概念 栈底： 栈顶： 中庸 大学 孟子 论语 ü 先进后出 、 后进先出 ü 有限序列性 栈的特性 栈底： 栈顶： 相同点 有限序列， 线性表结构， 元素个数是有限的， 可以 是空的， 也可以包含多个 元素。 栈是“ 先进后出 ”， 仅在 栈顶 一 端进行入栈或出栈操作； 队列是“ 先进先出 ”， 可 以在两端进行操作， 其中队尾 一 端入队， 队首 一 端出队。 问题与讨论：栈与队列有什么相同点与不同点？ 不同点 A B C D 数组 st 0 1 2 3 D C B A 栈的存储 top=3 top=2 top= 1 top=0 使用数组st来存储栈 栈底： 栈顶： D C D C B A 栈的存储 top=3 top=2 top= 1 top=0 B A ^ 栈的链式存储结构 栈底： 栈顶： top top = - 1 st = ['']*4 栈的基本操作：建栈 3 2 1 0 下标 空栈 top = top + 1 st[top] = 'A' top = top + 1 st[top] = 'B' top = top + 1 st[top] = 'C' top = top + 1 st[top] = 'D' 下标 3 2 1 top→ 0 栈的基本操作：入栈 D C B A C B A B A A 3 top→ 2 1 0 top→ 3 2 1 0 3 2 top→ 1 0 ① ② ③ ④ a = ['A','B','C','D'] for i in a: = D C B A 栈的基本操作：入栈 3 2 1 0 下标 思考： 若栈空则不能出栈， 判断栈空的条件是什么？ 下标 top→ 3 2 1 0 D C B A 出栈时栈顶元素取出， 同时top值减1 栈的基本操作：出栈 出栈和取出栈顶元素有什么区别？ 输出栈顶元素代码如何实现？ print(st[top]) top == - 1 while top > - 1: print(st[top],end="") top = top - 1 下标 top→ 3 2 1 0 D C B A 栈的基本操作：出栈 运行结果： DCBA 问题与讨论： 字母A,B,C按顺序入栈， 请问出栈的顺序可能有哪几种？ A,B,C A,C,B B,A,C B,C,A C,B,A C,A,B A B C 问题与讨论： 字母A,B,C按顺序入栈， 请问出栈的顺序可能有哪几种？ B,C,A C,B,A C,A,B A,B,C A,C,B B,A,C A B C 第 一章项目挑战中的“ 用户角色特征值 ”， 把该值 （十进制） 转换成二进制， 采用“ 除 二取余法 ”， 利用 栈来存储每次计算得到的余数 。 (6)10 = (110)2 22 2 1 1 0 … … … … … … 栈的实例：进制转换 2 top→1 0 入栈过程 top→2 1 0 2 6 2 3 2 1 0 栈的实例：进制转换 特征值的变化： 6→3→ 1→0 … …0 ……1 ……1 2 1 top→ 0 0 1 0 1 1 0 n= 1 ② n=0 ③ n=3 ① 2 2 1 1 top→ 0 0 top = - 1 ② ③ ④ 出栈过程 1 0 top→2 1 0 ① 1 栈的实例：进制转换 1 0 0 1 1 0 2 top→1 0 stack = [- 1]* 100 top = - 1 n = int(input("请输入十进制整数：")) while : x = n % 2 top = top + 1 n = n // 2 while top >= 0: print(stack[top],end="") = 栈的实例：进制转换 (6×(3+2)-4)÷2 6×(3+2)-4)÷2 (6×(3+2-4)÷2 )6×)3+2(-4(÷2 判断 一 个数学计算式中的括号（只有小括号） 是否匹配。 匹配 不匹配 不匹配 不匹配 栈的实例：括号匹配 括号的数量 括号的位置 从左往右遍历， 遇到左括号， 入栈， 遇到右括号， 出栈。 ① 栈空， 出现右括号， 不匹配 ② 遍历结束， 栈中还有左括号（栈不空）， 不匹配 ③ 遍历结束， 栈空， 匹配 1.计算式中只关注括号， 忽略其他字符 ( ( ) ) 2.判断左右括号的数量与位置时， 采用栈结构来设计 栈的实例：括号匹配 第 一 步： 抽象与建模 (6×(3+2)-4)÷2 top = - 1 ① ② ③ ④ 栈的实例：括号匹配 第 二 步： 设计算法 ( ( ) ) ... ...
