栈

1、栈是一种后进者先出，先进者后出的数据结构
2、用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈
3、栈的时间复杂度为 O(1)；往一个要先扩容的栈内添加一个数据，均摊之后时间复杂度也为O(1)
4、常见栈的使用场景
4.1、用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量入栈，当被调用函数执行完成，返回之后，将这个函数对应的变量出栈
4.2、表达式求值中的应用。比如：34+13*9+44-12/3这个运算，编译器就是通过两个栈来实现的，其中一个保存操作数的栈，另一个是保存运算符的栈，从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较；如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较
4.3、在括号匹配中的应用。比如，{[]()[{}]}或{[}()]检查哪个合法，用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式
4.4、浏览器前进后退功能。我们使用两个栈，X 和 Y，我们把首次浏览的a, b, c页面依次压入栈 X，当点击后退按钮时，从栈 X 中出栈c，并将出栈的c放入栈 Y，此时跳转到新的页面 d 了，此时需要清空栈 Y，页面 c 就无法再通过前进按钮重复查看了