一、栈的基础操作

top() //查看栈顶元素
pop() // 出栈
push(item) // 入栈
length() // 返回栈的大小
clear() // 清空或者说重置栈
isEmpty() // 查看栈是否为空

二、用数组来模拟栈

用数组来实现栈简单方便， 一般想到数组，我们的印象大概是这样的

我们可以想象把数组头朝下立起来

它就变成栈

考虑到不能让外界直接利用数组下标访问或者修改栈，需要做一些私有化处理。

三、代码实现

const Stack = (function() {
  const _items = Symbol() // 闭包 + 唯一标识symbol封装栈保证唯一性
  return class {
    constructor() {
      this[_items] = []
    }
    // 返回栈顶的元素
    top() {
      return this[_items][this[_items].length - 1]
    }
    // 新增元素
    push(el) {
      this[_items].push(el)
    }
    // 删除栈顶的元素并返回这个值
    pop() {
      return this[_items].pop()
    }
    // 清空栈
    clear() {
      this[_items] = []
    }
    // 栈的大小
    length() {
      return this[_items].length
    }
    // isEmpty
    isEmpty() {
      return this[_items].length === 0
    }
  }
})()

const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack)
stack[_items].push(4)
console.log(stack)

这里_items 虽然在内存中存在但不是全局对象（闭包的功劳）， 所以无法直接访问。

代码利用了 闭包 + symbol 做唯一标识封装栈保证栈的私有性。

四、利用栈转换进制

在 js 中，提供了 Number.prototype.toString 方法将十进制转换成其他进制，其实我们自己也可以使用栈这种数据结构，实现十进制的转换。

十进制转二进制的过程, 就是除二取余、逆序排列的过程，余数挨个入栈，然后再从栈顶挨个将余数取出，进行拼接，就得到了二进制

function baseConversionBy2(num) {
  const stack = new Stack()
  let res = ''

  while (num > 0) {
    stack.push(num % 2)
    num = Math.floor(num / 2)
  }
  while (!stack.isEmpty()) {
    res += stack.pop()
  }
  return res
}
console.log(baseConversionBy2(10)) // 1010

十进制转其他进制也同理

五、栈判断平衡括号

平衡括号概念

"{[()]}" 属于平衡括号

"{([)]}" 不属于平衡括号

"{{[}]}" 不属于平衡括号

"{{([](#))}()}" 属于平衡括号

open = '{[('

close = ')]}'

open 中包含的左半边符号入栈，如果出栈顺序和 close 包含的右半边符号一样，就可以认为是平衡括号

代码实现：

function check(str) {
  const stack = new Stack()
  const open = "{[("
  const close = "}])"
  let balanced = true
  let index = 0
  let symbol
  let top

  while (index < str.length && balanced) {
    symbol = str[index]
​
    if (open.includes(symbol)) {
      stack.push(symbol)
    } else {
      top = stack.pop()
      if (open.indexOf(top) !== close.indexOf(symbol)) {
        balanced = false
      }
    }
    index ++
  }
​
  if (balanced && stack.isEmpty()) {
    return true
  }
​
  return false
}
​
console.log(check("{[()]}")) // true
console.log(check("{([)]}")) // false
console.log(check("{{[}]}")) // false
console.log(check("{{([][])}()}")) // true