STL课程第六课《魔法盘子塔——认识Stack栈》本课目标理解什么是 Stack栈。掌握后进先出LIFO的特点。熟练使用push()、pop()、top()、size()、empty()。能够利用 Stack 完成简单模拟。为以后学习括号匹配、DFS、表达式计算打基础。第一幕 食堂里的盘子今天。程序王国的食堂开饭了。阿姨把盘子一个一个叠起来。画图 请问如果现在拿盘子。应该拿哪一个同学们都会回答最上面的。继续问为什么因为如果先拿最下面那个。整个盘子塔都会倒下来。所以。只能拿最上面的盘子。第二幕 什么叫后进先出第一个放进去的是①号盘子。后来放进去②号。③号。④号。⑤号。画图顶部 ⑤ ④ ③ ② ① 底部请问谁最先拿出来答案⑤号。也就是说最后放进去。最先拿出来。总结这就是后进先出英文LIFOLast In First Out后来的先走先来的后走。第三幕 Queue和Stack有什么不同画图。Queue ↑ ↑ 出 进Stack ↑ 进、出总结Queue两头操作。Stack永远只操作顶部。第四幕 请出Stack头文件#includeiostream #includestack using namespace std;创建Stack。stackint st;解释stack表示栈。int保存整数。st变量名字。第五幕 放盘子——push()先放10st.push(10);盘子10继续st.push(20);变成20 10继续st.push(30);变成30 20 10强调push永远放最上面。第六幕 拿盘子——pop()现在拿盘子。st.pop();谁离开当然30。变成20 10再st.pop();变成10老师强调pop永远删除栈顶。第七幕 看看最上面的盘子请问最上面是谁直接st.top()例如coutst.top();输出20top。就是顶部。第八幕 栈还有几个盘子st.size();例如coutst.size();输出2第九幕 栈空了吗st.empty();例如if(st.empty()) { cout没有盘子; }第十幕 Stack不能这样做请问Vectora[3]Stack可以吗答案不能。请问Queue可以遍历吗也不能。Stack更加不能。因为。Stack只能看到顶部。第十一幕 演示程序#includeiostream #includestack using namespace std; int main() { stackint st; st.push(10); st.push(20); st.push(30); cout栈顶st.top()endl; st.pop(); cout新的栈顶st.top()endl; cout元素个数st.size()endl; return 0; }输出栈顶30 新的栈顶20 元素个数2第十二幕 课堂小游戏依次执行push(5) push(8) push(2) pop() push(9)请画图。开始空↓5↓8 5↓2 8 5↓8 5↓9 8 5请问top是谁答案9第十三幕 课堂实践一——撤销功能Undo请问为什么Word里面。CtrlZ。可以撤销因为。每操作一步。都保存一次。例如输入A B CStackC B A点击撤销。就是pop()删除C。又撤销。删除B。是不是很方便第十四幕 课堂实践二——浏览器返回浏览器。访问百度 新闻 天气 地图请问点击返回。去哪地图退出。回天气。再返回。回新闻。这就是Stack。第十五幕 课堂实践三——字符串反转输入hello要求输出olleh思路依次把每个字符压入栈。h e l l o然后不断top() pop()输出olleh参考程序#includeiostream #includestack using namespace std; int main() { stackchar st; string s; cins; for(char c:s) { st.push(c); } while(!st.empty()) { coutst.top(); st.pop(); } return 0; }输入hello输出olleh第十六幕 Stack真正的大本领——括号匹配汉克老师展示(()()) ((())) (()(问是否合法以后。学习括号匹配。全部要用Stack。今天先认识下。以后专门讲。第十七幕 DFS也离不开Stack我们学习深度优先搜索DFS。虽然递归帮我们自动维护了调用栈但如果不用递归也可以自己写一个stack来完成搜索。因此Stack 是很多算法的重要基础。Queue 和 Stack 对比Queue队列Stack栈先进先出FIFO后进先出LIFO两端操作只操作栈顶front()看队首top()看栈顶BFS 常用DFS、括号匹配、撤销操作常用画图Queue进入 → → 离开Stack ↑ push ↓ pop本课总结今天我们认识了Stack栈。它最大的特点就是后进先出LIFOLast In First Out。掌握了五个最常用的成员函数成员函数作用生活中的理解push(x)压入栈顶放一个新盘子到最上面pop()删除栈顶拿走最上面的盘子top()查看栈顶看最上面的盘子size()元素个数数一数盘子有多少个empty()是否为空看盘子塔是否已经空了一句话口诀盘子高高往上放后来盘子先离场push往上压pop从上拿top看顶部empty看有没有学会 Stack 不发愁DFS、括号全都有为什么递归像 Stack我们同学很多会递归却不知道为什么会出现函数调用栈。举例小明要完成任务A但任务A需要先完成任务B任务B又需要先完成任务C。于是执行顺序变成开始A ↓ 开始B ↓ 开始CC 完成后再返回 B结束A ↑ 结束B ↑ 结束C这和盘子一模一样调用函数不断push。函数结束不断pop。同学们现在就更加理解什么是压栈push、什么是出栈pop。
STL课程第六课《魔法盘子塔——认识Stack栈》本课目标理解什么是 Stack栈。掌握后进先出LIFO的特点。熟练使用push()、pop()、top()、size()、empty()。能够利用 Stack 完成简单模拟。为以后学习括号匹配、DFS、表达式计算打基础。第一幕 食堂里的盘子今天。程序王国的食堂开饭了。阿姨把盘子一个一个叠起来。画图 请问如果现在拿盘子。应该拿哪一个同学们都会回答最上面的。继续问为什么因为如果先拿最下面那个。整个盘子塔都会倒下来。所以。只能拿最上面的盘子。第二幕 什么叫后进先出第一个放进去的是①号盘子。后来放进去②号。③号。④号。⑤号。画图顶部 ⑤ ④ ③ ② ① 底部请问谁最先拿出来答案⑤号。也就是说最后放进去。最先拿出来。总结这就是后进先出英文LIFOLast In First Out后来的先走先来的后走。第三幕 Queue和Stack有什么不同画图。Queue ↑ ↑ 出 进Stack ↑ 进、出总结Queue两头操作。Stack永远只操作顶部。第四幕 请出Stack头文件#includeiostream #includestack using namespace std;创建Stack。stackint st;解释stack表示栈。int保存整数。st变量名字。第五幕 放盘子——push()先放10st.push(10);盘子10继续st.push(20);变成20 10继续st.push(30);变成30 20 10强调push永远放最上面。第六幕 拿盘子——pop()现在拿盘子。st.pop();谁离开当然30。变成20 10再st.pop();变成10老师强调pop永远删除栈顶。第七幕 看看最上面的盘子请问最上面是谁直接st.top()例如coutst.top();输出20top。就是顶部。第八幕 栈还有几个盘子st.size();例如coutst.size();输出2第九幕 栈空了吗st.empty();例如if(st.empty()) { cout没有盘子; }第十幕 Stack不能这样做请问Vectora[3]Stack可以吗答案不能。请问Queue可以遍历吗也不能。Stack更加不能。因为。Stack只能看到顶部。第十一幕 演示程序#includeiostream #includestack using namespace std; int main() { stackint st; st.push(10); st.push(20); st.push(30); cout栈顶st.top()endl; st.pop(); cout新的栈顶st.top()endl; cout元素个数st.size()endl; return 0; }输出栈顶30 新的栈顶20 元素个数2第十二幕 课堂小游戏依次执行push(5) push(8) push(2) pop() push(9)请画图。开始空↓5↓8 5↓2 8 5↓8 5↓9 8 5请问top是谁答案9第十三幕 课堂实践一——撤销功能Undo请问为什么Word里面。CtrlZ。可以撤销因为。每操作一步。都保存一次。例如输入A B CStackC B A点击撤销。就是pop()删除C。又撤销。删除B。是不是很方便第十四幕 课堂实践二——浏览器返回浏览器。访问百度 新闻 天气 地图请问点击返回。去哪地图退出。回天气。再返回。回新闻。这就是Stack。第十五幕 课堂实践三——字符串反转输入hello要求输出olleh思路依次把每个字符压入栈。h e l l o然后不断top() pop()输出olleh参考程序#includeiostream #includestack using namespace std; int main() { stackchar st; string s; cins; for(char c:s) { st.push(c); } while(!st.empty()) { coutst.top(); st.pop(); } return 0; }输入hello输出olleh第十六幕 Stack真正的大本领——括号匹配汉克老师展示(()()) ((())) (()(问是否合法以后。学习括号匹配。全部要用Stack。今天先认识下。以后专门讲。第十七幕 DFS也离不开Stack我们学习深度优先搜索DFS。虽然递归帮我们自动维护了调用栈但如果不用递归也可以自己写一个stack来完成搜索。因此Stack 是很多算法的重要基础。Queue 和 Stack 对比Queue队列Stack栈先进先出FIFO后进先出LIFO两端操作只操作栈顶front()看队首top()看栈顶BFS 常用DFS、括号匹配、撤销操作常用画图Queue进入 → → 离开Stack ↑ push ↓ pop本课总结今天我们认识了Stack栈。它最大的特点就是后进先出LIFOLast In First Out。掌握了五个最常用的成员函数成员函数作用生活中的理解push(x)压入栈顶放一个新盘子到最上面pop()删除栈顶拿走最上面的盘子top()查看栈顶看最上面的盘子size()元素个数数一数盘子有多少个empty()是否为空看盘子塔是否已经空了一句话口诀盘子高高往上放后来盘子先离场push往上压pop从上拿top看顶部empty看有没有学会 Stack 不发愁DFS、括号全都有为什么递归像 Stack我们同学很多会递归却不知道为什么会出现函数调用栈。举例小明要完成任务A但任务A需要先完成任务B任务B又需要先完成任务C。于是执行顺序变成开始A ↓ 开始B ↓ 开始CC 完成后再返回 B结束A ↑ 结束B ↑ 结束C这和盘子一模一样调用函数不断push。函数结束不断pop。同学们现在就更加理解什么是压栈push、什么是出栈pop。
