概念
Stack，栈，是一种后进先出（Last In Fisrt Out ， LIFO）的数据结构。
JS的实现
JS中并没有相关的类去专门实现Stack（Java中就有专门的Stack类被封装在jdk中， 当然这也是比较简单的）。但是JS对数组的相关操作可用用来模拟栈的行为，换句话说，数组可用当作栈来使用。
- 将操作对象压入栈push()；
- 将操作对象弹出栈pop()， 这个方法返回该出栈对象;
函数的调用栈
栈在计算机中用途及其广泛。
最基础的应该是函数的调用。
比如下面简单的例子中，存在调用关系 a ，调用 b， b调用c的关系。这个过程其实是利用了栈在维护，即函数调用栈：当我们执行这段代码最初调用了函数a，那么将a压入调用栈中，a还没有结束，却在a中调用了函数b，那么b也入栈，此时调用栈顶部是b，b还没有执行完成，调用了c，那么c，入栈。
c中没有调用任何函数，c执行完后，c从调用栈弹出，程序回到b函数中，当初将c入栈的地方继续执行，直到b执行完成，b也被弹出调用栈。程序接着回到a函数中，直到a函数执行完成，调用栈弹出a，空空如也。
其实，一个程序执行完成，其实就是函数调用栈被清空。 ```javascript const c = () => {
} const b = () => { c(); } const a = () => { b(); }
a();
面试题
有效的括号(LeetCode 20)
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
这道题的目的是判断字符串中，括号有没有正确的成对闭合，我们的思路是遍历字符串中的字符，若遇到左括号，就把左括号压栈，若遇到右括号则弹出栈顶元素，与当前字符比对是否成对。如果不成对，就可以直接认为字符串中未正确闭合，反之，匹配就继续遍历。当最终遍历完字符串的时候，栈中无元素，则认为整个字符串中括号正确闭合。
二叉树遍历（LeetCode 144）
给定一个二叉树，返回它的 前序 遍历。 示例: 输入: [1,null,2,3]
1 \ 2 / 3 输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
遍历一棵树首先想到的递归。
但是，利用栈来遍历明显更简单，这被称作迭代。
我们的思路就是，先把根结点压栈，然后循环检测栈中元素（while(stack.length !== 0)），每次弹出一个栈顶元素，这时候再分别把它的右节点和左节点压栈，进入下一个循环。可以想见，叶子节点并没有子节点，当到达一个叶子节点后，暂时没有后续节点入栈了，那么下一个出栈的就是距离最近的一个右节点。
逆波兰表达式求值（LeetCode 150）
根据 逆波兰表示法，求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
首先，何为逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
若有收获，就点个赞吧
0 人点赞
