栈的一些常用场景总结

• 括号匹配
• 表达式中求值
• 下一个更大元素
• 浏览器前进后退
• 执行上下文栈

括号匹配

function validString(string) {
  const resultStack = [];
  const markMap = new Map([
    ["(", ")"],
    ["[", "]"],
    ["{", "}"]
  ]);
  const top = arr => arr[arr.length - 1];

  for (let i = 0; i < string.split("").length; i++) {
    const str = string[i];
    const isLeft = markMap.get(str);
    // 遇到左边的括号，进栈
    if (isLeft) {
      resultStack.push(str);
      continue;
    }
    // 遇到右边的括号，看看和栈顶的括号是不是配对的，是则出栈，不是则肯定非法字符串
    const isRelative = str === markMap.get(top(resultStack));
    if (!isRelative) {
      return false;
    }
    resultStack.pop();
  }
  // 最后，栈空表示合法字符串，否则非法字符串
  return !resultStack.length;
}
// true
console.log(validString("[[({}{})]]({})"));

表达式中求值

/** -- 准备工作开始 - **/
// 符号的优先级
const priorityMap = { "+": 0, "-": 0, "*": 1, "/": 1 };
// 符号的运算公式
const computeMap = {
  "+": (a, b) => a + b,
  "-": (a, b) => a - b,
  "*": (a, b) => a * b,
  "/": (a, b) => a / b,
};
// 栈顶元素
const top = (arr) => arr[arr.length - 1];
// 次栈顶元素
const top2 = (arr) => arr[arr.length - 2];
// 栈是不是空的
const isEmpty = (arr) => !arr.length;

// 每次计算的时候，根据符号栈的栈顶符号，计算数字栈前两个，然后符号栈执行出栈，将计算结果推到数字栈
const compute = (numberStack, markStack) => {
  const computeFn = computeMap[markStack[markStack.length - 1]];
  const result = computeFn(top2(numberStack), top(numberStack));
  markStack.pop();
  numberStack.pop();
  numberStack.pop();
  numberStack.push(result - 0);
};
/** -- 准备工作结束 -- **/

// 正餐：
function computeExpression(expressionString) {
  const markStack = [];
  const numberStack = [];
  expressionString.split("").forEach((str) => {
    const isMark = priorityMap.hasOwnProperty(str);
    // 是数字的话，直接推进数字栈
    if (!isMark) {
      numberStack.push(str - 0);
      return;
    }
    // 是符号的话，如果符号栈不为空且当前优先级不大于栈顶符号的优先级，则计算
    // 直到符号栈为空或者当前优先级大于栈顶符号的优先级，符号栈才执行进栈
    while (
      !isEmpty(markStack) &&
      priorityMap[str] <= priorityMap[top(markStack)]
    ) {
      compute(numberStack, markStack);
    }
    markStack.push(str);
  });
  // 遍历完之后，挨个计算，直到符号栈为空
  while (markStack.length) {
    compute(numberStack, markStack);
  }
  // 数字栈只剩下一个
  const result = top(numberStack);
  numberStack.pop();
  return result;
}
// 18
console.log(computeExpression("1+2*5*1+4/2+5"));

下一个更大元素

const top = arr => arr[arr.length - 1]
const isEmpty = arr => !arr.length
var nextGreaterElement = function(numbers) {
  const stack = [];
  let ans = [];
  for (let i = numbers.length - 1; i >= 0; i--) {
    const cur = numbers[i];
    while (!isEmpty(stack) && cur >= top(stack) ) {
      stack.pop();
    }
    ans[i] = isEmpty(stack) ? -1 : top(stack);
    stack.push(cur);
  }
  return ans;
};

var dailyTemperatures = function(numbers) {
  const stack = [];
  // 存放的是索引，这样方便计算天数
  let ans = [];
  for (let i = numbers.length - 1; i >= 0; i--) {
    const cur = numbers[i];
    // 注意比较的时候，根据栈顶的索引拿到相应的温度进行比较
    while (!isEmpty(stack) && cur >= numbers[top(stack)]) {
      stack.pop();
    }
    // 存答案的时候，是计算差值
    ans[i] = isEmpty(stack) ? 0 : top(stack) - i;
    stack.push(i);
  }
  return ans;
};

var nextGreaterElement = function(numbers) {
  const stack = [];
  let ans = [];
  // 假装数组长度翻倍了
  for (let i = numbers.length * 2 - 1; i >= 0; i--) {
    // 这里要用实际索引
    const cur = numbers[i % numbers.length];
    while (!isEmpty(stack) && cur >= top(stack)) {
      stack.pop();
    }
    // 只需要真实数组长度这里存答案即可
    if (i < numbers.length) {
      ans[i] = isEmpty(stack) ? -1 : top(stack);
    }
    stack.push(cur);
  }
  return ans;
};

浏览器的前进后退

• 依次访问a、b、c三个页面，则依次进入x栈
• 点击后退，c出x栈，进y栈，此时x栈栈顶是b，所以看到b页面
• 再点击后退，b出x栈，进y栈，此时x栈栈顶是a，所以看到a页面
• 点击前进，b出y栈，进x栈，此时x栈栈顶是b，所以看到b页面
• 跳转到新页面d，清空y栈，d进x栈，此时x栈栈顶是d，所以看到b页面，y栈被清空了所以不论前进或后退都访问不到

执行上下文栈

• 浏览器执行JS代码的时候，首先创建全局的执行上下文，压入执行栈的顶部
• 执行函数的时候，创建函数的执行上下文，压入执行栈的顶部
• 函数执行完毕的时候，当前的函数执行上下文出栈
• 浏览器的JS引擎总是访问，位于执行栈的顶部的执行上下文
• 当前页面关闭的时候，全局的执行上下文出栈

var color = 'blue';
function changeColor() {
    var anotherColor = 'red';
    function swapColors() {
        var tempColor = anotherColor;
        anotherColor = color;
        color = tempColor;
    }
    swapColors();
}
changeColor();

• 当上述代码在浏览器中加载时，JavaScript 引擎会创建一个全局执行上下文并且将它推入当前的执行栈
• 调用 changeColor函数时，此时changeColor函数内部代码还未执行，js执行引擎立即创建一个changeColor的执行上下文（简称EC），然后把这执行上下文压入到执行栈（简称ECStack）中。
• 执行changeColor函数过程中，调用swapColors函数，同样地，swapColors函数执行之前也创建了一个swapColors的执行上下文，并压入到执行栈中。
• swapColors函数执行完成，swapColors函数的执行上下文出栈，并且被销毁。
• changeColor函数执行完成，changeColor函数的执行上下文出栈，并且被销毁。

引用

• 深入理解JavaScript执行上下文和执行栈 
  https://segmentfault.com/a/1190000018550118
• 数据结构与算法之美
  https://time.geekbang.org/column/intro/126
  
• 单调栈解决 Next Greater Number 一类问题
  https://leetcode-cn.com/problems/next-greater-element-i/solution/dan-diao-zhan-jie-jue-next-greater-number-yi-lei-w/