JS数据结构与算法——栈

1、栈结构概念

栈(Stack)是一种先进后出(LIFO Last in First out)的线性表，先进栈的将会比后进栈的先出栈。

• 栈的限制是仅允许在一端进行插入和删除运算。这一端被称为栈顶，相对地将另一端称为栈底；
• 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
• 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素；
  

2、栈操作

栈的常见操作包含以下几种：

• push(element): 入栈，将一个元素加入栈顶
• pop(): 出栈，将栈顶元素从栈中弹出，同时返回弹出元素
• peek(): 返回栈顶元素，不会对其进行其他操作
• isEmpty(): 查看栈是否为空
• size(): 返回栈内元素个数
• clean(): 清空栈内元素
• toString(): 返回字符串

3、栈封装示例

function Stack() {
  this.items = [];

  //压栈
  /*this.push = function(){} 该方法也可用，相对于实例的属性*/
  //相对于对象的属性，性能更优
  Stack.prototype.push = function (element) {
    this.items.push(element)
  }

  //出栈
  Stack.prototype.pop = function () {
    return this.items.pop()
  }

  //查看栈顶元素
  Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
  }

  //判断栈是否为空
  Stack.prototype.isEmpty = function () {
    return this.items.length == 0
  }

  //获取栈元素个数
  Stack.prototype.size = function () {
    return this.items.length
  }

  //toString方法
  Stack.prototype.toString = function () {
    var resultString = ''
    for (var i = 0; i < this.items.length; i++) {
      resultString = this.items[i] + ' '
    }
    return resultString
  }
}

4、栈的应用

以十进制数字转为二进制数字为例，实现思路如图：

实现代码：

    //函数：将十进制转换为二进制
    function dectobin(decNumber) {
      //定义栈对象来存放余数
      var stack = new Stack()
      while (decNumber > 0) {
        //获取余数，放入栈中
        stack.push(decNumber % 2)
        //获取整除后结果
        decNumber = Math.floor(decNumber / 2)
      }
      //依次出栈
      var binaryString = ''
      while (!stack.isEmpty()) {
        binaryString += stack.pop()
      }
      return binaryString
    }