栈（Stack）

算法原理

栈是后进先出（LIFO, Last In First Out）的线性结构：只允许在栈顶一端操作——push 压入、pop 弹出、peek 窥看栈顶但不取走。最后放进去的盘子必须最先被拿走，这正是"栈"这个名字的由来。它结构极简，却是计算世界的顶梁柱：函数调用栈、表达式求值、括号匹配、深度优先搜索、撤销操作（Ctrl+Z），底层都是一根栈。

本动画在容量 6 的栈上演一套标准操作序列，一操作一拍：

push 3 → push 7 → push 12   （栈：底 3 7 12 顶）
peek                        （栈顶 12 亮一下，栈不变）
pop → pop                   （弹出 12、弹出 7——后进的先出）
push 5                      （栈：底 3 5 顶）
✓ 完成 ｜ 栈深 2 · 4 进 2 出

关键看点在两次 pop：先弹出的是最后压入的 12，再弹出 7——LIFO 不是口号，是出栈顺序本身。

动画怎么看

• 居中一列卡片：栈本体，栈底在下、栈顶在上，卡片自下而上堆叠；
• push 拍：新卡在栈顶位置淡入，栈顶标记上移一格；
• peek 拍：栈顶卡转 warning 亮一下——只看不拿，栈深不变；
• pop 拍：栈顶卡向右滑动淡出，栈顶标记回落一格；
• top 指针：常驻栈顶旁的三角标记，永远指向下一个 push 的落点；
• 状态行：push 12 ｜ 入栈 / pop ｜ 弹出 12 / ✓ 完成 ｜ 栈深 2 · 4 进 2 出。

复杂度分析

C++ 参考代码

#include <iostream>
using namespace std;

class Stack {
    int a[6];          // 底在下，top 是下一个空位
    int top = 0;
public:
    bool empty() const { return top == 0; }
    bool full()  const { return top == 6; }
    void push(int v) {
        if (full()) { cout << "溢出\n"; return; }
        a[top++] = v;               // 入栈：顶上放一个
    }
    int peek() const { return a[top - 1]; }   // 看栈顶，不取
    int pop() {
        if (empty()) { cout << "下溢\n"; return -1; }
        return a[--top];            // 出栈：从顶上拿走
    }
};

int main() {
    Stack s;
    s.push(3); s.push(7); s.push(12);
    cout << s.peek() << endl;       // 12（栈深仍为 3）
    cout << s.pop()  << endl;       // 12 —— 后进的先出
    cout << s.pop()  << endl;       // 7
    s.push(5);                      // 栈内：3 5
    return 0;
}

什么时候用栈

问题的解法天然呈现"最近的相关"关系时，就该上栈：括号匹配（最近的左括号等着被配对）、表达式求值（运算符栈）、函数调用（谁调用谁返回，调用栈管到底）、DFS（回溯的顺序就是弹栈的顺序）、文本编辑器的撤销（最后做的操作最先被撤销）。栈也常作为"把递归改迭代"的桥——显式栈接管调用栈，既保住 DFS 语义又绕开爆栈风险。用数组实现时唯一的坑是判满与判空：pop 空栈、push 满栈都是事故，本动画的容量 6 与栈深计数就是这两个守门员。