前端数据结构与算法之栈（js 实现）-一一网

栈的概念

根据百科描述：

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

它大概是这个样子的：

图片来源：wikipedia

栈这种数据结构很简单，但是却能实现很多关键的用途，比如浏览器的前进和后退功能，js 中的函数上下文等功能。

接下来看看栈的数据结构要如何实现。

栈的数据结构

定义栈结构我们可以使用构造函数或者 class 来定义：

/**
 * 栈的数据结构，结构中用于保存数据的变量我们用数组来保存，
 * 但是你要明白本质上是为 elements 申请了一块地址连续的内存空间
 * @param {*} maxSize 栈的最大容量
 */
function Stack(maxSize) {
  // 存入栈中的元素
  this.elements = [];
  this.maxSize = maxSize || 0;
  // topIndex 栈顶元素的位置
  this.topIndex = -1;
}

class Stack {
  constructor(maxSize) {
    this.elements = [];
    this.maxSize = maxSize || 0;
    this.topIndex = -1;
  }
}
复制代码

栈的基础算法

栈的基础算法不多，主要有以下四个，要注意 pop 出栈算法可以清除出栈元素也可以不用清除，如果对于存储空间要求比较高，就需要清除掉。

/**
 * 初始化栈
 * @param {*} maxSize 栈的容量
 * @returns Stack
 */
function init(maxSize) {
  return new Stack(maxSize);
}

/**
 * 入栈
 * @param {*} stack 栈
 * @param {*} element 入栈的元素
 * @returns 1-成功；0-失败
 */
function push(stack, element) {
  if (stack.topIndex >= stack.maxSize - 1) {
    return 0;
  }
  stack.topIndex++;
  stack.elements[stack.topIndex] = element;
  return 1;
}

/**
 * 访问栈顶元素
 * @param {*} stack 栈
 * @returns 栈顶元素
 */
function top(stack) {
  return stack.elements[stack.topIndex];
}

/**
 * 出栈，我们可以不必把原来的数据删掉，直接回退栈顶元素的位置就可以了
 * @param {*} stack 栈
 * @returns 1-成功；0-失败
 */
function pop(stack) {
  if (stack.topIndex < 0) {
    return 0;
  }
  stack.topIndex--;
  return 1;
}

// 判断是否是空栈
function empty(stack) {
  if (stack.topIndex < 0) {
    return 1;
  }
  return 0;
}
复制代码

可以看到栈的基础算法还是很简单的，接下来咱们做两个题来巩固一下。

常见算法

使用栈实现简易计算器

来源：力扣（LeetCode）描述

给定一个包含正整数、加(+)、减(-)、乘()、除(/) 的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数 +，-，，/ 四种运算符和空格。整数除法仅保留整数部分。

实现一个简易计算器是对栈结构最好的练习题，这道题使用两个栈来解决，一个保存数字的栈，一个保存运算符的栈。

// 辅助函数：执行两数的计算（最底层）
function operate(theta, a, b) {
  if (theta == "+") {
    return a + b;
  } else if (theta === "*") {
    return a * b;
  } else if (theta === "/") {
    return Math.floor(a / b);
  } else if (theta === '-') {
    return a - b;
  }
  return '';
}

// 执行计算
function calc(numberStack, operatorStack) {
  let a = top(numberStack);
  pop(numberStack);
  let b = top(numberStack);
  pop(numberStack);
  // 进行计算的时候，要注意 a 和 b 两数的顺序，因为从栈顶拿出来的时候顺序是反的
  push(numberStack, operate(top(operatorStack), b, a));
  pop(operatorStack);
}

/**
 * 使用栈实现简易计算器，只包含加减乘除
 * @param {string} s
 * @return {number}
 */
function calculate(s) {
  // 初始化两个栈
  let numberStack = new Stack(100);
  let operatorStack = new Stack(100);
  // 依次从 s 中读取每个字符来处理
  let count = 0;
  while (count < s.length) {
    if (s[count] === ' ') {
      count++;
      continue;
    }
    // 使用 js 中特有的 isNaN 来判断字符是否是一个数字
    if (!isNaN(s[count])) {
      // 转成数字存入数字栈
      push(numberStack, +s[count]);
      count++;
    } else {
      // 如果操作符栈为空或者当前操作符比栈顶操作符优先级高，就入栈
      if (empty(operatorStack) || precede(s[count], top(operatorStack))) {
        push(operatorStack, s[count]);
        count++;
      } else {
        calc(numberStack, operatorStack);
      }
    }
  }
  // 上面的逻辑主要是把表达式处理完（入栈），到这一步时，需要继续处理两个栈中的计算
  while(!empty(operatorStack)) {
    calc(numberStack, operatorStack);
  }
  // 这里可直接返回 top(numberStack)，但是你要记住 js 会自动回收两个栈的内存
  const result = top(numberStack);
  numberStack = null;
  operatorStack = null;
  return result;
}

calculate('2+4*7')
复制代码

检测是否是有效括号

题目描述：给定一个只包含括号的字符串，判断串中的这些括号能否有效配对。比如：”()()”, “{()}”, “{()[()]}” 都可以有效配对，但是：”[{]}” 这种就不能有效配对。

这个问题用栈结构来解决是标准解法，最后看看如果栈是个空栈，就说明是有效括号了。

// 定义右括号的配对项，作用是：比如取到括号 "]"，那么它将会返回 "["，拿它来跟栈顶元素作比较
function pairs(a) {
  if (a == "}") return "{";
  if (a == "]") return "[";
  if (a == ")") return "(";
  return 0;
}

/**
 * 检测是否是有效的括号
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
  // 初始化一个栈空间
  let stack = new Stack(100);
  let count = 0;
  // 依次处理字符串
  while (count < s.length) {
    // 从第二次开始会进入这个逻辑，拿栈顶元素与下一个字符做比对，如果能配上对
    // 就把栈顶元素弹出
    if (top(stack) === pairs(s[count])) {
      pop(stack);
    } else {
      // 否则一直往栈里面添加符号
      push(stack, s[count]);
    }
    count++;
  }
  // 栈为空就说明是有效括号
  if (empty(stack)) return true;
  return false;
}
复制代码