栈

栈只是一种特殊的线性表，它是线性表的一种具体形式，也就是必须通过顺序表或链表来实现它，但是它在操作上有一些特殊的要求和限制，只能在一端进行操作。对于栈来说，表尾称之为栈顶，而表头称之为栈底。新的元素总是靠近栈顶，旧的元素总是靠近栈底，栈就像弹夹一样，最先压进去的子弹一定是最后出来的，所以它遵循先进后出或后进先出的原则，即 LIFO（Last In First Out）。往栈中添加元素的操作，叫做入栈，从栈中移除元素的操作，叫做出栈

栈应用很广，在回溯问题中，可以存储访问过的任务和路径、撤销的操作，可以用来处理计算机科学问题

优先处理最新的邮件
函数调用栈
浏览器历史记录
编译器

栈和内存栈

数据结构中的栈和内存中的栈空间是有区别的，虽然它们有点联系

function decimalToBinary(decNumber) {
  const remStack = new Stack();
  let number = decNumber;
  let rem;
  let binaryString = '';
  while (number > 0) { 
    rem = Math.floor(number % 2);    // 求余
    remStack.push(rem);              // 放入栈中
    number = Math.floor(number / 2); // 获得下一次被除数
  }
  while (!remStack.isEmpty()) {
    binaryString += remStack.pop().toString(); // 从栈中取出
  }
  return binaryString;
}

这是改进后的算法，十进制可以转换为 2~16 之间的任意进制

function baseConverter(decNumber, base) {
  const remStack = new Stack();
  const digits = '0123456789ABCDEF';
  let number = decNumber;
  let rem;
  let baseString = '';
  if (!(base >= 2 && base <= 16)) { // 判断是否能够在基数内进行转换
    return ''
  }
  while (number > 0) {
    rem = Math.floor(number % base); // 求余
    remStack.push(rem); // 放入栈中
    number = Math.floor(number / base); // 获得下一次被除数
  }
  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()]; // 从栈中取出并转换
  }
  return baseString;
}

检查括号的匹配性

对于一个表达式，每一个左括号都有一个唯一对应的右括号，并且是正确的嵌套位置，那么这个表达式就是平衡的，否则这个表达式是不平衡的，比如：

() - 平衡
)( - 不平衡
[()] - 平衡
[()()] - 平衡

对于一个表达式的括号匹配算法，就是扫描表达式将遇到的左括号压入栈，遇到匹配到的右括号就弹栈，最后看栈是否为空，如果为空则代表表达式是平衡的

function checkExpression(str) {
  const leftBrackets = ['(', '[', '{'];
  const rightBrackets = [')', ']', '}'];
  const stack = new Stack();
  // 只有一个符号的情况
  if (str.length == 1) return false;
  for (let i = 0; i < str.length; i++) {
    // 如果遇到左括号就入栈
    if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
      stack.push(str[i]);
    } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
      // 如果栈为空或者与栈顶括号不匹配就返回 false，否则就是匹配成功并出栈
      if (stack.isEmpty() || leftBrackets.indexOf(stack.peek()) != rightBrackets.indexOf(str[i])) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.isEmpty();
}

中缀、后缀、前缀

前缀、中缀、后缀表达式是对表达式的不同记法，其区别在于运算符相对于操作数的位置不同，前缀表达式的运算符位于操作数之前，中缀和后缀同理

中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间，对于人来说很容易理解，但对于计算机来说理解非常困难

前缀表达式是由一个波兰数学家提出的，又称为波兰表达式，如果一个中缀表达式1+2使用前缀表达式，它将是+12

后缀表达式又称为逆波兰表达式，如果一个中缀表达式1+2使用前缀表达式，它将是12+

前缀、后缀表达式进行解析和求值时，不需要考虑优先级、结合性

对于中缀表达式A + B * C，用人脑算的时候，眼睛会自动移到后面两个数上，最后再计算加法。实际上是没意识到自己的大脑已经添加了括号并划分好了计算顺序：(A + ( B * C))

栈

数组实现

链式实现

反转

十进制转二进制

检查括号的匹配性

中缀、后缀、前缀