浅谈数据结构之栈

栈属于一种后进先出，先进后出的一种数据结构。这有点像往一个箱子里面放东西，最开始放的东西被压倒的箱底，只能先取出放在箱子最上面的物体，再取出箱底的物体。

浏览器的前进和后退也可以看做是栈的应用。当点击一个新的网页的时候，相当于把当前的页面压入栈中，当后退的时候，再从栈里弹出，栈为空的时候，就代表不能后退了。

所以，对于栈来说，操作比较单一，只有入栈和出栈的操作，虽然限制比较多，但是会让数据的处理更加的简单而且可控。

比如要实现一个括号匹配的效果，就可以用栈来实现。

左括号主要包括['(', '{', '[']，右括号主要包括[')', '}', ']']，所以，当给定一个字符串的时候，如果遇到左括号，就将左括号入栈，如果遇到右括号，就将栈顶的元素弹出，看是否能和右括号匹配上，这样就实现了括号的匹配检测。

主要代码实现如下

function checkValide(str: string) {
  const left = ['(', '{', '['];
  const right = [')', '}', ']'];
  const stack: string[] = [];
  for (let i = 0; i < str.length; i++) {
    const currentStr = str[i];
    if (left.indexOf(currentStr) > -1) {
      stack.push(currentStr);
    }
    if (right.indexOf(currentStr) > -1) {
      const tag = stack.pop();
      if (tag) {
        const index = left.indexOf(tag);
        if (right[index] !== currentStr) {
          return false;
        }
      }
    }
  }
  if(stack.length) return false;
  return true;
}

console.log(checkValide('{[asdadasd]}')); // 输出：true
console.log(checkValide('{[asdadasd}]')); // 输出：false