栈

物理结构和逻辑结构

栈和队列。这两者都属于逻辑结构，它们的物理实现既可以利用数组，也可以利用链表来完成。逻辑结构依靠物理结构实现

1. 是什么？

一个后进先出的数据结构
类似于乘电梯，后进去的人最先出来

2. 使用 js 代码实现一个栈

const stack = [];
stack.push(1);
stack.push(2);
const item1 = stack.pop();
const item2 = stack.pop();

上面代码2是后进入数组的但是是最先被移出数组的

3. 使用场景

3.1. 十进制转二进制

上面的图就是我们十进制35转二进制的过程，每次除以2然后把余数留下，直到最后的数字为0，然后我们把我们的余数按照从后往前排列也就是100011得到我们的二进制，后出来的余数反而要排到前面，所以这个余数也是后进先出

3.2. 有效的括号

我们从左到右遍历字符串，遇到左括号就执行入栈操作，遇到右括号就执行出栈操作，如果最后我们的栈是空的就是合法的

3.3. 函数调用堆栈

上面最先调用的事 greeting 函数，然后调用 sayHi ，sayHi 最后调用却最先执行完

4. 具体代码实现

4.1. 有效的括号 leetCode 题号 20

解题步骤
1). 新建一个栈
2). 遍历每一个字符串，遇到左括号就把当前的左括号push 到我们的栈中，遇到右括号先判断它是否和栈里最后一项的括号类型匹配，如果匹配就把栈里最后一项左括号出栈，类型不匹配直接判定不合法。
3). 字符串遍历完成栈空了就合法，否则不合法。

var isValid = function(s) {
    if (s.length % 2 === 1) {
        return false;
    }
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        if (['(', '{', '['].includes(s[i])) {
            stack.push(s[i])
        } else {
            const lastS = stack[stack.length - 1]
            if (
                lastS === '(' && s[i] === ')' ||
                lastS === '{' && s[i] === '}' ||
                lastS === '[' && s[i] === ']'
                ) {
                    stack.pop()
                } else {
                    return false
                }
        }
    }
    return stack.length === 0
};

上面代码时间复杂度是 O(n) n 是 字符串的长度，空间复杂度，因为声明了一个 stack 最差就是每一个字符串都push，所以也是 O(n)

4.2. js 中的函数调用堆栈

const func1 = () => {
  func2();
}
const func2 = () => {
  func3();
}
const func3 = () => {

}

func1()

上面代码我们执行的时候，会先把 func1 放到栈里，然后是 func2 最后是 func3，当 func3 执行完成后它先从栈里移出，然后是 func2 最后是 func1