栈
什么是栈
先进后出（后进先出）
常见的办法
- push 增加一个元素到栈顶
- pop 弹出栈顶的元素
- top 返回栈顶的元素
- isEmpty 判断是否为空
- size 返回栈里元素的个数
- clear 清空栈
实现栈的逻辑
function Stack() { const items = [] // 从栈顶增加元素，压栈 this.push = function (item) { items.push(item) } // 弹出 this.pop = function () { return !this.isEmpty() && items.pop() } // 返回栈顶元素 this.top = function () { return !this.isEmpty() && items[items.length - 1] } // 判断是否为空 this.isEmpty = function () { return items.length === 0 } // 返回栈里的大小 this.size = function () { return items.length } // 清空栈 this.clear = function () { items.length = 0 }}简略练习
1、判断括号是否非法
思路
遍历字符串，当遇到 ( 时，增加一个记号到栈中，示意这是第一对括号的结尾。
当遇到 ) 时，咱们从栈中取出一个记号，示意该括号为一组。
中途如果遇到 ） 无奈pop的时候，则示意短少了 (。间接返回 false。
遍历完结后，咱们判断栈的长度。如果栈空，则示意所有括号都对消掉返回 true。如果长度不为 0，则示意其中短少了 )。返回 false。
代码实现
const str1 = '(12)(323)()123(1))'const str2 = '()(123123)'function isLegal(str) { const items = new Stack() for (let i = 0; i < str.length; i++) { if (str[i] === '(') { items.push(1) } else if (str[i] === ')') { if (items.isEmpty()) return false else items.pop() } } return items.isEmpty()}console.log(isLegal(str1), isLegal(str2))2、计算逆波兰表达式（后缀运算）
思路
遍历该数组表达式，将所有数字增加到栈中。
当遇到运算符时，从栈中取出两个数字进行拼接，应用eval进行计算，并将后果从新压栈。持续循环
循环完结后，如果表达式正确会剩下最初一个数值，咱们只须要从栈中取出来返回即可
代码实现
// 4+13/5const exp1 = ['4', '13', '5', '/', '+']const exp2 = ['10', '6', '9', '3', '+', '-11', '*', '/', '*', '17', '+', '5', '+']function calcExp(exp) { const stack = new Stack() for (let i = 0; i < exp.length; i++) { const item = exp[i] if (['+', '-', '*', '/'].indexOf(item) >= 0) { const value1 = stack.pop() const value2 = stack.pop() const expStr = value2 + item + value1 stack.push(parseInt(eval(expStr)).toString()) } else { stack.push(item) } } return stack.pop()}console.log(calcExp(exp1))console.log(calcExp(exp2))3、实现一个有min办法的栈
实现一个栈，除了常见的push，pop办法以外，提供一个min办法，返回栈里最小值。要求工夫复杂度为 O(1)
思路
定义两个栈，一个失常存数据和操作，下文简称栈。另一个存每次的进栈时的最小值，下文简称min栈。
当每次push的时候，将值失常增加到栈中。咱们判断min栈中，如果为空或者min栈顶的数据比增加的值大，那么咱们进行压栈。此时min栈顶就是此次操作中的最小值。
每次pop的时候，栈和min栈失常操作即可。min栈pop一个元素后的栈顶。因为每次push咱们都会往min栈中压入该状态的最小值。此时取栈顶的值，仍旧是该栈中的最小值。
代码实现
function MinStack() { const stack = new Stack() const minStack = new Stack() this.push = function (item) { stack.push(item) if (minStack.isEmpty() || minStack.top() > item) { minStack.push(item) } else { minStack.push(minStack.top()) } } this.pop = function () { if (stack.isEmpty()) return false stack.pop() minStack.pop() } this.min = function () { return minStack.top() }}const minStack = new MinStack()minStack.push(3) // [3]console.log(minStack.min()) // 3minStack.push(2) // [3,2]console.log(minStack.min()) // 2minStack.push(5) // [3,2,5]console.log(minStack.min()) // 2minStack.push(-1) // [3,2,5,-1]console.log(minStack.min()) // -1minStack.pop() // [3,2,5]minStack.pop() // [3,2]minStack.pop() // [3]console.log(minStack.min()) // 3// 3// 2// 2// -1// 34、中序表达式转后缀表达式
思路
定义一个栈和一个 list 数组。
循环表达式元素。
如果为数字，间接增加到 list 中。
如果为左括号，则压栈。
如果为右括号，则循环栈元素，并顺次弹出栈顶元素到 list 中，直到遇到左括号完结循环。并弹出左括号。
如果为运算符，则判断过后的栈是否为空栈。如果空栈，则将运算符间接增加到空栈中。如果不为空栈则循环该栈，将栈顶的运算符优先级大于等于以后运算符的一次弹出，并增加到 list。直到找到优先级小于以后运算符为止。
将以后运算符压栈。
循环完结后，将栈中剩下的元素，顺次弹出栈顶元素并增加到 list 中。
并返回 list 后果。
代码实现
const priorityMap = { '+': 1, '-': 1, '*': 2, '/': 2}function infixExpToPostfixExp(exp) { const stack = new Stack() const list = [] for (let i = 0; i < exp.length; i++) { const item = exp[i] if (!isNaN(item)) { list.push(item) } else if (item === '(') { stack.push(item) } else if (item === ')') { while (stack.top() !== '(') { list.push(stack.pop()) } stack.pop() } else { while (!stack.isEmpty() && ['+', '-', '*', '/'].indexOf(stack.top()) !== -1 && priorityMap[stack.top()] >= priorityMap[item]) { list.push(stack.pop()) } stack.push(item) } } while(!stack.isEmpty()) { list.push(stack.pop()) } return list}const test1 = ['12', '+', '3'] // 12+3const test2 = ['2', '-', '3', '+', '2'] // 2-3+2const test3 = ['(', '1', '+', '(', '4', '+', '5', '+', '3', ')', '-', '3', ')', '+', '(', '9', '+', '8', ')'] // (1+(4+5+3)-3)+(9+8)console.log(infixExpToPostfixExp(test1))console.log(infixExpToPostfixExp(test2))console.log(infixExpToPostfixExp(test3))