小学生学C++编程语法知识（STL容器（6、认识Stack（栈）））

STL课程

第六课：《魔法盘子塔——认识Stack（栈）》

本课目标

1. 理解什么是 Stack（栈）。

2. 掌握后进先出（LIFO）的特点。

3. 熟练使用push()、pop()、top()、size()、empty()。

4. 能够利用 Stack 完成简单模拟。

5. 为以后学习括号匹配、DFS、表达式计算打基础。

第一幕 食堂里的盘子

今天。

程序王国的食堂开饭了。

阿姨把盘子一个一个叠起来。

画图：

🍽 🍽 🍽 🍽 🍽

请问：

如果现在拿盘子。

应该拿哪一个？

同学们都会回答：

最上面的。

继续问：

为什么？

因为：

如果先拿最下面那个。

整个盘子塔都会倒下来。

所以。

只能拿最上面的盘子。

第二幕 什么叫后进先出？

第一个放进去的是：

①号盘子。

后来放进去：

②号。

③号。

④号。

⑤号。

画图：

顶部 ⑤ ④ ③ ② ① 底部

请问：

谁最先拿出来？

答案：

⑤号。

也就是说：

最后放进去。

最先拿出来。

总结：

这就是：

后进先出

英文：

LIFO

（Last In First Out）

后来的先走，先来的后走。

第三幕 Queue和Stack有什么不同？

画图。

Queue：

😀 😀 😀 😀 ↑ ↑ 出 进

Stack：

🍽 🍽 🍽 ↑ 进、出

总结：

Queue：

两头操作。

Stack：

永远只操作：

顶部。

第四幕 请出Stack

头文件：

#include<iostream> #include<stack> using namespace std;

创建Stack。

stack<int> st;

解释：

stack

表示：

栈。

int

保存整数。

st

变量名字。

第五幕 放盘子——push()

先放：

10

st.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()

例如：

cout<<st.top();

输出：

20

top。

就是：

顶部。

第八幕 栈还有几个盘子？

st.size();

例如：

cout<<st.size();

输出：

2

第九幕 栈空了吗？

st.empty();

例如：

if(st.empty()) { cout<<"没有盘子"; }

第十幕 Stack不能这样做

请问：

Vector：

a[3]

Stack：

可以吗？

答案：

不能。

请问：

Queue：

可以遍历吗？

也不能。

Stack：

更加不能。

因为。

Stack只能看到：

顶部。

第十一幕 演示程序

#include<iostream> #include<stack> using namespace std; int main() { stack<int> 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里面。

Ctrl+Z。

可以撤销？

因为。

每操作一步。

都保存一次。

例如：

输入：

A B C

Stack：

C B A

点击：

撤销。

就是：

pop()

删除：

C。

又撤销。

删除：

B。

是不是很方便？

第十四幕 课堂实践二——浏览器返回

浏览器。

访问：

百度 新闻 天气 地图

请问：

点击：

返回。

去哪？

地图退出。

回：

天气。

再返回。

回：

新闻。

这就是：

Stack。

第十五幕 课堂实践三——字符串反转

输入：

hello

要求：

输出：

olleh

思路：

依次把每个字符压入栈。

h e l l o

然后不断：

top() pop()

输出：

olleh

参考程序：

#include<iostream> #include<stack> using namespace std; int main() { stack<char> st; string s; cin>>s; for(char c:s) { st.push(c); } while(!st.empty()) { cout<<st.top(); st.pop(); } return 0; }

输入：

hello

输出：

olleh

第十六幕 Stack真正的大本领——括号匹配

汉克老师展示：

(()()) ((())) (()(

问：

是否合法？

以后。

学习：

括号匹配。

全部要用：

Stack。

今天先认识下。

以后专门讲。

第十七幕 DFS也离不开Stack

我们学习：

深度优先搜索（DFS）。

虽然递归帮我们自动维护了"调用栈"，

但如果不用递归，也可以自己写一个stack来完成搜索。

因此：

Stack 是很多算法的重要基础。

Queue 和 Stack 对比

画图

Queue

进入 → 😀 😀 😀 → 离开

Stack

🍽 🍽 🍽 ↑ push ↓ pop

本课总结

今天，我们认识了Stack（栈）。

它最大的特点就是：

后进先出（LIFO，Last In First Out）。

掌握了五个最常用的成员函数：

一句话口诀

盘子高高往上放，后来盘子先离场；
push往上压，pop从上拿；
top看顶部，empty看有没有；
学会 Stack 不发愁，DFS、括号全都有！

"为什么递归像 Stack？"

我们同学，很多会递归，却不知道为什么会出现"函数调用栈"。

举例：

小明要完成任务A，但任务A需要先完成任务B；任务B又需要先完成任务C。

于是执行顺序变成：

开始A ↓ 开始B ↓ 开始C

C 完成后，再返回 B：

结束A ↑ 结束B ↑ 结束C

这和盘子一模一样：

• 调用函数：不断push。

• 函数结束：不断pop。

同学们，现在就更加理解什么是"压栈（push）"、什么是"出栈（pop）"。