浅谈数据结构之栈

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

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

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

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

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

主要代码实现如下

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
如果您觉得本文对您有用,欢迎捐赠或留言~
微信支付
支付宝

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注