乐趣区

关于前端:算法入门及简单练习栈

jiezi

栈

什么是栈

先进后出（后进先出）

常见的办法

  • 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))
退出移动版