数据结构学习数组、栈和队列

数组

数组是最简单的内存数据结构，由于其简单性和灵活性，很多编程语言都内置数组，JS当然也支持。关于数组的介绍可参考以下文章

数组基础学习

数组方法学习

栈

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的
同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

在现实生活中也能发现很多栈的例子，比如一摞书，最新的书在最上面，取书的时候也是先取最上面。栈也被用在编程语言的编译器和内存中保存变量、方法调用等。JS是一门解释性语言，编译过程是由浏览器完成的，JS中的原始值都是在栈中存储的

利用数组的push和pop方法，可以很方面的模拟栈数据结构

首先为栈声明一些方法

push(element(s)) ：添加一个（或几个）新元素到栈顶。
pop() ：移除栈顶的元素，同时返回被移除的元素。
peek() ：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返
回它）。
isEmpty() ：如果栈里没有任何元素就返回 true ，否则返回 false 。
clear() ：移除栈里的所有元素。
size() ：返回栈里的元素个数。这个方法和数组的 length 属性很类似。

实现声明的方法

class Stack {
  constructor () {
    this.items = []; //{1}
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  clear() {
    this.items = [];
  }
  size() {
    return this.length;
  }
}

// 使用
let s = new Stack();
s.push('a');

这种方式实现的栈结构有个缺点，由于items是公有属性，导致外部能随意操作items中的值。这样实现的栈本质上和数组没什么区别，所以要想办法把items变成私有属性，一个比较简单的方法是使用ES6的WeakMap

let Stack = (function(){
  const items = new WeakMap();
  class Stack {
    constructor() {
    items.set(this, []);
  }
  //其他方法
  }
  return Stack;
})()

除此之外，也可以通过特权方法达到属性私有化的目的

function Stack() {
  let items = []; // 私有属性
  this.push = function(element) { // 特权方法
    items.push(element)
  }
  // 其他方法
}

let s = new Stack();
s.push('a');

应用

使用栈结构实现十进制转二进制

function divideBy2(decNumber){
var remStack = new Stack,
  rem,
  binaryString = '';
while (decNumber > 0){
  rem = Math.floor(decNumber % 2);
  remStack.push(rem);
  decNumber = Math.floor(decNumber / 2);
}
while (!remStack.isEmpty()){
  binaryString += remStack.pop().toString();
}
return binaryString;
}

divideBy2(10); // '1010'

队列

队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。
队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在现实中，最常见的队列的例子就是排队，比如在电影院、自助餐厅、杂货店收银台，排在第一位的人会先接受服务，服务完成后先离开

使用数组的push和shift方法可以模拟这种数据结构

队列要实现的方法

enqueue(element(s)) ：向队列尾部添加一个（或多个）新的项。
dequeue() ：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front() ：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。
isEmpty() ：如果队列中不包含任何元素，返回 true ，否则返回 false 。
size() ：返回队列包含的元素个数，与数组的 length 属性类似。

使用ES6实现队列

let Queue = (function(){
  let items = new WeakMap();
  class Queue {
    constructor() {
      items.set(this, []);
    }
    enqueue() {
      this.items.push(element);
    }
    dequeue() {
      return this.items.shift();
    }
    front() {
      return this.items[0];
    }
    isEmpty() {
      return this.items.length === 0;
    }
    size() {
      return this.items.length;
    }
  }
  return Queue;
})()

使用ES5实现队列

function Queue() {
  let items = [];
  this.enqueue = function(element){
    items.push(element);
  };
  // 其他方法
}