javaScript的数据结构与算法（一）——栈和队列

[wengjq]

1、栈

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾。称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。现在通过数组的方法来实现栈，代码如下：

function Stack() {
  var items = [];
  this.push = function(element){//添加一个（或几个）新元素到栈顶
    items.push(element);
  };
  this.pop = function(){//移除栈顶的元素，同时返回被移除元素
    return items.pop();
  };
  this.peek = function(){//返回栈顶的元素，但并不对栈做任何修改
    return items[items.length-1];
  };
  this.isEmpty = function(){//如果栈内没有任何元素就返回true，否则返回false
    return items.length == 0;
  };
  this.size = function(){//返回栈里的元素个数
    return items.length;
  };
  this.clear = function(){//移除栈里的所有元素
    items = [];
  };
  this.print = function(){//打印
    console.log(items.toString());
  };
  this.toString = function(){
    return items.toString();
  };
}

下面是一个小算法题，可以视为栈的综合利用，如何将10进制数字转成2进制数字：

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();//余数除完翻转过来就是2进制数
  }
  return binaryString;
}

升级版， 如何将10进制数字转成任意进制数字，代码如下：

function baseConverter(decNumber,base){
  var remStack = new 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;
} 
baseConverter(100345,2) // "11000011111111001"
baseConverter(100345,8) //"303771"
baseConverter(100345,16) // "187F9"   

2、队列

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

function Queue() {
  var items = [];
  this.enqueue = function(element){//向队列尾部添加一个（或是多个）元素
    items.push(element);
  };
  this.dequeue = function(){//移除队列的第一个元素，并返回被移除的元素
    return items.shift();
  };
  this.front = function(){//返回队列的第一个元素——最先被添加的,也将是最先被移除的元素。队列不做任何变动。（不移除元素，只返回元素信息。与stack的peek方法类似）
    return items[0];
  };
  this.isEmpty = function(){//如果队列内没有任何元素就返回true，否则返回false
    return items.length == 0;
  };
  this.clear = function(){//移除队列里的所有元素
    items = [];
  };
  this.size = function(){//返回队列里的元素个数
    return items.length;
  };
  this.print = function(){//打印                                                                                                                                                                                                                             
    console.log(items.toString());
  };
 }

2.1、优先队列

指队列元素的添加和移除是基于优先级的。实现一个优先队列，有两种选项：设置优先级，然后再正确的位置添加元素；或者用入队操作添加元素，然后按照优先级移除他们。下例将会在正确的位置添加元素，如下：

function PriorityQueue(){
  var items = [];
  function QueueElement(element, priority){
    this.element = element;
    this.priority = priority;
  }
  this.enqueue = function(element, priority){
    var queueElement = new QueueElement(element, priority);
    if(this.isEmpty()){
      items.push(queueElement);
    }else{
      var added = false;
      for(var i = 0; i < items.length; i++){
          if(queueElement.priority < items[i].priority){
            items.splice(i,0,queueElement);
            added = true;
            break;
          }
      }
    } 
    if(!added){
      items.push(queueElement);
    }
  }
  this.dequeue = function(){
    return items.shift();
  };
  this.front = function(){
    return items[0];
  };
  this.isEmpty = function(){
    return items.length == 0;
  };
  this.size = function(){
    return items.length;
  };
  this. print = function(){
    for (var i=0; i<items.length; i++){
        console.log(items[i].element + ' - ' + items[i].priority);
    }
  };
}

2.2、循环队列——击鼓传花

击鼓传花游戏，在这个游戏中，孩子们围成一个圆圈，把花尽快的传递给旁边的人。某一时刻传花停止，这个时候花落在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩下一个孩子。例子如下：

function hotPotato(namelist, num){
  var queue = new Queue();
  for(var i = 0; i < namelist.length; i++){
    queue.enqueue(namelist[i]);
  }
  var eliminated = '';
  while(queue.size() > 1){
    for(var i = 0; i < num; i++){
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();
    console.log(eliminated+"在游戏中淘汰了。");
  }
  return queue.dequeue();
}
var names = ["a","b","c","d","e"];
var winner = hotPotato(names,7);
console.log("胜利者"+winner);
//c在游戏中淘汰了。
//b在游戏中淘汰了。
//e在游戏中淘汰了。
//d在游戏中淘汰了。
//胜利者a

[stick-yi]

请问我能够把你这系列的转载么？

[wengjq]

@stick-yi 可以的。

[norname-shine]

非常的棒，我是从前端开始学习，最近开始想学习底层原理。发现老哥写的这篇文章，受益良多。
不过我推荐放点图片增加记忆，我自己是选择用数组的方法绘制了图，加强记忆。

[wengjq]

@norname-shine 嗯嗯 谢谢你的建议

[zhangwinning]

真棒

[sialvsic]

divideBy2 如果传入 0 就会有问题显示一个 '' "，更应该期待为 0

console.log(divideBy2(0) === '0');
console.log(divideBy2(1) === '1');
console.log(divideBy2(2) === '10');
console.log(divideBy2(4) === '100');