关于栈的理解以及实际应用场景

[maicFir]

栈是一种数据结构，在 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

6、本题来源leetcode-20