栈与队列 · 单步演示
栈
只能在一端（栈顶）放入和取出的线性表：最后放进去的最先拿出来。这里用一个定长数组加一个 top 下标来实现。
0
1
2
3
4
5
top = −1（在数组范围外）
出栈顺序（空）
步 001 / 013空栈，容量 6。top = −1 表示栈里没有元素。左边是栈底，右边是栈顶。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
push(x)：if top = cap−1：上溢，拒绝top ← top+1；s[top] ← xpop()：if top = −1：下溢，拒绝x ← s[top]；top ← top−1；return x
变量
| top | -1 |
|---|---|
| 容量 cap | 6 |
| 元素个数 | 0 |
| 最近的操作 | — |
复杂度
| 最好情况 | O(1) |
|---|---|
| 平均情况 | O(1) |
| 最坏情况 | O(1) |
| 额外空间 | O(n) |
push 和 pop 都只动 top 附近的一个格子，与栈里有多少元素无关。空间就是数组本身。
要点
- 函数调用、括号匹配、撤销操作、深度优先搜索都离不开栈。
- top 指向栈顶元素本身（空栈时为 −1），这是本演示采用的约定；也有写法让 top 指向下一个空位，判空判满条件要跟着改。
常见错误
pop 前不判空就会下溢，读到的是无意义的旧值甚至越界。