栈：后进先出

一摞盘子

想象食堂里高高的一摞盘子。你把盘子加在最上面，也从最上面取盘子，绝不会从中间抽一个。最后放上去的盘子最先被取走——这就是后进先出，即 LIFO。

栈是一种抽象数据类型：它由你能对它*做什么*来定义，而不是由它怎么实现来定义。真正的操作只有三个。

push(x)：把 x 放到栈顶。
pop()：移除并返回栈顶元素。
top() / peek()：查看栈顶元素但不移除。

push 3        top -> | 3 |
              |       | 2 |
              v       | 1 |
                      '---'   bottom

pop  -> 3     top -> | 2 |
                      | 1 |
                      '---'

压栈加到顶部；弹栈从顶部移除。栈底从不变动。

使用 std::stack

C++ 标准库直接给你一个现成的栈。三种操作都在 O(1) 内完成——常数时间，无论栈有多高。

#include <stack>
#include <iostream>

std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
std::cout << s.top();   // 3 (the last one pushed)
s.pop();                // removes 3
std::cout << s.top();   // 2

std::stack：注意 pop() 只移除、不返回——要先读 top()。

自己手写一个

栈简单到你能用一个数组（或像 `std::vector` 这样的动态数组）几行就搭出来。"栈顶"不过是最后一个被填的位置——在末尾加或删都是 O(1)，无需移动元素。

#include <vector>

struct Stack {
    std::vector<int> data;
    void push(int x) { data.push_back(x); }   // O(1) amortized
    int  top()       { return data.back(); }   // O(1)
    void pop()       { data.pop_back(); }       // O(1)
    bool empty()     { return data.empty(); }
};

五个方法就是一整个栈——vector 的末端就是栈顶。

如果 vector 偶尔得扩容，为什么 `push_back` 还是 O(1)？因为扩容时容量翻倍，那次偶发的昂贵复制被摊薄到许多次便宜的压入上——这就是所谓的均摊 O(1)。你在基础篇讲动态数组时见过这一点。

栈出现在哪里

一旦你认出 LIFO 这个形状，栈无处不在。调用栈正是程序记住每次函数调用后该返回哪里的机制——每深入一层递归就压入一个栈帧，每返回一次就弹出一个。编辑器里的撤销会最先弹出你最近的那次操作。而代码里的括号匹配，是栈的经典习题。

括号匹配是这样的：从左到右扫描。遇到左括号就压入；遇到右括号就弹出并检查是否配对。一旦出现不匹配，或扫描结束时栈不为空，括号就不平衡。

// Is a string of () [] {} balanced?
bool balanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c=='(' || c=='[' || c=='{') st.push(c);
        else {
            if (st.empty()) return false;          // closer with nothing open
            char o = st.top(); st.pop();
            if ((c==')'&&o!='(') || (c==']'&&o!='[') ||
                (c=='}'&&o!='{')) return false;     // wrong match
        }
    }
    return st.empty();   // leftover openers => unbalanced
}

经典的栈用法：栈顶永远是最近打开、尚未闭合的那个括号。