栈和队列

栈和队列值允许在线性集合的一端进行操作，推入和弹出操作。栈先进后出，队列先进先出，这就是他们最大的不同点。

栈Stack

栈Stack是一种先进后出的数据结构， 在js中，我们可以使用Array或者链表来简单的模拟一个栈， 或者也可以像下面这样子简单编写一个栈的构造函数

class Stack {
  constructor() {
    this.stack = [];
  }
  push(item) {
    this.stack.push(item);
  }
  pop() {
    return this.stack.pop();
  }
  peek() {
    if (this.stack && this.stack.length > 0) {
      return this.stack[this.stack.length - 1];
    }
    return undefined;
  }
  length() {
    return this.stack.length;
  }
  isEmpty() {
    return this.stack.length === 0;
  }
  clear() {
    this.stack.length = 0;
  }
}

栈的典型基础案例

1.进制转换

比如十进制转八进制

// 十进制转换为八进制
function decimal2octal(num) {
  if (typeof num !== 'number') {
    throw new TypeError('Expect a number input');
  }
  if (num === 0) return 0;
  let quotient = num;
  let remainder;
  const stack = [];
  // 只要商大于0 就把余数推到队列
  while (quotient > 0) {
    remainder = quotient % 8;
    stack.push(remainder);
    quotient = Math.floor(quotient / 8);
  }
  // 最后反转即可
  return stack.reverse().join('') - 0;
}

2.括号匹配检验

遇到左括号就进栈，遇到右括号就跟当前栈顶匹配，能匹配就将其出栈，否则不匹配.

比如 (()), ()()()等就是合法闭合的， 如果是多种括号，比如([{}])() 思路也是一样的

function isClosure2(str) {
  if (!str) return false;
  const stack = [];
  if (str[0] === '(') {
    stack.push(str[0]);
  } else {
    return false;
  }
  for (let i = 1, len = str.length; i < len; i++) {
    const char = str[i];
    if (char === '(') {
      stack.push(char);
    }
    if (char === ')') {
      stack.pop();
    }
  }
  return stack.length === 0;
}

3.中缀表达式的计算机求值

比如求算 ”1 + 3 * 4 / 2“要求算出7

1、设置两个栈，一个数字栈numStack，用于存储表达式中涉及到的数字，operatorStack用于存储表达式中涉及到的运算符 逐个字符分析表达式，直到全部字符都已分析完 2、若当前字符为数字，则判断是否后续字符也为数字，若为数字则进行拼接，直到下一个数字为运算符为止，此时将拼接好的多位数字压入数字栈中。（如果已经是最后一个字符则直接压入栈） 3、若当前字符为算数运算符 如果运算符栈为空则直接压入栈中 运算符不为空，则对运算符优先级进行判断 如果当前运算符优先级大于等于栈顶运算符则直接压入栈中 如果优先级低于栈顶运算符，则，从数字栈中取出两个数据，将当前栈顶运算符弹出进行运算，将结果压入数字栈中，将当前运算符压入运算符栈中。 4、此时数字与运算符都已经压入栈中，此时运算符栈中均为优先级相同的运算符，需要进行收尾操作，如果运算符栈不为空，则依次从数字栈中弹出两个数据，与当前栈顶的运算符进行运算。将结果压入数字栈中。最后数字栈中的数字就是所要求解的结果

下面的代码可能不是很正确， 但是可以通过大部分的表达式， 暂时没有考虑括号的情况

class Stack {
  constructor() {
    this.stack = [];
  }
  push(item) {
    this.stack.push(item);
  }
  pop() {
    return this.stack.pop();
  }
  peek() {
    if (this.stack && this.stack.length > 0) {
      return this.stack[this.stack.length - 1];
    }
    return undefined;
  }
  length() {
    return this.stack.length;
  }
  isEmpty() {
    return this.stack.length === 0;
  }
  clear() {
    this.stack.length = 0;
  }
}
/* 113 + 20 * 6 / 3 */

// 判断是否是一个数字
function isNumChar(char) {
  const numReg = /^\d{1}$/;
  return numReg.test(char);
}

// 判断是否是操作符
function isOperatorChar(char) {
  const operatorReg = /^\+|\-|\*|\/|\(|\)$/;
  return operatorReg.test(char);
}

function calculate(num1, num2, operator) {
  switch (operator) {
    case '+':
      return num1 + num2;
    case '-':
      return num1 - num2;
    case '*':
      return num1 * num2;
    case '/':
      return num1 / num2;

    default:
      break;
  }
}

function calExpression(expression) {
  const numStack = new Stack();
  const operatorStack = new Stack();
  let n = 0,
    i = 0,
    len = expression.length;
  for (; i < len; i++) {
    const char = expression[i];
    if (char === ' ') {
      // 过滤一下空格
      continue;
    }
    if (isNumChar(char)) {
      n = parseInt(char);
      while (expression[i + 1] && expression[i + 1] !== ' ') {
        if (isNumChar(expression[i + 1])) {
          n = n * 10 + (expression[i + 1] - 0);
          i++;
        } else {
          break;
        }
      }
      numStack.push(n);
    } else if (isOperatorChar(char)) {
      //   operatorStack.push(char);
      switch (char) {
        case '+':
          if (operatorStack.length() === 0) {
            operatorStack.push(char);
          } else {
            const peek = operatorStack.peek();
            if (peek === '+' || peek === '-' || peek === '(') {
              operatorStack.push(char);
            } else {
              // 需要计算
              const num2 = numStack.pop();
              const num1 = numStack.pop();
              const operator = operatorStack.pop();
              const result = calculate(num1, num2, operator);
              numStack.push(result);
              operatorStack.push(char);
            }
          }
          break;
        case '-':
          if (operatorStack.length() === 0) {
            operatorStack.push(char);
          } else {
            const peek = operatorStack.peek();
            if (peek === '+' || peek === '-' || peek === '(') {
              operatorStack.push(char);
            } else {
              // 需要计算
              const num2 = numStack.pop();
              const num1 = numStack.pop();
              const operator = operatorStack.pop();
              const result = calculate(num1, num2, operator);
              numStack.push(result);
              operatorStack.push(char);
            }
          }
          break;
        case '*':
        case '/':
          if (operatorStack.length() > 0) {
            const peek = operatorStack.peek();
            if (peek === '*' || peek === '/') {
              const num2 = numStack.pop();
              const num1 = numStack.pop();
              const operator = operatorStack.pop();
              const result = calculate(num1, num2, operator);
              numStack.push(result);
              //   operatorStack.push(char);
            }
          }
          operatorStack.push(char);
          break;
        case '(':
          operatorStack.push(char);
          break;
        case ')':
          while (operatorStack.peek() !== '(') {
            const num2 = numStack.pop();
            const num1 = numStack.pop();
            const operator = operatorStack.pop();
            const result = calculate(num1, num2, operator);
            numStack.push(result);
          }
          // 弹出（
          operatorStack.pop();
          break;

        default:
          break;
      }
    }
  }
  while (operatorStack.length() > 0) {
    const num2 = numStack.pop();
    const num1 = numStack.pop();
    const operator = operatorStack.pop();
    const result = calculate(num1, num2, operator);
    numStack.push(result);
  }
  // console.log(numStack, operatorStack);
  return numStack.pop();
}

// 下面的测试用例一般都可以通过
console.log(calExpression('113 + 20 * 6 / 3 - 0'));
console.log(calExpression('1 + 2'));
console.log(calExpression('1 * 2 + 3'));
console.log(calExpression('1 + 2 * 3'));
console.log(calExpression('1 + 2 * 3 / 6'));
console.log(calExpression('1 + 2 * 3 / 4'));
console.log(calExpression('(1 + 2 + 3) * 5'));
console.log(calExpression('(1 + 2 - 1) * 5 * 6'));

还有一些变种题目， 比如波兰表达式求值， 逆波兰表达式求值，给优先级高的加上括号等题目，都可以采用栈来解决

队列 Queue

队列是尾部插入，头部弹出的先进先出的数据结构

队列案例

1.循环队列

6个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时1秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。

function getWinner(nameList, num) {
  const queue = [...nameList];
  while (queue.length > 1) {
    for (let i = 0; i < num; i++) {
      queue.push(queue.shift());
    }
    queue.shift();
  }
  return queue.shift();
}

其他按理后续补吧