椰程信奥 · 说课稿

栈与队列 · 说课稿（对应视频 42′54″，课件 20 页）

一、教材与学情

本讲对应视频《CSP复赛专题9-数据结构1》（42′54″），内容聚焦栈与队列。它们是学生接触的第一批"非数组"结构，也是后续搜索、动态规划、图论的基础设施。学情上的典型困难不是"记不住接口"，而是 指针为什么会动、动到哪里——尤其是循环队列的取模回绕与判空判满。

知识与技能：能用数组徒手写出栈（一个指针）与队列（两个指针）；掌握循环队列的判空 head==tail、判满 (tail+1)%M==head、求个数 (tail-head+M)%M；熟练使用 stack / queue 五个接口。
过程与方法：通过"同一组输入 1、2、3、4 分别过栈和队列"的对比实验，自己看出 FILO 与 FIFO 的差别，而不是被灌输定义。
情感态度：体会"主动限制操作"换取"不容易写错"的工程思想；建立"先手写、再用 STL"的学习路径。

① 栈/队列的指针模型；② 循环队列的三件套公式；③ 括号匹配与约瑟夫环的建模。

① 循环队列为什么要牺牲一个格子；② 负数取模 (tail-head)%M 会出错； ③ "围成一圈"到"队首出、队尾进"的翻译。

环节	时间	教师活动	学生活动	设计意图
① 情境引入	4′	课件第 3 页：一摞盘子 vs 排队买票。"能不能从盘子中间抽一个？能不能插队？"	回答并说出两条"规矩"	用生活经验锚定抽象规则
② 栈的原理与手写	10′	第 4–5 页边讲边点：摞盘子动画 → 数组模拟栈，每次 push/pop 都让学生先猜 top 变成几	口头报 top 值，看是否与动画一致	把"指针移动"变成可验证的预测
③ STL 与三个坑	4′	第 6 页：重点敲黑板 `pop()` 不返回值	改错练习	提前拆除高频编译/运行错误
④ 队列的原理与假溢出	8′	第 7–8 页：先让学生"入一个、出一个"反复做，直到 tail 顶到末尾，让他们自己喊出"前面明明空着"	观察划掉的格子，说出问题	先制造认知冲突，再引出循环队列
⑤ 循环队列（重头戏）	10′	第 9–10 页环形动画：连续入队直到队满，追问"此时用了几格？"，引出牺牲一格的必要性	读三件套公式，指出 `+M` 的原因	本讲最难点的可视化突破
⑥ 对比与选型	4′	第 12 页管道对比：1、2、3、4 进去再出来	预测取出顺序	一句话记住选型口诀
⑦ 例题 + 检测	5′	第 13–16 页两道真题动画 + 第 17 页三道检测	完成检测	当堂形成性评价

栈：一个口　top = −1　push: stk[++top]=x　pop: top--　FILO

队列：两个口　head / tail　FIFO　→ 循环：(tail+1)%M

循环队列：空 head==tail　满 (tail+1)%M==head　个数 (tail-head+M)%M ★+M

选型：最近/嵌套/撤销 → 栈；依次/轮转/排队 → 队列

问：为什么不直接教 STL，要花时间手写？
答：STL 的价值在于"替你做对"，但学生不知道它对在哪时，遇到需要改造结构的题（如双端、单调栈）就完全无从下手。手写一遍指针，是把黑盒变成白盒。