一起动脑筋 · 先看一个小故事
女孩把红盘、蓝盘、黄盘依次叠起来。要拿盘子时，只从最上面拿。
把过程摊开来看
- 放红盘底部
- 放蓝盘红盘上方
- 放黄盘栈顶
- 取出顺序黄、蓝、红
栈按后进先出的规则操作。
入栈把元素放到顶部，出栈取走顶部。函数调用、括号匹配等问题都能用到这种顺序。
最后放入的先取出
从左到右表示栈底到栈顶，最右边是可以取出的元素。
红盘
红盘是当前栈顶。
红盘蓝盘
蓝盘成为新的栈顶。
红盘蓝盘黄盘
最后放入黄盘，所以先取黄盘。
红盘蓝盘
黄盘已取走，现在轮到蓝盘位于栈顶。
01什么是栈？
栈（Stack）是一种只在同一端进行主要插入和删除的数据结构。
这一端叫栈顶（top）。
02为什么像一摞盘子？
盘子 C ← 最上面盘子 B盘子 A
最后放上去的盘子 C，会最先被拿走。
后进先出（LIFO）
03push、pop、top 是什么？
push
把新元素压到栈顶。
pop
移除栈顶元素。
top
查看当前栈顶元素。
04栈是怎样变化的？
空栈→ push AA→ push BB / A→ popA
每次只从栈顶进出。
05栈能解决什么问题？
- 函数调用栈
- 撤销操作
- 括号匹配
- 表达式处理
- DFS 的某些实现
06C++ 里怎样使用栈？
#include <stack>
std::stack<int> s;
s.push(10);
s.push(20);
std::cout << s.top(); // 20
s.pop();pop() 只移除元素，不返回被移除的值，因此如果要使用它，通常先 top() 再 pop()。
07栈一定是连续内存吗？
不一定。
std::stack 是一种容器适配器，默认通常使用 std::deque 作为底层容器，也可以使用其他满足要求的容器。
你已经知道了什么
- 栈遵循后进先出。
- 主要操作发生在栈顶。
- push 压入，pop 移除，top 查看栈顶。
- 栈适合表达“最近加入的先处理”。
- 栈的逻辑模型不等于具体内存布局。
下一篇：队列：像排队买票
轮到你来试一试
依次放入 1、2，再取出一个，取到谁？
想好了吗？点开看解释
2。它最后进入，位于栈顶；取走后 1 才成为栈顶。