C++ stack

平时洗完碗把盘子一摞一摞叠起来时，有一个很明显的规律：最后放到最上面的那个盘子，拿取时总是第一个被端走，如下图所示。

在编程中，这种 “后放进去的数据先拿出来” 的结构叫做 “栈（stack）”。它遵循的规则简称为 LIFO，也就是 “Last In, First Out（后进先出）” 的缩写。当程序每次只需要处理 “最后放进去的那个数据” 时，我们就可以使用 C++ 标准库提供的 std::stack。

C++ stack 的定义与常用操作

在 C++ 中，std::stack 属于 “容器适配器”。为什么叫适配器呢？因为它自己并不从头管理内存，而是默认把前面学过的 std::deque 包装在内部，相当于给双端队列套上了一个 “只在顶部开口的圆筒外壳”：把底部和中间的读写入口全部封住，只留最上面一个口子进出数据。

对于 stack 来说，这个唯一能够进出数据的顶部位置叫做 “栈顶（top）”。使用 std::stack 之前，我们需要先引入 <stack> 头文件。

语法：

#include <stack>

std::stack<元素类型> 变量名;

说明：

尖括号 <> 里指定栈中保存的元素类型即可，比如 std::stack<int> nums; 就定义了一个用来存放整数的空栈。

需要注意，std::stack 不能像 std::vector 那样直接写 {10, 20, 30} 花括号列表来赋初值，平时都是先创建一个空栈，再调用成员函数把元素一个个放进去。std::stack 的常用操作如下表所示。

C++ stack 的基本操作

操作 std::stack 时，最常用的就是 push()、top() 和 pop() 这 3 个函数。这里有一条规则小伙伴们要先记牢：pop() 的返回值类型是 void，它只负责把栈顶元素删掉，不会返回被删掉的值。如果出栈前还需要用到栈顶元素，我们需要先调用 top() 把值保存下来，再调用 pop() 删除。

示例 1：入栈、查看栈顶与出栈

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> history;

    history.push("打开文档");            // 依次压入 3 条操作记录
    history.push("修改标题");
    history.push("保存文档");

    std::cout << "当前栈顶：" << history.top() << '\n';

    std::string last = history.top();    // 先保存栈顶元素
    history.pop();                       // 再弹出栈顶元素

    std::cout << "已撤销：" << last << '\n';
    std::cout << "新栈顶：" << history.top() << '\n';
    std::cout << "剩余数：" << history.size() << '\n';
    return 0;
}

运行结果如下。

当前栈顶：保存文档
已撤销：保存文档
新栈顶：修改标题
剩余数：2

分析：

在这个例子中，3 条操作记录按照 “打开文档 → 修改标题 → 保存文档” 的先后顺序通过 push() 压入 history 栈中。因为 "保存文档" 是最后一个放进去的，所以它正好处在栈顶位置，第一次调用 history.top() 看到的就是 "保存文档"。

接着我们先把 history.top() 保存到变量 last 中，再调用 history.pop() 将其从栈顶移除。当最上面的 "保存文档" 被移走后，原本压在它下面的 "修改标题" 就露了出来，成为新的栈顶，此时剩余元素个数变为 2。

如果想要把 stack 里的所有元素按照 “后进先出” 的顺序一个个取出来处理，又应该怎么写呢？在实际开发中，我们通常配合 while 循环和 !s.empty() 依次读取并弹出栈顶元素。请看下面例子。

示例 2：依次弹出全部元素

#include <iostream>
#include <stack>

int main() {
    std::stack<int> nums;
    nums.push(10);
    nums.push(20);
    nums.push(30);

    while (!nums.empty()) {
        std::cout << nums.top() << ' ';    // 先读取栈顶
        nums.pop();                        // 再弹出栈顶
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

30 20 10

分析：

从运行结果可以看出，入栈时的顺序是 10、20、30，而在循环中每次从栈顶取出的顺序刚好反过来，变成了 30 20 10。当最后一个元素 10 被 pop() 弹出后，nums.empty() 变为 true，循环自动结束。

另外还要留意，std::stack 没有提供 clear() 成员函数。如果需要直接清空整个栈，除了像上面这样循环弹出之外，也可以直接写成 nums = {}; 赋一个新的空栈。

为了严格保证 “后进先出” 的规则，std::stack 专门屏蔽了下标 []、at() 以及迭代器接口。压在栈底和中间的元素，必须等它上面的元素全部 pop() 移走之后才能访问到。因此，对 stack 直接使用下标读取会在编译时报错：

std::stack<int> nums;
nums.push(10);
std::cout << nums[0] << '\n';    // 不支持 [] 下标访问

如果我们的需求是按 “先来后到” 的排队顺序处理数据，可以使用队列 std::queue。如果是既想保留全部数据，又想随时从头到尾遍历或按下标读取，则应该直接使用 std::vector 或 std::deque。

C++ stack 的常见应用

在实际开发中，当数据的处理顺序符合 “最后进入的最先处理” 时，使用 std::stack 会非常合适，常见场景包括以下 3 类：

• 软件的撤销操作：用户依次完成了操作 A、操作 B、操作 C。当按下快捷键（Ctrl + Z）撤销时，总是先撤销最近刚完成的操作 C，再退回操作 B，最后才轮到最早的操作 A。
• 浏览器的页面后退：从网站首页点进列表页、再点进详情页时，访问路径被依次压入栈中。每点击一次左上角的【后退】按钮，就会弹出当前页并回到上一层刚浏览过的页面。
• 数据逆序与括号匹配：把一串数据按顺序依次压入栈中，再从栈顶一个个弹出来，得到的自然就是反转后的逆序结果。

下面我们通过一个示例，利用 std::stack 后进先出的特点将单词里的字符倒序输出。

示例 3：倒序输出字符串

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::string word = "lvye";
    std::stack<char> st;

    for (char ch : word) {
        st.push(ch);    // 按顺序依次压入栈中
    }

    while (!st.empty()) {
        std::cout << st.top();
        st.pop();       // 依次弹出栈顶字符
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

eyvl

分析：

遍历字符串 "lvye" 时，4 个字符按 'l' → 'v' → 'y' → 'e' 的顺序依次压入栈 st 中，最后进去的字符 'e' 位于栈顶。随后在 while (!st.empty()) 循环中依次从栈顶取出并弹出字符，输出顺序自然就反转成了 eyvl。