算法入门及简单练习——栈

栈

先进后出（后进先出）

• push 添加一个元素到栈顶
• pop 弹出栈顶的元素
• top 返回栈顶的元素
• isEmpty 判断是否为空
• size 返回栈里元素的个数
• clear 清空栈

使用js的数组实现一个栈

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
  }
}

判断括号是否合法

思路

遍历字符串，当遇到 ( 时，添加一个记号到栈中，表示这是第一对括号的开头。
当遇到 ) 时，我们从栈中取出一个记号，表示该括号为一组。
中途如果遇到 ） 无法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))

计算逆波兰表达式（后缀运算）

思路

遍历该数组表达式，将所有数字添加到栈中。
当遇到运算符时，从栈中取出两个数字进行拼接，使用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))

实现一个有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

中序表达式转后缀表达式

思虑

定义一个栈和一个 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))