Olverae Assets

1 一句话定义

栈（stack）是一种「后进先出（LIFO）」的容器：只能在同一端放东西（push）和拿东西（pop），最后放进去的，最先被拿出来。

把它想成一摞盘子：你只能往最上面放一个、也只能从最上面取一个。想拿到底下那只，必须先把上面的都取走。最后摞上去的盘子，反而最先被拿走——这就是「后进先出」。函数调用、撤销(Ctrl+Z)、括号匹配、DFS，背后都是栈。

元素从同一端进出：10 先压入、压到最底；30 最后压入、坐在栈顶。下一节你将单步 push / pop，亲眼确认「最后进的 30 最先出来」。

2 模型 · 单步 push / pop，确认后进先出

点 ▶ 看演示：先 push 10、20、30（每个都压到栈顶），再连续 pop 两次。盯住栈顶 top 和「刚弹出」——你会看到先出来的是 30（最后进的），不是 10。

用数组实现栈：一个数组 + 一个 top 下标

最常见的栈实现：用数组存元素，再用一个整数 top 记「下一个空位 / 当前元素个数」。

int s[MAX];
int top = 0;              // top = 当前元素个数（也是下一个空位下标）

void push(int v) { s[top++] = v; }   // 放到 s[top]，再让 top 加 1
int  pop()       { return s[--top]; }  // 先让 top 减 1，再取 s[top]
int  peek()      { return s[top-1]; } // 只看栈顶，不弹出

注意 top 的用法：push 是先用后加（s[top++]），pop 是先减后用（s[--top]）。栈顶元素永远是 s[top-1]。pop 前必须确认栈非空（top > 0），否则就「栈下溢」了。

栈演示 · push 10,20,30 然后 pop ×2

栈

栈顶 top = 0

—

刚弹出的值

代码（当前行高亮）

提示

点 ▶ 看 push/pop。push 把新值压到栈顶（top++），pop 从栈顶取走（--top）。最后压入的最先弹出。

3 核心要点 · 4 句人话吃透栈

每张卡片先一句大白话。重点：LIFO、两种实现、典型用途、和队列的对照。

① 只在一端进出（LIFO）

一句话：push 和 pop 都在「栈顶」这一端，最后进的最先出。底下的元素被压着，动不了。

三个核心操作：push（压入栈顶）、pop（弹出栈顶并返回）、peek/top（只看栈顶不弹）。都只碰栈顶，所以都是 O(1)。

② 两种实现：数组 or 链表

一句话：数组版用一个 top 下标；链表版就是「头插 + 头删」——链表的头插法天生就是个栈。

数组栈：简单快，但容量固定（满了会溢出）。链表栈：在 head 处插入/删除（O(1)），容量随意。两者都满足 LIFO。

③ 典型用途

一句话：凡是「后做的先撤、要原路返回」的场景都用栈。

函数调用栈（递归靠它）、撤销 Ctrl+Z、括号/表达式匹配、DFS、进制转换（余数倒序输出，正好用栈翻过来）。最后一个就是 2521 21T3 Q4 考的。

④ 栈 vs 队列

一句话：栈是 LIFO（后进先出），队列是 FIFO（先进先出）——一个翻转顺序，一个保持顺序。

DFS 用栈（扎到底再回头），BFS 用队列（逐层）。把图遍历里的栈换成队列，深度优先就变成了广度优先。

栈: 进 1,2,3 → 出 3,2,1 (反序) 队列: 进 1,2,3 → 出 1,2,3 (原序)

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是用栈最常翻车的坑——空栈还 pop、固定容量压爆、peek 和 pop 混用、top 下标差一。点击卡片看运行效果。

① 空栈还 pop（下溢）

没判 top>0 → top 变负、读到栈外垃圾

② 满栈还 push（溢出）

没判 top<MAX → 写到数组外，越界

③ 该 peek 却 pop

只想看栈顶却把它弹掉了，元素丢失

④ 栈顶下标差一

用 s[top] 当栈顶 → 其实是空位，应是 s[top-1]

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题正对栈套路：LIFO 顺序、出栈结果、空栈处理、典型用途、进制转换为何用栈。最后到练习系统亲手用栈做括号匹配。

去做例题：栈 · 括号匹配

去做例题

Stacks

栈