栈 Stack

栈（Stack）是一种线性数据结构，它遵循“后进先出”（LIFO，Last In First Out）原则，即最后加入的元素最先被取出。栈通常用于实现需要“反向”操作的算法和数据结构。

栈的特点：

• 后进先出（LIFO）：栈的访问顺序遵循后进先出的原则，最后插入的元素最先被移除。
• 操作限制：栈只允许在一端进行插入和删除操作，这一端通常被称为栈顶（Top）。
• 动态增长：栈可以根据需要动态地扩展或收缩（对于动态数组实现的栈）。
• 存储结构：栈可以使用数组或链表来实现。

栈的常见操作：

• push：将一个元素添加到栈顶。
• pop：移除栈顶元素，并返回该元素的值。
• peek（或 top）：查看栈顶元素的值，但不移除它。
• isEmpty：检查栈是否为空。
• size：返回栈中元素的个数。

栈的应用：

• 递归调用的实现：计算机的函数调用使用栈来管理函数的调用和返回。当一个函数调用时，它的返回地址和局部变量会被压入栈中，函数执行完毕后从栈中弹出返回地址。
• 表达式求值：栈常用于表达式的求值和解析，特别是在中缀表达式、后缀表达式和前缀表达式的转换和计算中。
• 深度优先搜索（DFS）：栈用于深度优先搜索（DFS）算法，通过栈记录搜索路径，实现图的遍历。
• 回溯算法：在回溯算法中，栈用于记录当前的选择和路径，便于回退到上一步状态。

栈的示例（C++）：

#include <iostream>
#include <stack> // 引入stack头文件
using namespace std;

int main()
{
    stack<int> st; // 创建一个空栈

    // push操作：压栈
    st.push(10); // 压入10
    st.push(20); // 压入20
    st.push(30); // 压入30

    // peek操作：查看栈顶元素
    cout << "栈顶元素: " << st.top() << endl; // 输出: 30

    // pop操作：弹出栈顶元素
    st.pop(); // 弹出30

    // 打印栈顶元素
    cout << "弹出栈顶元素后, 栈顶元素: " << st.top() << endl; // 输出: 20

    // isEmpty操作：检查栈是否为空
    if (!st.empty())
    {
        cout << "栈不是空的!" << endl; // 输出: 栈不是空的!
    }

    // size操作：获取栈的大小
    cout << "栈的大小: " << st.size() << endl; // 输出: 2

    return 0;
}

代码解析：

• push：将元素压入栈中。
• top：查看栈顶元素的值。
• pop：移除栈顶元素。
• empty：检查栈是否为空。
• size：返回栈的元素数量。

栈的优缺点：

优点：

• 时间效率高：栈的插入和删除操作通常为 O(1) 时间复杂度，因此在许多需要频繁插入和删除操作的场景中，栈非常高效。
• 简单的操作：栈的操作非常简单，只需要知道栈顶元素，并根据栈顶进行插入或删除操作。

缺点：

• 访问受限：栈只允许访问栈顶的元素，不能直接访问栈中的其他元素，因此它并不适用于需要随机访问元素的场景。
• 空间限制：栈的大小是有限的，如果栈中的元素太多，可能会发生栈溢出（尤其是递归调用时，栈空间可能会用尽）。

栈的应用实例：

• 括号匹配：栈可以用于检测表达式中的括号是否匹配，特别是在编译器中，栈用于解析代码中的括号、花括号、方括号等。
• Undo（撤销）操作：在许多应用程序中，撤销功能通常是通过栈来实现的，每次执行操作时，将当前状态压入栈中，撤销时从栈中弹出之前的状态。
• 表达式求值：栈用于处理中缀、前缀、后缀表达式的转换和计算。

总结：

栈是一种常见的线性数据结构，具有后进先出的特点，广泛应用于各种计算机科学和算法问题中。它的简单性和高效性使其成为实现许多算法和数据结构的基础。在需要跟踪状态或执行回溯操作的场景中，栈是非常有用的工具。