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