栈 Stack

是一种常见的数据结构，它遵循一种称为“后进先出”（Last-In-First-Out，LIFO）的原则。在栈中，最后添加的元素首先被移除，而最先添加的元素最后被移除。

栈可以使用数组或链表来实现。数组实现的栈可以使用固定大小的数组，或者可以动态调整大小。链表实现的栈没有大小限制，并且可以方便地进行元素的插入和删除。

使用场景

• 函数调用：栈可用于跟踪函数调用的顺序和返回地址。
• 表达式求值：栈可以用于解析和求解表达式，如中缀表达式转后缀表达式，并计算后缀表达式的值。
• 撤销操作：栈可用于实现撤销/重做功能，将操作记录在栈中以便回退和恢复状态。
• 浏览器历史记录：浏览器可以使用栈来跟踪用户浏览历史记录，使用户能够返回到之前访问的页面。
• 深度优先搜索（DFS）：在图遍历中，栈可以用于实现深度优先搜索算法。