栈的一些常用场景总结 | 项目复盘
栈，是一种基本的数据结构，就像我们放盘子一样，一个一个往上放，用的时候，从上一个一个往下拿，不能从中间抽。
典型的特点：只允许在一端插入和删除数据，后进者先出，先进者后出。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，优先联想“栈”这种数据结构。
简单总结了栈的一些常用场景：
- 括号匹配
- 表达式中求值
- 下一个更大元素
- 浏览器前进后退
- 执行上下文栈
括号匹配
假设表达式中只包含三种括号，圆括号 ()、方括号 [] 和花括号{}，并且它们可以任意嵌套。
比如，{[{}]}或 [{()}([])] 等都为合法格式，而{[}()] 或 [({)] 为不合法的格式。 现在给一个包含三种括号的表达式字符串，如何检查它是否合法呢？
典型的栈思路！
从左到右扫描字符串，遇到左边的括号，进栈；遇到右边的括号，看看和栈顶的括号是不是配对的，是则出栈，不是则肯定非法字符串。最后，栈空表示合法字符串，否则非法字符串。
这边用js实现代码：
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("[[({}{})]]({})"));
表达式中求值
比如： 3+5*8-6
对于这个四则运算，我们可以很快求解出答案。
但是对于计算机来说，怎么实现这样一个表达式求值的功能呢？
其实，利用两个栈，一个保存数，一个保存符号。从左向右遍历表达式，当遇到数字，直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
栈顶的优先级低，入栈。栈顶的优先级高，则数栈栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
这边用js实现代码：输入单纯考虑10以内的加减乘除的表达式，得到计算结果
/** -- 准备工作开始 - **/ // 符号的优先级 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"));
下一个更大元素
给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。
比如给一个数组 [2,1,2,4,3]，则需要返回数组 [4,2,4,-1,-1]。因为2的下一个更大的元素是4，1的下一个更大的元素是2，以类类推。
当然暴力想法很容易，每次都来个遍历，但时间复杂度会变成o(n^2)。
把数组的元素想象成一个队伍，元素大小想象成人的身高。你现在是长官，面对他们站在前面。
如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。
其实想想，下一个更大的元素，遍历的时候，如果从前往后遍历，是不知道后面的。所以遍历最好从后往前遍历。
就是倒着进栈，用栈存放更小的值
只要栈不为空且当前的值不小于栈顶的值，就将栈顶的值出栈(结合图，矮个子的就起开)
直到栈为空或者当前的值小于栈顶的值
对应的答案就是栈顶的值，栈为空的话就是-1，并且当前值进栈
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; };
这个算法的复杂度只有 O(n)，总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次，没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。
再试试使用这种思路解决类似的问题：
给一个数组，存放近几天的天气气温，需要返回一个数组，计算：对于每一天，还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0
举例：天气数组 T = [23, 24, 25, 21, 19, 22, 26, 23]，返回[1, 1, 4, 2, 1, 1, 0, 0]
细品品，其实思路很接近了，只是这里因为计算天数，所以栈里存放的是索引。
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; };
再拓展下！
如何处理「循环数组」？同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？
给你一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,4]。拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4 。
这里就很有技巧了，通过 % 运算符求模（余数），数组索引%整数倍数的数组长度 === 数组索引，让数组有”环形“的效果，但实际长度没有增加。
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三个页面，此时后退看到b，再后退看到a，前进又看到b，但是从b跳转到d之后，此时不管是前进还是后退都无法看到c页面了。
怎么实现的呢？
新建两个栈：x栈负责存储打开过的网址和后退的网址，y栈负责存储点击前进时浏览的网址。
- 依次访问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栈被清空了所以不论前进或后退都访问不到c
执行上下文栈
执行Javascript代码，更是栈的应用场景之一，JS是单线程，所有代码排队执行。
- 浏览器执行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函数的执行上下文出栈，并且被销毁。
这里注意，执行函数，是先创建函数的执行上下文，然后再是执行函数内部的代码。 换言之，函数内部代码执行前：参数已被初始化、作用域链已被创建、this已被确定。
其他语言的函数调用栈，道理类似。
引用
本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情
