前额叶是大脑控制中枢。> 人类是所有动物中，唯一能够自主控制自己的欲望、情绪和冲动的动物，能够为了将来更大的利益而延迟满足当下的需求。

今天，我们继续探索JS算法相关的知识点。我们来谈谈关于{栈| Stack}的相关知识点和具体的算法。

如果，想了解其他数据结构的算法介绍，可以参考我们已经发布的文章。如下是算法系列的往期文章。

文章list

• 整数
• 常规排序算法
• 数组
• 字符串
• 链表

好了，天不早了，干点正事哇。

---

文章概要

0.知识点简讲
1.后缀表达式
2.小行星碰撞
3.判断括号的正确性
4.每日温度
5.直方图最大面积

知识点简讲

栈是个啥

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

栈也被用在编程语言的_编译器_和内存中保存变量、方法调用等，也被用于_浏览器历史记录_（浏览器的返回按钮）。

而在前端，Stack耳熟能详的功能就是调用栈，调用栈就是用来管理函数调用关系的一种数据结构，是 JavaScript 引擎追踪函数执行的一个机制。

还有一个比较重要的用处就是在解析器中，无论是HTML/Vue/JavaScript，在生成对应的AST的时候，针对Token进行匹配处理。此时，就可以利用Stack后进先出的特性，进行匹配处理。

解析HTML生成的AST

解析Vue模板生成的AST

关于调用栈的详细介绍，可以翻阅我们之前文章。这里就不在赘述。

栈的应用(算法方向)

在一些题目中，数据保存的顺序和使用顺序相反，即最后保存的数据最先使用，这与栈的_后进先出_特性契合，可以将数据保存到栈中。

JS版本的Stack

由于JS语言的特殊性，不存在真正意义上的Stack结构，一般使用数组特定的Api（push/pop）模拟最简单的stack使得能够满足后进先出的特性。

let stack = [];
stack.push(1);
stack.push(2);
==== 入栈 1、2====

stack.pop() // 2出栈
stack.pop() // 1出栈 
1
2
3
4
5
6
7

在一些简单的场景下，利用数组来模拟栈是可以满足条件的。但是作为一个功能完备的数据结构，还有一些其他的功能，使用上述的实现方式显的有点捉襟见肘。

那么，我们就自己实现一个比较功能完备的stack。它有如下的功能点

• push(element(s)):添加一个（或几个）新元素到栈顶
• pop():移除栈顶的元素，同时返回被移除的元素
• peek(): 返回栈顶的元素，不对栈做任何修改
• isEmpty():如果栈里没有任何元素就返回true,否则返回false
• size(): 返回栈里的元素个数
• clear(): 移除栈里所有的元素

class Stack {
 constructor() { this.items = []; 
 }
 // 添加element到栈顶
 push(element) { this.items.push(element);
 }
 // 移除栈顶的元素,同时返回被移除的元素
 pop() { return this.items.pop();
 }
 // 返回栈顶的元素，不对栈做任何修改
 peek() { return this.items[this.items.length - 1];
 }
 // 如果栈里没有任何元素就返回`true`,否则返回`false`
 isEmpty() { return this.items.length === 0;
 }
 // 返回栈里的元素个数
 size() { return this.items.length;
 } 
 // 移除栈里所有的元素
 clear() { this.items = [];
 } 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

虽然，我们实现了一个功能完备的stack结构，但是仔细一看，其实就是对array中push/pop等api进行了一次包装。但是，经过包装后，使得针对stack结构的各种操作，变得更具有封装性，而不会产生很多样板代码。

---

1. 后缀表达式

题目描述：

后缀表达式是一种算术表达式，也叫逆波兰式（RPN）,它的操作符在操作数的后面。> 要求输入一个用字符串数组表示的后缀表达式，请输出该后缀表达式的计算结果。>
示例：后缀表达式["2","1","3","*","+"]对应的表达式是2 + 1 * 3,因此输出的计算结果为5

分析

1.以["2","1","3","*","+"]为例子分析。

• 从左往右扫描数组，首先遇到的操作数2,由于后缀表达式的特点，操作符还在后面，在操作符未知的情况下，是无法进行计算处理。所以，需要将当前的操作数进行暂存处理。
• 继续扫描数组，接下来的两个数据都是操作数，（1/3）还是没有操作符的出现，继续将对应的操作数进行暂存处理
• 继续扫描，直到遇到操作符（*）。按照后缀表达式的规则，此操作符对应的操作数是刚刚被暂存的一对操作数1/3
• 存储操作数的容器，是根据数据存入的时间顺序而排序。1/3明显位于容器的尾部。也就是说，需要从容器的尾部将一对数据取出，并做运算处理。
• 根据数据存入和取出的特点，我们可以利用stack来作为存储操作数的容器

2.一对操作数在操作符的作用下，合并成一个值，而这个值可能还会和未被处理的操作数进行计算，所以需要将其存入容器中
3.在容器中仅存唯一的数值，并且操作符也全部被消费了，此时容器中的数据就是后缀表达式最终的结果

代码实现

function evalRPN(tokens){let stack = new Stack();for(let token of tokens){switch(token){// 处理操作符case "+":case "-":case "*":case "/": // 在源数据中，靠后的操作数let back = stack.pop(); // 在源数据中，靠前的操作数let prev = stack.pop();// 计算操作数，并将其入栈处理stack.push(calculate(prev,back,token));break;default:// 处理操作数，直接入栈stack.push(parseInt(token));}}// 操作符都处理完，且栈中只有一个数据return stack.pop();
} 
1
2

辅助函数，用于处理两个操作数之间的算术问题。(有一点需要注意，就是操作数之间的顺序问题)

fucntion calculate(prev,back,operator){switch(operator){case "+":return prev + back;case "-":return prev - back;case "*":return prev * back;case "/":return (prev/back)>>0; // 数据取整default:return 0;}
} 
1
2

---

2. 小行星碰撞

输入一个表示小行星的数组

• 数组中每个数字的绝对值表示小行星的大小
• 数字的正负表示小行星运动的方向，正号表示向右飞行，负号表现向左飞行。
• 如果两个小行星相撞，体积小的小行星会消失，体积大的不受影响
• 如果相撞的小行星大小相等，两个都会消失
• 飞行方向相同的小行星永远不会相撞

示例：有6颗小行星[4,5,-6,4,8,-5],它们相撞之后最终剩下3颗小行星[-6,4,8]

分析

1.拿例子中的数据来分析，存在6颗小行星[4,5,-6,4,8,-5]

• 第一颗是_向右飞行_大小为4的行星，此时不知道是否会和后面行星碰撞，先将其保存到某个_数据容器_中。(因为它位于第一位置，所以不需要考虑前面)
• 第二颗还是_向右飞行_大小为5的行星，它与现存且已知的行星方向相同，所以与其不会碰撞。但是，不知道是否与后面的行星是否发生碰撞，所以也是先将其存入到_数据容器_中。
• 第三颗是_向左飞行_大小为6的行星。由于它与现存且已知的行星方向相反，一定会相撞，大小为5的行星离它近，因此两个行星率先相遇。
• 由前面分析我们得知，我们先后往数据容器中依次存入了4/5，而在遇到方向不同的行星时，是率先取最近一次加入到数据容器的数据。也就是说，针对数据容器中的数据的存取，满足后进先出的规则。我们可以考虑用栈来具象化该数据结构。

2.在①中我们规定，针对向右飞行的行星，是采取了直接存入到数据容器中(stack)

• 如果当前元素是向左飞行时，此时就会发生碰撞，且他们直接遵循大值原则即谁大谁能存活。
• 并且向左飞行的元素秉持着，不撞南墙不回头的态度，只要栈里面还有额外的数据，它就要和stack中的数据battle一下，哪怕_身败名裂_
• 只有存活下来的元素，才配进入栈中

代码实现

function asteroidCollision(asteroids){let stack = new Stack();for(let as of asteroids){// 当前元素向左飞行，并且该元素的绝对值比栈顶元素大while(!stack.empty() && stack.peek()>0&& stack.peek()<-as){stack.pop();}// 当前元素向左飞行,当前元素和栈顶元素体积一样 (需要互相抵消) if(stack.length  && as<0 && stack.peek()==-as ){stack.pop();}else if(as >0//当前元素向右飞行|| stack.empty() // 栈为空 （初始化）// 当前元素向左飞行(在经过对比后，还是无法消除) || stack.peek()<0){stack.push(as)}}return stack;
} 
1
2

上述的代码中，我们使用了Stack中的一些方法。

---

3. 判断括号的正确性

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。

示例：> 输入：s = “()[]{}” 输出：true> 输入：s = “(]” 输出：false

分析

1.当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合，但是，我们此时还用不到该左括号，所以，将其存入数据容器中
2.由于，题目中还需指定，必须以指定的顺序，此时，就需要考虑左括号的存入顺序了，后存入的先处理。即：后进先出的规则 ==> 那数据容器可以选为栈

代码实现

function isValid (s) {let stack = new Stack();// 遍历 字符串for(let c of s){// 遇到左括号，将与其匹配的右括号入栈处理if(c==='('){stack.push(')')}else if(c==='['){stack.push(']')}else if(c==='{'){stack.push('}')// 遇到右括号// 1. 判断栈内是否有括号，如果没有，那说明此时匹配不了// 2. 满足①的情况下，判断此时字符是否和栈顶元素匹配}else if(stack.length ===0 || stack.pop()!==c){return false;}}// 最后再验证一下，栈是否为空，如果不为空，说明还有未匹配的括号return !stack.length;
}; 
1
2

---

3. 每日温度

输入一个数组，每个数字都是某天的温度。> 计算每天需要等几天才会出现更高的温度>
示例：输入数组[35,31,33,36,34],输出结果为[3,1,1,0,0]>

• 第一天温度为35°，要等3天才会出现更高的温度36°
• 第四天的文档是36°，后面没有更高的温度，与其对应的输出是0

分析

1.每次从数组中读出某一天的温度，并且都将其与之前的温度（保存在数据容器中的温度）相比较。
2.从离它较近的温度开始比较，也就是后存入数据容器中的温度先拿出来比较，满足后进先出的原则 —> 我们选Stack作为数据容器
3.题目中，需要计算出现更高温度的等待天数，存入栈中的数据应该是温度在数组中的下标。* 等待的天数就是两个温度在数组中的下标之差。

代码实现

function dailyTemperatures(temperatures){ // 定义一个与源数组相同的数组，用于存储最后结果let result = new Array(temperatures.length);let stack = new Stack();for(let i = 0;itemperatures[stack.peek()]){// 取出，存于stack中的满足条件的温度的下标let prev = stack.pop();// 计算等待天数 并将其存入result[prev]中result[prev] = i - prev;}// 将当前下标存入stack中stack.push(i)}return result;
} 
1
2

额外提醒

• 只有在 stack 非空，且当前的温度大于栈顶温度，才会从stack中取出栈顶元素
• 在满足条件的时候，是已经存入到stack中的数据，找到了它对应的需要等待的天数i - prev

---

直方图最大面积

输入一个由非负数组成的数组，数组中的数字是直方图中柱子的高，求直方图中最大矩形的面积> 假设直方图中柱子的宽度为1>
示例：输入数组[2,1,5,6,2,3],直方图中最大矩形的面积为10（2*5）

分析 - 双指针法

1.如果直方图中一个矩形从下标为i的柱子开始，到下标为j的柱子结束，那么两根柱子之间的矩形（含两端的柱子）的宽度是j-i+1，矩形的高度就是两根柱子之间的所有柱子最矮的高度
2.如果能逐一找出直方图中所有矩形并比较它们的面积，就能得到最大的矩形面积
3.定义两个指针i/j :i表示靠前的柱子下标，j表示靠后的柱子下标

代码实现 - 双指针法

function largestRectangleArea(heights){let maxArae = 0;for(let i=0;i

function selectionSort(arr){let len = arr.length;if(len<2) return arr; // 处理边界值let i,j,minIndex;// 外层循环: 控制迭代轮次for(i=0;i