学习目标掌握栈的进阶操作Peek偷看、isEmpty、isFull理解栈的状态空栈、满栈、栈溢出学习栈的实际应用括号匹配、计算器、程序调用栈培养用栈解决实际问题的能力 小提示这是选学章节适合对栈有基本了解并想深入学习的同学11.1 栈的更多操作偷看和检查除了入栈Push和出栈Pop栈还有一些有用的小技巧 偷看栈顶Peek有时候我们想看看最上面是什么但不想拿走它。生活例子羽毛球筒你想知道筒里还有几个球 ┌───┐ │ │ ← 看一眼是白色的球 │ │ 不拿出来 │ │ └───┘ 看完后球还在里面对比Pop vs PeekPop出栈 [ ] ← 拿走了 [ ] [ ] 拿走后 [ ] ← 香蕉变成顶部 [ ] Peek偷看 [ ] ← 只是看看 [ ] [ ] 看完后 [ ] ← 苹果还在顶部 [ ] [ ]什么时候用Peek想知道栈顶是什么但还不想拿走它比如看看筒里的球够不够但不打球 栈的状态检查1. 空栈Empty Stack栈里什么都没有 顶 → (空的) ------ 底 就像 - 空的羽毛球筒 - 空的盘子架 ️ - 空的书堆 为什么要检查空栈如果栈是空的就不能Pop [ 空栈 ] ↓ 想拿东西 → ❌ 错误没有东西可拿生活例子小明想拿羽毛球 筒里的状态 ┌───┐ │ │ ← 空的 │ │ └───┘ 小明能拿到球吗 答案不能筒是空的 程序要先检查if (栈不是空的) { 才能拿 }2. 满栈Full Stack有些栈有大小限制羽毛球筒装满了 ┌───┐ │ │ ← 装满了 │ │ │ │ │ │ │ │ └───┘ 再放一个 → ❌ 放不下了生活例子️ 盘子叠太高会倒 书堆太高会倒 煎饼叠太高会塌栈溢出Stack Overflow这个词你可能听说过栈溢出 栈满了还要放东西 就像 1. 盘子叠太高 → 倒了 2. 书堆太高 → 倒了 3. 积木太高 → 倒了 小故事小红的积木塔小红在叠积木 高度2块 高度4块 ⬜ 高度6块 继续叠... ⬜ 高度9块 再叠... 哗啦 倒了 这就是栈溢出3. 栈的完整操作总结操作名称作用改变栈Push(入栈)添加到顶部是Pop(出栈)移除顶部并返回是Peek(偷看)查看顶部否isEmpty检查是否为空否isFull检查是否已满否 思考题生活中的栈检查问题1妈妈在厨房洗碗盘子架最多放10个盘子。现在已经放了8个盘子 ️ ️ ️ ️ ️ ️ ️ ️ ---- 盘子架 问 1. 还能放几个盘子 _____ 2. 如果再洗了5个盘子会发生什么 _____ 3. 怎么解决 _____问题2小明打羽毛球筒里原来有3个球。原来 ┌───┐ │ │ │ │ │ │ └───┘ 打了2场 - 第1场用了1个球 - 第2场用了2个球 问 1. 现在筒里还有球吗 _____ 2. 如果还想打第3场怎么办 _____11.2 神奇的应用括号匹配游戏你写数学算式的时候老师有没有说过括号要配对哦栈可以帮我们检查 数学算式中的括号正确的括号( 2 3 ) ✓ - 左括号和右括号配对 ( 2 ( 3 × 4 ) ) ✓ - 嵌套的括号也配对 [ 2 { 3 × ( 4 5 ) } ] ✓ - 不同类型的括号配对错误的括号( 2 3 ❌ - 缺少右括号 ) 2 3 ( ❌ - 顺序反了 ( 2 [ 3 × 4 ) ] ❌ - 类型不匹配 用栈检查括号规则遇到左括号(、[、{→ 放进栈遇到右括号)、]、}→ 从栈里拿出来检查是否配对最后栈如果是空的 → 括号配对成功✓例子1检查( 2 3 )步骤1读到 ( 栈的状态 顶 → [ ( ] ---- 步骤2读到数字2、、3跳过 步骤3读到 ) 从栈里拿出 ( → 配对成功✓ 栈的状态 顶 → (空) ---- 结果栈是空的括号正确✓例子2检查( 2 ( 3 × 4 ) )步骤1读到第1个 ( 栈 顶 → [ ( ] ---- 步骤2读到第2个 ( 栈 顶 → [ ( ] [ ( ] ---- 步骤3读到第1个 ) 拿出一个 ( → 配对 ✓ 栈 顶 → [ ( ] ---- 步骤4读到第2个 ) 拿出一个 ( → 配对 ✓ 栈 顶 → (空) ---- 结果栈是空的括号正确✓例子3检查错误的( 2 3缺右括号步骤1读到 ( 栈 顶 → [ ( ] ---- 步骤2读完了没有 ) 结果栈不是空的括号错误❌ 动手练习检查括号判断下面的括号是否正确并画出栈的变化( 5 6 )正确 □是 □否( ( 2 3 ) × 4 )正确 □是 □否( 2 3 ) )正确 □是 □否( ( 2 3 )正确 □是 □否 为什么括号匹配很重要在编程中# 正确的代码if(age10):print(你好)# 错误的代码if(age10:print(你好)❌ 缺少右括号在数学中正确( 2 3 ) × 4 20 错误( 2 3 × 4 ❌ 没法算计算机就用栈来检查你的代码有没有写错括号11.3 神奇的应用计算器的秘密你知道计算器是怎么算2 3 × 4的吗用栈 为什么需要栈问题哪个答案对2 3 × 4 ? 方案A从左到右算 2 3 5 5 × 4 20 ❌ 错 方案B先乘除后加减 3 × 4 12 2 12 14 ✓ 对计算器需要记住遇到乘号×要等一等先算乘法再算加法用栈来记住等待的数字和运算符 简化的计算过程例子算2 3 × 4步骤1读到 2 数字栈 顶 → [ 2 ] ---- 步骤2读到 运算符先记住 运算符栈 顶 → [ ] ---- 步骤3读到 3 数字栈 顶 → [ 3 ] [ 2 ] ---- 步骤4读到 ×乘法优先级高 运算符栈 顶 → [ × ] [ ] ---- 步骤5读到 4 数字栈 顶 → [ 4 ] [ 3 ] [ 2 ] ---- 步骤6开始计算 先算乘法3 × 4 12 数字栈 顶 → [ 12 ] [ 2 ] ---- 再算加法2 12 14 数字栈 顶 → [ 14 ] ---- 答案14 ✓ 运算优先级优先级运算符高× ÷乘除低 -加减规则优先级高的先算相同优先级从左到右算括号里的先算 思考题问题1用栈的方法算5 2 × 3步骤 1. 读到5 → 数字栈_____ 2. 读到 → 运算符栈_____ 3. 读到2 → 数字栈_____ 4. 读到× → 运算符栈_____ 5. 读到3 → 数字栈_____ 6. 先算2×3 _____ 7. 再算5_____ _____ 答案_____问题2为什么计算器需要两个栈答 一个栈存_______________ 另一个栈存_______________问题3算一算10 - 2 × 3 ? 如果从左到右算 10 - 2 8 8 × 3 24 ❌ 正确的算法 2 × 3 _____ 10 - _____ _____ 答案_____11.4 神奇的应用程序的记忆——调用栈当程序运行时计算机也用栈来记住事情 打电话的故事小明的一天早上小明在做作业任务A 突然妈妈叫小明去买酱油任务B ↓ 小明先记住作业做到哪了去买酱油 路上遇到老师老师让他去传达室拿东西任务C ↓ 小明先记住要买酱油去传达室 在传达室拿到东西任务C完成✓ ↓ 小明想起来要买酱油去买酱油 买完酱油任务B完成✓ ↓ 小明想起来要做作业回家继续做作业 做完作业任务A完成✓用栈表示开始 栈[ 做作业A ] 妈妈叫去买酱油 栈[ 买酱油B ] [ 做作业A ] 老师叫去拿东西 栈[ 拿东西C ] [ 买酱油B ] [ 做作业A ] 完成拿东西出栈 栈[ 买酱油B ] [ 做作业A ] 完成买酱油出栈 栈[ 做作业A ] 完成作业出栈 栈(空) 全部完成✓发现了什么最后收到的任务最先完成最早的任务最后完成这就是栈的后进先出 程序中的调用栈程序也是这样工作的小故事做三明治主任务做三明治 ↓ 需要拿面包 ↓ 需要打开柜子 ↓ 完成打开柜子 ✓ ↓ 完成拿面包 ✓ ↓ 需要拿生菜 ↓ 需要打开冰箱 ↓ 完成打开冰箱 ✓ ↓ 完成拿生菜 ✓ ↓ 完成做三明治 ✓用栈表示步骤1开始做三明治 栈[ 做三明治 ] 步骤2需要拿面包 栈[ 拿面包 ] [ 做三明治 ] 步骤3需要打开柜子 栈[ 打开柜子 ] [ 拿面包 ] [ 做三明治 ] 步骤4柜子打开了完成 栈[ 拿面包 ] [ 做三明治 ] 步骤5面包拿到了完成 栈[ 做三明治 ] 步骤6需要拿生菜 栈[ 拿生菜 ] [ 做三明治 ] 步骤7需要打开冰箱 栈[ 打开冰箱 ] [ 拿生菜 ] [ 做三明治 ] 步骤8冰箱打开了完成 栈[ 拿生菜 ] [ 做三明治 ] 步骤9生菜拿到了完成 栈[ 做三明治 ] 步骤10三明治做好了完成 栈(空) 为什么要用栈好处1记住顺序做事情时要记住 - 正在做什么 - 做完后要回到哪里 - 栈自动帮我们记住好处2一层一层返回就像 - 剥洋葱 一层一层剥 - 穿衣服 一件一件脱 - 走迷宫 原路返回 思考题问题1小红的任务小红在画画任务A 妈妈叫她洗手任务B 洗手时发现没毛巾去拿毛巾任务C 画出栈的变化 开始 栈_________________ 妈妈叫洗手 栈_________________ _________________ 发现没毛巾 栈_________________ _________________ _________________ 拿到毛巾 栈_________________ 洗完手 栈_________________ 继续画画 栈_________________问题2程序的任务程序要做蛋糕 1. 准备材料 1.1 拿面粉 1.2 拿鸡蛋 2. 搅拌 3. 烤箱烘烤 画出调用栈在拿鸡蛋时的样子 栈_________________ _________________ _________________11.5 本章小结今天我们学习了栈的进阶应用让我们回顾一下 新学到的操作操作作用改变栈例子Peek查看栈顶但不移除否看羽毛球筒里有什么球isEmpty检查栈是否为空否确认盘子架是否空了isFull检查栈是否已满否确认书堆是否太高✨ 三大实际应用 括号匹配检查数学算式的括号是否配对检查程序代码的括号是否正确用栈记住左括号遇到右括号就配对 计算器处理运算优先级先乘除后加减用两个栈数字栈 运算符栈让计算器知道该先算什么 调用栈程序运行时记住任务任务被打断时记住回去的地方一层一层完成一层一层返回 栈溢出的教训栈有容量限制 - ️ 盘子不能叠太高 - 书不能堆太多 - 超过限制会栈溢出 预防方法 - 用 isFull 检查 - Push前先确认还有空间 - 设计合理的栈大小 生活中的进阶应用数学作业- 检查括号是否配对写代码- 编辑器自动检查括号计算器- 正确计算表达式电脑程序- 记住程序执行状态任务管理- 记住被打断的任务走迷宫- 原路返回11.6 【想一想】进阶挑战题挑战题1Peek的应用小明有一个装零食的罐子栈顶 → [ 饼干 ] [ 巧克力 ] [ 糖果 ] [ 苹果 ] ----------问题小明想知道罐子里最上面是什么零食但不想吃。他应该用哪个操作□ Pop出栈□ Peek偷看□ Push入栈用Peek后罐子会变成什么样答_________________________如果小明想吃最上面的零食应该用什么操作答_________________________ 吃完后罐子变成_________________________生活中还有哪些只看不拿的情况例子1_________________________ 例子2_________________________挑战题2栈溢出的预防场景学校图书角有一个书架最多放15本书。现在已经放了13本 ← 第13本 ... ← 第1本 ---- 书架问题还能放几本书答_________________________如果班里同学又带来5本书怎么办□ A. 全部堆上去会倒□ B. 只放2本其他找地方□ C. 拿走最下面的旧书放新书你选理由程序里怎么防止栈溢出答在Push之前先检查_______________挑战题3括号匹配大挑战判断下面的括号是否正确并解释原因1.( [ ] )□ 正确 □ 错误 理由_________________________2.( [ ) ]□ 正确 □ 错误 理由_________________________3.{ ( [ ] ) }□ 正确 □ 错误 理由_________________________4.( ( ( ) ) )□ 正确 □ 错误 理由_________________________挑战题找出错误并改正原式( 2 [ 3 × ( 4 - 5 ] ) ) 错在哪里_________________________ 改正_________________________挑战题4计算器的思考问题1用栈计算10 - 2 × 3步骤提示 1. 先算乘法2 × 3 _____ 2. 再算减法10 - _____ _____ 答案_____ 如果从左到右算 10 - 2 8 8 × 3 24 为什么答案不同 答_________________________问题2为什么计算器需要记住运算的优先级乘除的优先级_____ 高/低 加减的优先级_____ 高/低 如果没有优先级 2 3 × 4 _____ 从左到右算 有优先级 2 3 × 4 _____ 先乘后加挑战题5调用栈的魔法小故事小明整理房间主任务整理房间 步骤1整理书桌 → 发现笔没墨了 → 去找新笔子任务1 → 新笔在柜子里 → 打开柜子子任务2 → 完成打开柜子 → 完成拿到新笔 → 继续整理书桌 → 完成书桌整理好 步骤2整理床铺 → 完成床铺整理好 完成房间整理好画出调用栈的变化时刻A正在整理书桌 栈[ 整理书桌 ] [ 整理房间 ] 时刻B发现没笔去找笔 栈_________________ _________________ _________________ 时刻C需要打开柜子 栈_________________ _________________ _________________ _________________ 时刻D柜子打开了 栈_________________ _________________ _________________ 时刻E拿到新笔 栈_________________ _________________ 时刻F书桌整理完 栈_________________ 时刻G全部完成 栈_________________思考哪个任务最先开始______哪个任务最先完成______这符合栈的什么特点______ 家长互动建议亲爱的家长本章是进阶内容您可以和孩子一起探索Peek操作教孩子只看不拿的概念讨论生活中的偷看场景比如看冰箱里有什么但不拿出来理解不是所有操作都会改变状态安全意识培养讨论栈溢出的危险盘子叠太高会倒书堆太高会倒培养适度原则括号配对游戏和孩子一起检查数学作业中的括号用不同颜色标记配对的括号找出不配对的括号理解计算机如何检查语法错误计算顺序理解讲解运算优先级先乘除后加减用具体例子说明为什么需要优先级让孩子体会计算器的思考过程培养数学运算的逻辑思维任务管理启发讨论做事情被打断的情况如何记住未完成的任务完成一件事再回到上一件事培养任务管理能力编程思维培养解释程序是如何记忆的为什么程序能记住很多事情栈在计算机中的重要作用激发对编程的兴趣 终极挑战挑战任务设计一个智能计算器设计一个能处理括号和优先级的计算器例子计算( 2 3 ) × ( 4 - 1 )步骤1识别括号和数字 - 括号( ) ( ) - 数字2 3 4 1 - 运算符 × - 步骤2先算括号里的 - ( 2 3 ) 5 - ( 4 - 1 ) 3 步骤3再算乘法 - 5 × 3 15 答案15你的设计需要几个栈_____ 分别用来存什么 栈1_________________ 栈2_________________ 栈3_________________如果需要 怎么处理括号 答_________________ 怎么处理优先级 答_________________ 恭喜你完成了栈的进阶学习你现在不仅知道栈是什么还知道了 Peek偷看- 只看不拿 isEmpty/isFull - 状态检查 栈溢出 - 容量限制 括号匹配 - 语法检查 计算器 - 表达式计算 调用栈 - 程序记忆这些知识在实际编程中非常有用继续加油 温馨提示栈不仅仅是后进先出这么简单它是计算机科学中最重要的数据结构之一从浏览器到编译器从计算器到程序运行到处都有栈的身影。理解栈就离真正的程序员更近了一步 复习栈和队列是一对好朋友一个先进先出一个后进先出。记住盘子叠高高后放先拿掉浏览器往回跑后退一步步倒括号要配对计算有优先程序会记忆任务一层层