栈

栈是一种数据的存储方式，特点是后进先出(Last In First Out), 就是只能在栈顶进行操作。

stack.png

想一下我们往箱子里放书，只能一本一本的从最上面累加，拿的时候也是从最上面往外拿，只能一头操作不能两头操作。

接下来，我们用数组来实现栈的功能，主要的方法有：

• push: 添加元素到栈顶
• pop: 弹出栈顶元素
• top: 返回栈顶元素
• isEmpty: 判断栈是否为空
• size：返回栈里的元素个数
• clear：清空栈

function Stack () {
    let items = []; // 存储数据
    
    // 从栈顶添加元素，也叫压栈
    this.push = function (item) {
        items.push(item);
    }
    
    // 弹出栈顶元素
    this.pop = function () {
        return items.pop();
    }
    
    // 返回栈顶元素
    this.top = function () {
        return items[items.length - 1];
    }
    
    // 判断栈是否为空
    this.isEmpty = function () {
        return items.length === 0;
    }
    
    // 返回栈的大小
    this.size = function () {
        return items.length;
    }
    
    // 清空栈
    this.clear = function () {
        items = [];
    }
}

为啥items数组没有挂在this上呢？

items是作为私有变量存在的，如果挂在this上面，实例就可以访问到，就能根据下标去操作数组，就不符合先进后出了。所以只能调用方法去操作。

下面通过几个例子，来感受一下通过栈的方式来思考问题

例一:
判断是否是合法的括号（成对出现）

as()sfrg(dfg)
(sf(dfdg))
()()))

思路分析：for循环遍历字符串

• 遇到左括号入栈
• 遇到右括号，如果栈中有元素，栈顶元素出栈；如果栈为空，说明没有对应的左括号，结束循环，返回false。
• 遍历完之后查看栈是否为空，是的话说明括号都一一抵消掉了，是合法的返回true；否的话说明缺少对应的左括号，是不合法的返回false。

function isLegalBrackets(str) {
    const stack = new Stack();
    for(let i = 0; i < str.length; i++) {
        const item = str[i];
        // 遇到做括号入栈
        if (item === '(') {
            stack.push(item);
        } else if (item === ')') {
           // 遇到右括号，判断栈是否为空
            if (stack.isEmpty()) {
                return false;
            } else { // 弹出左括号
                stack.pop();
            }
        }
    }

    // 如果栈为空，说明字符串括号合法
    return stack.isEmpty();
}

例二：中缀表达式转后缀表达式

中缀表达式：运算符在两个运算对象的中间：

1 + 2、1+2+3

后缀表达式：运算符在两个运算对象的后面：

1 2 +、1 2 3 + +

后缀表达式的优点：计算机运算特别方便，严格从左向右进行，不需要考虑运算符的优先，也没有括号了。

思路分析：
后缀表达式重要的就是运算符的存放位置，运算数的顺序就是从左到右依次存放。我们定义一个数组和栈，数组存放后缀表达式，栈存放运算符和括号，在合适的时候出栈存入数组。

循环中缀表达式数组

• 遇到运算数存入数组
• 遇到左括号入栈
• 遇到运算数，如果栈为空或者当前运算符的优先级大于栈顶元素的优先级，或者栈顶元素是左括号，入栈
• 如果当前运算符的优先级小于等于栈顶元素的优先级，弹出栈顶元素存到数组中，直到没有栈顶元素优先级大于当前运算符的优先级为止。最后把当前运算符入栈
• 如果是右括号，弹出栈顶元素直到遇到左括号为止。并且弹出左括号
• 循环结束后，如果栈中还有元素，依次弹出存到数组中。

这篇文章过程分析描述的挺详细的

const priorityMap = { '+': 1, '-': 1, '*':2, '/': 2 }; // 定义运算符优先级
function infixExpToPostfixExp (exp) {
  const postfixArr = []; // 存储后缀表达式
  const stack = new Stack();

  for(let i = 0; i < exp.length; i++) {
    const item = exp[i];

    if (!isNaN(item)) { // 是数字直接存进数组
      postfixArr.push(item);
    } else if (stack.isEmpty() || priorityMap[item] > priorityMap[stack.top()] || item === '(' || stack.top() === '(') { // 栈为空 || 当前元素优先级大于栈顶元素优先级 || 当前元素是左括号 || 栈顶是左括号，直接入栈
      stack.push(item);
    } else if (item === ')') { // 遇到右括号
      while(stack.top() !== '(') { // 把左括号前的运算符全部出栈存到数组中
        const top = stack.pop();
        postfixArr.push(top);
      }
      stack.pop(); // 左括号出栈
    } else if (priorityMap[item] <= priorityMap[stack.top()]) { // 当前元素优先级小于栈顶元素优先级
      while(priorityMap[item] <= priorityMap[stack.top()]) { // 把比当前元素优先级大的运算符全部出栈存进数组
        const top = stack.pop();
        postfixArr.push(top);
      }
      stack.push(item); // 当前运算符入栈
    }
  }
  while(!stack.isEmpty()) { // 如果最后栈中还有元素，全部出栈存进数组
    postfixArr.push(stack.pop());
  }

  return postfixArr;
}

// var exp = ["(","1","+","(","4","+","5","+","3",")","-","3",")","+","(","9","+","8",")"];
// console.log(infixExpToPostfixExp(exp))

例三. 计算逆波兰表达式

逆波兰表达式也就是后缀表达式，例如：["4", "13", "5", "/", "+"]，它的计算方式就是遇到'/'时，把13和5拿出来进行除法运算，然后把13、5、/三个元素删除，把运算结果放进去，遇到‘+’, 把前两个运算数拿出来进行加法运算，最后的结果也就是后缀表达式的结果。

用栈怎么实现呢？循环遍历数组

• 遇到操作数，入栈
• 遇到运算符，依次从栈顶弹出两个元素，和当前运算符进行运算
• 把运算结果入栈
• 遍历结束后，栈里只有一个元素，这个元素就是最后的计算结果

function calcExp (exp) {
  const stack = new Stack();
  for (let i = 0; i < exp.length; i++) {
    const item = exp[i];
    if (['+', '-', '*', '/'].includes(item)) {
      const value1 = stack.pop();
      const value2 = stack.pop();

      const expStr = value2 + item + value1;
      // 计算并取整
      const res = parseInt(eval(expStr));
      // 计算结果压入栈中（注意转成字符串）
      stack.push(res.toString());
    } else {
      stack.push(item);
    }
  }
  return stack.pop();
}

3. 实现一个有min方法的栈

实现一个栈，除了常见的push，pop方法以外，提供一个min方法，返回栈里最小的元素，且时间复杂度为o(1)

思路分析：

1. 用两个栈来存储数据，一个是常规栈（dataStack），正常存储数据，另一个专门用来存储最小值(minStack)。两个栈的元素个数要一致，如果最小值栈只存储当前的最小值（只有一个元素）， pop()操作之后再求最小值就不行了
2. 编程思想里有一个分而治之的思想，就是分开想，分开处理。考虑dataStack的时候，就别管min方法，它就是一个普通的栈，正常处理就行

考虑minStack的时候，就别管dataStack了，它是专门为min方法而存在的栈。如果minStack为空，push进来的数据一定是最小的，直接入栈；如果不为空，跟栈顶元素比较，比栈顶元素小也入栈。如果比栈顶元素大，为了保证和常规栈的长度一样，把栈顶元素再次入栈

function MinStack () {
  var dataStack = new Stack(); // 普通的栈
  var minStack = new Stack(); // 存储最小值的栈

  this.push = function (item) {
    dataStack.push(item); // 普通栈正常压栈

    if (minStack.isEmpty() || item < minStack.top()) { // 如果最小值栈为空或者将要压入的值比栈顶元素小，入栈
      minStack.push(item);
    } else { // 否则就把栈顶元素再一次入栈（minStack要和dataStack的元素个数保持一致）
      minStack.push(minStack.top())
    }
  };
 
  this.pop = function () { // 两个栈都弹出
    minStack.pop();
    return dataStackk.pop();
  }

  this.min = function () { // 直接取栈顶元素
    return minStack.top();
  }
}

有些问题用数组的方式来实现很难，但是用栈来思考就会发现别有洞天。这也是看了张老师的视频讲解之后做了一下笔记，方便日后查阅。