一些数据结构

data-structures.js

//栈
function Stack(){
  var value = [];
  
  if(typeof this.isEmpty !== 'function'){
    Stack.prototype.isEmpty = function(){
      return value.length === 0;
    }
  }
  
  if(typeof this.push !== 'function'){
    Stack.prototype.push = function(element){
      value.push(element);
    }
  }
  
  if(typeof this.pop !== 'function'){
    Stack.prototype.pop = function(){
      if(this.isEmpty()){
        console.error('the stack is empty!');
        return;
      }else{
        return value.pop();
      }
    }
  }
  
  if(typeof this.size !== 'function'){
    Stack.prototype.size = function(){
      return value.length;
    }
  }
  
  if(typeof this.clear !== 'function'){
    Stack.prototype.clear = function(){
      value = [];
    }
  }
  
  if(typeof this.peek !== 'function'){
    Stack.prototype.peek = function(){
      return value[value.length - 1];
    }
  }
}
//队列
//与栈类似，pop改为shift，peek改为front
//不过都用数组储存，其实效率不高？


//链表
//LinkedList
//本来方法都应该定义在prototype上的，这里偷懒了直接定义在每一个示例上
function LinkedList(){
  var head = null;
  var size = 0;
  
  function Node(element){
    this.element = element;
    this.next = null;
  }
  
  this.isEmpty = function(){
    return size === 0;
  }
  
  this.size = function(){
    return size;
  }
  if(typeof this.append !== 'function'){
    LinkedList.prototype.append = function(element){
      var node = new Node(element);
      if(head === null){
        head = node;
      }else{
        var current = head;
        while(current.next){
          current = current.next;
        }
        current.next = node;
      }
      size++;
    }
  }
  //插在position之前
  this.insert = function(position, element){
    if(position < 0 || position > this.size()){
      console.error('insert position error');
      return;
    }else{
      var current = head,
          previous;
      var node = new Node(element);
      if(position === 0){
        node.next = head;
        head = node;
      }
      for(let i = 0; i < position; i++){
        previous = current;
        current = current.next;
      }
      previous.next = node;
      node.next = current;
      size++;
    }
  }
  
  this.removeAt = function(position){
    if(position < 0 || position > this.size){
      console.error('position error');
    }else{
      var current = head,
          previous;
      if(position === 0){
        head = current.next;
      }else{
        for(let i = 0; i < position; i++){
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      size--;
      return current.element;
    } 
  }
  
  this.remove = function(element){
    if(this.isEmpty()){
      console.error('empty!');
      return;
    }
    var current = head,
        previous;
    if(head.element === element){
      head = current.next;
      return;
    }
    while(current && current.element !== element){
      previous = current;
      current = current.next;
    }
    if(current.element === element){
      previous.next = current.next;
      size--;
      return;
    }else if(current === null){
      console.error(element + ' is not in this list');
      return;
    }    
  }
  
  this.toString = function(){
    if(head === null){
      return '';
    }else{
      var current = head;
      var str = '';
      while(current){
        str += ',' + current.element;
        current = current.next;
      }
      return str.slice(1)
    }
  }
  
  this.indexOf = function(element){
    if(head === null){
      return -1;
    }else{
      var current = head,
          index = 0;
      while(current && current.element !== element){
        index++;
        current = current.next
      }
      if(current.element === element){
        return index;
      }else{
        return -1;
      }
    }
  }
  
  this.getHead = function(){
    return head.element;
  }
}

var list = new LinkedList();
list.append(1);
list.append(2);
list.insert(1, 3);
console.log(list.getHead());
console.log(list.indexOf(2));
console.log(list.toString());
list.remove();
console.log(list.toString());

//集合Set
function mySet(){
  var items = {};
  
  this.has = function(element){
    for(var item in items){
      if(items.hasOwnProperty(item))
        return true;
    }
    return false;
  }
  
  this.add = function(element){
    if(items.hasOwnProperty(element)){
      return false;
    }else{
      items[element] = element;
      return true;
    }
  }
  
  this.remove = function(element){
    if(!this.has(element)){
      return false;
    }else{
      delete items[element];
      return true;
    }
  }
  this.clear = function(){
    items = {};
  }
  this.size = function(){
    return Object.keys(items).length;
  }
  this.value = function(){
    return Object.keys(items);
  }
  
  this.union = function(otherSet){
    var unionSet = new mySet();
    var other = otherSet.value();
    var old = this.value();
    for(let i = 0; i< old.length; i++){
      unionSet.add(old[i]);
    }
    for(let i = 0; i < other.length; i++){
        unionSet.add(other[i]);
      }   
    return unionSet;
  }
  
}

var set = new mySet();
set.add(1);
set.add('hello');
var set2 = new mySet();
set2.add(1);
set2.add('wow');
var newSet = set.union(set2);
console.log(newSet.value());

//值得注意的是Object的key都会变成string，所以‘1’和1是一样的，
//而ES6的Set可以储存各种数据
var set = new Set();
set.add(1);
set.add('1');
console.log([...set.values()]);