数据结构（七）栈&中、后、前缀表达式

栈的定义

栈是限制在表尾插入和删除操作的线性表。
允许插入和删除的一端叫做栈顶，另一端为栈底。
不含任何元素的栈称为空栈。

栈的特点

后进先出

链栈的定义

链栈的结构与链表相似，插入与删除都在链表的头部。即链栈是一个以 top 为头结点、从栈顶指向栈底的单链表。

创建链栈

出栈

出战的可能组合：

实现

JavaScript

let Stack = (() => {
  let items = new WeakMap();
  class Stack {
    constructor() {
      items.set(this, []);
    }
    // 添加一个（或几个）新元素到栈顶
    push(element) {
      let s = items.get(this);
      s.push(element);
    }
    // 移除栈顶元素并返回被移除的元素
    pop() {
      let s = items.get(this);
      let r = s.pop();
      return r;
    }
    // 查看栈顶元素
    peek() {
      let s = items.get(this);
      return s[s.length - 1];
    }
    // 检查栈是否为空
    isEmpty() {
      let s = items.get(this);
      return s.length == 0;
    }
    // 栈的元素个数
    size() {
      let s = items.get(this);
      return s.length;
    }
    // 清空栈
    clear() {
      items.set(this, []);
    }
    // 打印栈
    print() {
      let s = items.get(this);
      console.log(s.toString());
    }
  }
  return Stack;
})();

应用

• 递归
• 进制转换
• 迷宫求解
• 括号匹配

  表达式（难点）

  中缀表达式

  转后缀表达式

1. 若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈。
2. 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。
3. 若取出的字符是“（”，则直接送入S1栈顶。
4. 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
5. 重复上面的1~4步，直至处理完所有的输入字符。
6. 若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。

完成以上步骤，S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！

后缀表达式

后缀表达式：9 3 1-3+ 10 2/+
表达式：(9+(3-1)3)+(10/2)
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

前缀表达式

倒过来转为后缀表达式再计算