数据结构：栈 (Stack)

什么是栈？

栈是一种遵循 后进先出 (LIFO, Last-In, First-Out) 原则的线性数据结构。可以把它想象成一摞盘子：你只能在顶部放盘子，也只能从顶部取盘子。

基本操作

• Push: 在栈顶添加一个元素。
• Pop: 移除并返回栈顶的元素。
• Peek (或 Top): 查看栈顶元素，但不移除它。
• IsEmpty: 检查栈是否为空。

C++ STL 中的 std::stack

C++ 标准模板库 (STL) 提供了 std::stack 容器适配器。

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(10);
    s.push(20);
    s.push(30);

    std::cout << "Top element is: " << s.top() << std::endl; // 30

    s.pop();
    std::cout << "Top element is: " << s.top() << std::endl; // 20

    std::cout << "Stack size is: " << s.size() << std::endl;

    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;

    return 0;
}

应用场景

• 函数调用: 程序中的函数调用就是通过栈来管理的。
• 表达式求值: 将中缀表达式转换为后缀或前缀表达式，并进行求值。
• 括号匹配: 检查代码或表达式中的括号是否成对出现。
• 深度优先搜索 (DFS): 可以用显式的栈来实现 DFS 遍历。
• 撤销/重做功能: 编辑器中的 Undo/Redo 功能。