栈

什么是栈

栈是一种线性的 后进先出 的数据结构，其规定了数据只能在栈顶进行操作，要么从栈顶压入数据，要么从栈顶弹出数据

生活中就有类似栈的例子，比如吃完饭，将盘子一个一个摞起来，然后洗盘子的时候，从摞起来的盘子中的顶部拿一个来洗，这就是类似栈的操作，先放的盘子在底部，后放的盘子在顶部，后放的盘子先被洗( 弹出 )

栈的操作的时间复杂度都是 O(1)，因为其只涉及在栈顶的压入或者弹出操作，不涉及别的额外的操作

栈的应用

在函数调用中的应用

内存中 '栈' 这块内存地址被用来 存储函数调用时的临时变量，每执行一个函数，就会将其临时变量装成一个 栈帧 入 '栈'，在其执行完毕之后，再将其所对应的 栈帧 出栈

function sum(a, b) {
  var sum = a + b;
  return sum;
}

var a = 1;
var b = 2;
sum(a, b);

栈帧

在表达式求值中的应用

对于求值表达式，类似 3+2*1-5 这种，我们也可以通过栈来计算其结果
其步骤如下：

1. 创建两个栈用来存放 运算符 和 操作数
2. 循环目标字符串
3. 当前运算符如果比栈顶的运算符优先级要高，则入栈，否则，弹出栈顶运算符，进行运算，结果入操作数栈

在括号匹配中的应用

栈可以用来判断字符串中的括号是否对应，例如 '()'、'[]'、'{}'、')('，最后一个就是对应不上的

1. 遇到左括号，入栈
2. 遇到与栈顶左括号匹配的右括号，出栈
3. 结束时，栈非空，则表示不匹配

实现浏览器前进、后退功能

使用两个栈来保存浏览历史和后退操作

被点击的 url 入栈1，点击后退，栈1顶部的 url 出栈入栈2，点击前进，栈2顶部的 url 出栈入栈1，当栈1有新的 url 入栈时，清空栈2，相当于 栈2保存的是后退的操作记录

浏览器前进后退

思考

1. 内存中的栈和上面所说的栈是一样的吗？

内存中的堆栈 和 数据结构的堆栈是不一样的，内存中的堆栈是 真实的物理地址区域，数据结构的堆栈是抽象出来的数据存储结构，在内存物理地址上做了和逻辑数据结构一样的操作( 出栈，入栈... )，就将其类比称为对应的数据结构

2. 为什么函数调用要用栈这种数据结构，用其它数据结构不行吗？

其实用其它数据结构也可以，不过在函数嵌套调用时，栈最符合这种 后进先出 的逻辑，所以用栈是最好的选择。从调用函数进入被调用函数，对于数据只是作用域的变化，使用栈的话，被调用函数执行完毕之后出栈，正好回到调用函数的作用域