栈结构+一道算法

ZiHao...大约 2 分钟

1.栈（stack）

它是一种受限制的线性表，后见先出

其限制是仅允许在表的一端进行插入和删除操作，这一段被称为栈顶相对地把另一端称为栈底
LIFO 表示就是后进入的元素，带一个弹出栈空间，类似于自动餐托盘最后放上托盘，往往先拿出去使用
向一个栈插入新元素又称作进栈，入栈，或者压栈，他是把新元素放到栈顶元素的上面，使之成为新的栈顶元素
从一个栈删除元素又称作出栈，或者退栈，他是把栈顶元素删掉，使其相邻的元素成为新的栈顶元素。

2.栈结构的实现例一

var longestValidParentheses = function (s) {
  let maxLen = 0;
  let stack = [];
  stack.push(-1); // 初始化一个参照物
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      // ( 入栈   )出栈
      stack.push(i);
    } else {
      // )的情况 出栈
      stack.pop();
      if (stack.length) {
        // 每次出栈 计算下当前有效连续长度
        // 如何计算连续长度 当前位置 - 栈顶下标  并取值最大的有效长度
        maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
      } else {
        stack.push(i); //栈为空时 放入右括号参照物 表示从这个下标开始 需要重新计算长度
      }
    }
  }
  return maxLen;
};

利用栈结构解题

例二

code

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  if (s.length % 2 === 1) {
    return false; //如果为奇数  不可能匹配
  }
  const stack = []; //创建一个空栈
  for (let i = 0; i < s.length; i++) {
    //遍历
    const c = s[i]; //取得字符
    if (c === "[" || c === "{" || c === "(") {
      //将右括号入栈，碰到对应的左括号出战
      stack.push(c);
    } else {
      const top = stack[stack.length - 1]; //取出栈顶元素
      if (
        (top === "{" && c == "}") ||
        (top === "(" && c == ")") ||
        (top === "[" && c === "]")
      ) {
        //如果栈顶元素与之匹配，则出栈
        stack.pop();
      } else {
        //不匹配直接退出
        return false;
      }
    }
  }
  //最后判断以下栈中是否有匹配剩下的  有则匹配失败   无则匹配成功
  return stack.length === 0;
};