栈是一种数据结构，在js中我们知道，基础数据类型是存放在栈内存中的，引用数据类型是存放在栈中的一个地址引用，实际上是存放在堆内存中，今天我们看一道leetcode题目，加深对栈的理解，匹配有效括号，这是栈的应用
题目意思是: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
要求：
1、左括号必须用相同类型的右括号闭合
2、左括号必须正确的顺序闭合
题目考察核心关于栈的使用场景，以及我们可以利用栈来解决这道题
我们先抛开这个道算法题，什么是栈，理解栈，用一个图来理解下
在js中我们可以用数组来模拟栈所具备的特性，入栈与出栈，我们常常能听到栈是先进后出，后进先出的特性，怎么理解这看着似乎都认识，但总是很烧壳的一个概念
我们用一个数组来模拟栈
入栈
// 构造一个栈结构，定义一个数组 var stack = []; // 入栈 stack.push(1); // 不断的入栈,有时也叫压栈 stack.push(2); stack.push(3，4); console.log(stack) // [1,2,3,4]
出栈
... let value = null; value = stack.pop(); // 4 被弹出来了 console.log(stack); // [1,2,3]; value = stack.pop(); // 3 被弹出来了 console.log(stack); // [1,2]; value = stack.pop(); // 2 被弹出来了 console.log(stack); // [1]; value = stack.pop(); // 1 被弹出来了 console.log(stack); // []; // 最后栈的长度就是空了
可以结合上面一张图再理解下上面入栈和出栈的代码，当每次执行出栈操作时，后面添加进来的数组依次被弹出去了。用一个比较形象的比喻就是，先上车的坐在车子尾巴上，后面上车的，站在车门口，当车子每停一次，后面进来的，站在门口的就先出去了。
言归正传，理解了栈结构特性，那么这道题就可以利用栈来解决
const isValid = (s) => { var stack = []; for (let i=0;i<s.length;i++) { const val = s[i] // 入栈操作 if (val === '(') { stack.push(')') } else if (val === '[') { stack.push(']'); // 入栈操作 } else if (val === '{') { stack.push('}'); // 入栈操作 } else if (val !== stack.pop()) { // pop取出值，后面依次比较，如果与取出的值不相等，那么就是不匹配的，返回false return false; } } return stack.length === 0 // 最后全部pop出来了，数组是空，证明全部匹配上了 }
除了这种方式还有没有其他解？我们看下其他方式
const isValid2 = (s) => { const stack = []; const map = new Map([ ['(', ')'], ['[', ']'], ['{', '}'] ]); for (let i=0;i<s.length;i++) { const c = s[i]; if (map.has(c)) { // 判断map中有key值,入栈操作 stack.push(c) } else { // 获取栈的值 const mapKey = stack[stack.length -1]; // 获取map的值 if (map.get(mapKey) === c) { stack.pop(); } else { return false; } } } return stack.length === 0 }
总结
1、理解栈结构特性，先进后出，后进先出特性
2、数组模拟栈特性,push入栈，pop出栈
3、符号匹配的应用，在循环中判断是否是(,[,{，然后入栈操作对应的对称符号，判断当前值是否不等于出栈值，那么返回false,直到stackpop出所有的值，栈长度为空，证明所有符号都匹配上了。
4、利用map映射对应的符号匹配，循环字符串，如果map有key,就把当前key添加到栈中，如果没有，那么就先在取出对应栈的key,然后用当前的key，去map.get(key)获取的值与当前值是否相等，如果相等，就pop出该值，如果不相等就直接返回false,直到循环结束，栈的长度为0,证明所有符号都匹配上了。
5、code example[1]
6、本题来源leetcode-20[2]
