栈

一、栈是什么？

• 一个后进先出(First In Last Out)的数据结构，简称 FILO 结构
• JavaScript 中没有栈，但可以用 Array 实现栈的所有功能

二、简易示例

示例源码

const stack = []
stack.push(1)
stack.push(2)
const a = stack.pop()   // 注：后进先出，a的值为 2
const b = stack.pop()   // b 值为 1

其中，变量 a 值为 2，b 值为 1。

三、什么场景下用栈？

需要考虑后进先出的场景都可以用栈，举例如下：

• 十进制转二进制
• 判断字符串的括号是否有效
• 函数调用堆栈

3.1 场景一：十进制转二进制

要将十进制转成二进制，如下图所示，发现后出来的余数反而要排到前面。

解题思路：将余数依次入栈，然后再出栈，就可以实现余数倒序输出。

3.2 场景二：有效的括号

场景：给一些字符串，里面都是括号这样的字符，然后判断字符串里的括号是否是有效的(有效指的是可以有效地闭合)。

((((()))))    -- VALID
()()()()      -- VALID
((((()        -- INVALID
((()(())))    -- VALID

解题思路：通过观察发现，越靠后的左括号，对应的右括号越靠前。所以可以遍历字符串，将左括号入栈，右括号出栈，最后栈空了就是合法的。

3.3 场景三：函数调用堆栈

对于相互调用的函数而言，代码示例如下，发现最后调用的函数，会最先执行完。所以在JS解释器中，也是利用栈来控制函数的调用顺序。

function greeting(){
    // ...
  sayHi()
  // ...
}
function sayHi() {
  return "Hi"
}
greeting()