浅谈数据结构之栈

该文章由 leevare 发布于 ,归类于 Javascript

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

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

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

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

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

主要代码实现如下

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

如果觉得我的文章对您有用,请您随意打赏。您的支持将鼓励我更加努力创作!

相关文章:

说点什么

avatar
300
  订阅  
提醒