算法入门及简单练习——栈前端javascript算法

栈
文章图片

什么是栈
先进后出（后进先出）
常见的方法

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/5 const 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()) // 3 minStack.push(2) // [3,2] console.log(minStack.min()) // 2 minStack.push(5) // [3,2,5] console.log(minStack.min()) // 2 minStack.push(-1) // [3,2,5,-1] console.log(minStack.min()) // -1 minStack.pop() // [3,2,5] minStack.pop() // [3,2] minStack.pop() // [3] console.log(minStack.min()) // 3// 3 // 2 // 2 // -1 // 3

4、中序表达式转后缀表达式思路 【算法入门及简单练习——栈】定义一个栈和一个 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+3 const test2 = ['2', '-', '3', '+', '2'] // 2-3+2 const 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))