# 栈
- 栈结构，后进先出，先进后出；操作受限的线性表，只允许在一端插入和删除数据；入栈、出栈的时间复杂度都为 O(1)
- 栈的限制，栈有什么优势？特定的数据结构是对特定场景的抽象，数组或链表暴露了太多的操作接口，在使用时就比较不可控；当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

- 基于数组或链表实现栈；
    - 基于数组的，支持动态扩容的顺序栈；摊还分析，入栈、出栈的时间复杂度仍为 O(1)

# 栈的实际使用：
- 浏览器的前进、后退功能
    - 使用两个栈 X、Y，将浏览的网页依次压入栈 X，当点击后退按钮时，再依次从 X 中出栈，并将出栈的数据依次放入栈 Y；点击前进按钮时，则从栈 Y 中取出数据，放入 X 中。
    - 从当前页面跳转到新的页面时，栈 Y 中的页面会被清空，无法再通过前进后退查看了。
- 栈在函数调用中的应用：
    - 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
- 栈在表达式求值中的应用：
    - 如计算表达式 `34 + 13 * 9 + 44 - 12 / 3`，编译器通过两个栈来实现；一个栈保存操作数，另一个保存运算符； 
    - 从左向右遍历表达式，当遇到数字，直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。 
    - 比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较
- 栈在括号或标签匹配中的应用   


# LeetCode：栈