栈

先进后出（后进先出）

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

使用js的数组实现一个栈

  1. function Stack() {
  2.   const items = []
  4.   // 从栈顶添加元素，压栈
  5.   this.push = function (item) {
  6.     items.push(item)
  7.   }
  9.   // 弹出
  10.   this.pop = function () {
  11.     return !this.isEmpty() && items.pop()
  12.   }
  14.   // 返回栈顶元素
  15.   this.top = function () {
  16.     return !this.isEmpty() && items[items.length - 1]
  17.   }
  19.   // 判断是否为空
  20.   this.isEmpty = function () {
  21.     return items.length === 0
  22.   }
  24.   // 返回栈里的大小
  25.   this.size = function () {
  26.     return items.length
  27.   }
  29.   // 清空栈
  30.   this.clear = function () {
  31.     items.length = 0
  32.   }
  33. }

判断括号是否合法

思路

遍历字符串，当遇到 ( 时，添加一个记号到栈中，表示这是第一对括号的开头。
当遇到 ) 时，我们从栈中取出一个记号，表示该括号为一组。
中途如果遇到 ） 无法pop的时候，则表示缺少了 (。直接返回 false。
遍历结束后，我们判断栈的长度。如果栈空，则表示所有括号都抵消掉返回 true。如果长度不为 0，则表示其中缺少了 )。返回 false。

实现

  1. const str1 = '(12)(323)()123(1))'
  2. const str2 = '()(123123)'
  4. function isLegal(str) {
  5.   const items = new Stack()
  6.   for (let i = 0; i < str.length; i++) {
  7.     if (str[i] === '(') {
  8.       items.push(1)
  9.     } else if (str[i] === ')') {
  10.       if (items.isEmpty()) return false
  11.       else items.pop()
  12.     }
  13.   }
  14.   return items.isEmpty()
  15. }
  17. console.log(isLegal(str1), isLegal(str2))

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

思路

遍历该数组表达式，将所有数字添加到栈中。
当遇到运算符时，从栈中取出两个数字进行拼接，使用eval进行计算，并将结果重新压栈。继续循环
循环结束后，如果表达式正确会剩下最后一个数值，我们只需要从栈中取出来返回即可

实现

  1. // 4+13/5
  2. const exp1 = ['4', '13', '5', '/', '+']
  3. const exp2 = ['10', '6', '9', '3', '+', '-11', '*', '/', '*', '17', '+', '5', '+']
  5. function calcExp(exp) {
  6.   const stack = new Stack()
  7.   for (let i = 0; i < exp.length; i++) {
  8.     const item = exp[i]
  9.     if (['+', '-', '*', '/'].indexOf(item) >= 0) {
  10.       const value1 = stack.pop()
  11.       const value2 = stack.pop()
  12.       const expStr = value2 + item + value1
  13.       stack.push(parseInt(eval(expStr)).toString())
  14.     } else {
  15.       stack.push(item)
  16.     }
  17.   }
  18.   return stack.pop()
  19. }
  21. console.log(calcExp(exp1))
  22. console.log(calcExp(exp2))

实现一个有min方法的栈

实现一个栈，除了常见的push，pop方法以外，提供一个min方法，返回栈里最小值。要求时间复杂度为 O(1)

思路

定义两个栈，一个正常存数据和操作，下文简称栈。另一个存每次的进栈时的最小值，下文简称min栈。
当每次push的时候，将值正常添加到栈中。我们判断min栈中，如果为空或者min栈顶的数据比添加的值大，那么我们进行压栈。此时min栈顶就是此次操作中的最小值。
每次pop的时候，栈和min栈正常操作即可。min栈pop一个元素后的栈顶。因为每次push我们都会往min栈中压入该状态的最小值。此时取栈顶的值，依旧是该栈中的最小值。

实现

  1. function MinStack() {
  2.   const stack = new Stack()
  3.   const minStack = new Stack()
  5.   this.push = function (item) {
  6.     stack.push(item)
  7.     if (minStack.isEmpty() || minStack.top() > item) {
  8.       minStack.push(item)
  9.     } else {
  10.       minStack.push(minStack.top())
  11.     }
  12.   }
  13.   this.pop = function () {
  14.     if (stack.isEmpty()) return false
  15.     stack.pop()
  16.     minStack.pop()
  17.   }
  18.   this.min = function () {
  19.     return minStack.top()
  20.   }
  21. }
  23. const minStack = new MinStack()
  25. minStack.push(3) // [3]
  26. console.log(minStack.min()) // 3
  27. minStack.push(2) // [3,2]
  28. console.log(minStack.min()) // 2
  29. minStack.push(5) // [3,2,5]
  30. console.log(minStack.min()) // 2
  31. minStack.push(-1) // [3,2,5,-1]
  32. console.log(minStack.min()) // -1
  33. minStack.pop() // [3,2,5]
  34. minStack.pop() // [3,2]
  35. minStack.pop() // [3]
  36. console.log(minStack.min()) // 3
  38. // 3
  39. // 2
  40. // 2
  41. // -1
  42. // 3

中序表达式转后缀表达式

思虑

定义一个栈和一个 list 数组。
循环表达式元素。
如果为数字，直接添加到 list 中。
如果为左括号，则压栈。
如果为右括号，则循环栈元素，并以此弹出栈顶元素到 list 中，直到遇到左括号结束循环。并弹出左括号。
如果为运算符，则判断当时的栈是否为空栈。如果空栈，则将运算符直接添加到空栈中。如果不为空栈则循环该栈，将栈顶的运算符优先级大于等于当前运算符的一次弹出，并添加到 list。直到找到优先级小于当前运算符为止。
将当前运算符压栈。
循环结束后，将栈中剩下的元素，依次弹出栈顶元素并添加到 list 中。
并返回 list 结果。

实现

  1. const priorityMap = {
  2.   '+': 1,
  3.   '-': 1,
  4.   '*': 2,
  5.   '/': 2
  6. }
  8. function infixExpToPostfixExp(exp) {
  9.   const stack = new Stack()
  11.   const list = []
  12.   for (let i = 0; i < exp.length; i++) {
  13.     const item = exp[i]
  14.     if (!isNaN(item)) {
  15.       list.push(item)
  16.     } else if (item === '(') {
  17.       stack.push(item)
  18.     } else if (item === ')') {
  19.       while (stack.top() !== '(') {
  20.         list.push(stack.pop())
  21.       }
  22.       stack.pop()
  23.     } else {
  24.       while (!stack.isEmpty() && ['+', '-', '*', '/'].indexOf(stack.top()) !== -1 && priorityMap[stack.top()] >= priorityMap[item]) {
  25.         list.push(stack.pop())
  26.       }
  27.       stack.push(item)
  28.     }
  29.   }
  31.   while(!stack.isEmpty()) {
  32.     list.push(stack.pop())
  33.   }
  34.   return list
  35. }
  37. const test1 = ['12', '+', '3'] // 12+3
  38. const test2 = ['2', '-', '3', '+', '2'] // 2-3+2
  39. const test3 = ['(', '1', '+', '(', '4', '+', '5', '+', '3', ')', '-', '3', ')', '+', '(', '9', '+', '8', ')'] // (1+(4+5+3)-3)+(9+8)
  41. console.log(infixExpToPostfixExp(test1))
  42. console.log(infixExpToPostfixExp(test2))
  43. console.log(infixExpToPostfixExp(test3))