栈在数据结构与算法中的应用

栈是一种线性数据结构，它遵循特定的操作规则，即后进先出（LIFO，Last In First Out）。这意味着最后一个被添加到栈中的元素将是第一个被移除的元素。在计算机科学中，栈被广泛应用于各种场景，如解析表达式、后缀/中缀/前缀算术表达式、函数调用和递归等。

栈的基本操作包括：

压栈（Push）：在栈顶添加一个元素。

弹栈（Pop）：删除栈顶的元素并返回该元素。

查看栈顶（Peek/Top）：返回栈顶的元素但不删除。

栈是否为空（Empty）：检查栈中是否有元素。

栈的元素个数（Size）：获取栈的元素个数。

栈的一种常见实现是使用数组。在这种情况下，压栈操作可以通过将元素添加到数组的末尾来完成，而弹栈操作可以通过删除数组的最后一个元素来完成。

另一种常见的栈实现是使用链表。在这种情况下，每个节点都包含一个数据元素和一个指向下一个节点的指针。压栈操作可以通过在链表末尾添加一个新节点来完成，而弹栈操作可以通过删除链表的最后一个节点来完成。

// stack.cpp// 编译运行// g++ -g stack.cpp -o stack && ./stack// 程序输出// Top element: 3// Stack element szie: 3// Top element after popping: 1// Stack is not empty#include <iostream>#include <stack>int main() {    std::stack<int> myStack;    myStack.push(1);    myStack.push(2);    myStack.push(3);    std::cout << "Top element: " << myStack.top() << std::endl;    std::cout << "Stack element szie: " << myStack.size() << std::endl;    myStack.pop();    myStack.pop();    std::cout << "Top element after popping: " << myStack.top() << std::endl;    if (myStack.empty()) {        std::cout << "Stack is empty" << std::endl;    } else {        std::cout << "Stack is not empty" << std::endl;    }    return 0;}

栈