用js实现数据结构(栈结构)

摘要：数组是计算机科学中最常用的数据结构，我们知道，在js中可以在数组的任意位置添加和删除元素。然而，我们在添加或者删除元素的时候还可以有更多的数据结构，有两种数据结构类似与数组，但在添加和删除元素的时候更为可控，他们就是栈和队列，这里主要用js来阐述一下栈的原理。

1. 什么是栈？

  栈是一种遵循先进后出（LIFO）原则的有序集合，新添加或者待删除的元素都保存的栈的末尾，称作栈顶，在栈里，新元素都靠近栈顶，旧元素都靠近栈底。在现实生活中，也能发现很多栈的例子，如一摞书，最先放的只能最后取出（当然指的是在一定的规则下，不能乱取）。栈也被用在编程语言的编译器和内存中保存变量，方法调用等。

2. 用js模拟栈结构的具体思路

• 创建一个类来表示栈，如下：

function Stack () {
  // 各种属性和方法的声明
}

• Stack类中所用的属性，首先，需要一种数据结构来保存栈里的元素，可以选择数组，如：

var items = []

• Stack中所用到的方法，如下：

1. push(element(s)) : 定义一个push方法来向栈顶添加一个或者多个元素
2. pop() : 移除栈顶的元素，同时返回被移除的元素
3. peek() : 返回栈顶的元素，并不对栈做任何的修改，也就是说该方法不会删除栈顶的元素，仅仅是返回他
4. isEmpty() : 判断栈是不是空栈，如果栈里面没有任何元素返回true,否则返回false
5. clear() : 移除栈里的所有元素
6. 返回栈里的元素个数这个方法和数组的length属性很类似

3. 编写Stack来实现上述提及到的方法

function Stack () {
  // 定义一个数组，用来保存栈里面的元素
  var items = []

  /**
   实现push方法，即往栈顶添加元素，因为存储栈元素的数据结构是数组,因此用数组的push
   方法来实现
 **/
  this.push = function (element) {
    items.push(element)
  }
  /***
    实现pop方法，该方法用来移除栈里的元素，遵循先进后出的原则LIFO,可以借用数组的
    pop方法来实现，数组的pop方法用来从数组的前面删除元素，并返回被删除的元素
  ***/
  this.pop = function () {
    return items.pop()
  }
 // ps: 通过push和pop我们就可实现元素的增加和删除，而且遵循了先进后出的原则
  /***
    实现peek方法，用于返回栈顶的元素，因此可以知道往栈里面最后添加的元素,
    因为内部是用数组来保存得，所以可以用下标来访问具体元素
  ***/
   this.peek = function () {
      return items[items.length -1]
   }

  /***
    实现isEmpty(),该方法判断栈是不是为空，是返回true，否则返回false
  ***/
  this.isEmpty = function () {
    return items.length === 0
  }

  /***
    实现size方法，类似与数组的length属性，但是栈是一种集合，因此最好用size方法来表示
  ***/
  this.size = function () {
    return items.length
  }

  /***
    实现clear，用于清空栈
  ***/
  this.clear = function () {
    items = []
    // ps: 多次调用pop方法，也能清空栈，但是一般不会这么操作
  }
}

4. 使用Stack类

4.1 基本用法

  // 先将Stack类实例化

  var stack = new Stack()

  console.log(stack.size()) // 0

  stack.push(2)

  stack.push(6)

  console.log(stack.size()) // 2

  console.log(stack.peek()) // 6

  console.log(stack.isEmpty()) // false

4.2 用Stack栈结构来实现一个进质转换(将十进制转化为任何进质)

  /***
    param1: 要转换的数

    param2: 进位基数，
  **/
  function baseConverter(decNumber, base) {
    var remStack = new Stack(), // 实例化Stack
        rem, // 余数
        baseString = '' , // 最终返回转换后的数
        digits = '0123456789ABCDEF';// 做一个映射
        
        while (decNumber > 0) {
          rem = Math.floor(decNumber % base); // 十进制向其他进质转化，除基取余
          remStack.push(rem); // 将得到的余数存起来
          decNumber = Math.floor(decNumber  / base) // 得到的整数部分继续参数运算
        } 
        
        while (!remStack.isEmpty()) {
          baseString += digits[remStack.pop()] // 后进先出，
        }
    
        return baseString
  }

  // 使用,将十进制的200分别转化为2，8，16进质

  console.log(baseConverter(200, 2)) // 11001000
  console.log(baseConverter(200, 8)) // 310
  console.log(baseConverter(200, 16)) // C8

总结：用js模拟了栈数据结构，必须注意的是要遵需先进后出的原则。