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.isEmpty = function(){
return items.length == 0;
}
this.print = function(){
console.log(items);
}
}
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
网友评论