1凹炸、棧
棧是一種遵從后進先出(LIFO)原則的有序集合戏阅。新添加的或待刪除的元素都保存在棧的末尾。稱作棧頂啤它，另一端就叫棧底奕筐。在棧里，新元素都靠近棧頂变骡，舊元素都靠近棧底±牒眨現(xiàn)在通過數(shù)組的方法來實現(xiàn)棧，代碼如下：
function Stack() {
var items = [];
this.push = function(element){//添加一個（或幾個）新元素到棧頂
items.push(element);
};
this.pop = function(){//移除棧頂?shù)脑厮担瑫r返回被移除元素
return items.pop();
};
this.peek = function(){//返回棧頂?shù)脑卦ㄐ兀⒉粚Ｗ鋈魏涡薷? return items[items.length-1];
};
this.isEmpty = function(){//如果棧內(nèi)沒有任何元素就返回true，否則返回false
return items.length == 0;
};
this.size = function(){//返回棧里的元素個數(shù)
return items.length;
};
this.clear = function(){//移除棧里的所有元素
items = [];
};
this.print = function(){//打印
console.log(items.toString());
};
this.toString = function(){
return items.toString();
};
}
下面是一個小算法題台妆，可以視為棧的綜合利用翎猛，如何將10進制數(shù)字轉(zhuǎn)成2進制數(shù)字：
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();//余數(shù)除完翻轉(zhuǎn)過來就是2進制數(shù)
}
return binaryString;
}
升級版胖翰， 如何將10進制數(shù)字轉(zhuǎn)成任意進制數(shù)字，代碼如下：
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(){//如果隊列內(nèi)沒有任何元素就返回true猛遍，否則返回false
return items.length == 0;
};
this.clear = function(){//移除隊列里的所有元素
items = [];
};
this.size = function(){//返回隊列里的元素個數(shù)
return items.length;
};
this.print = function(){//打印
console.log(items.toString());
};
}
2.1、優(yōu)先隊列
指隊列元素的添加和移除是基于優(yōu)先級的碎绎。實現(xiàn)一個優(yōu)先隊列螃壤，有兩種選項：設(shè)置優(yōu)先級，然后再正確的位置添加元素筋帖；或者用入隊操作添加元素奸晴，然后按照優(yōu)先級移除他們。下例將會在正確的位置添加元素日麸，如下：
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寄啼、循環(huán)隊列——擊鼓傳花
擊鼓傳花游戲，在這個游戲中代箭，孩子們圍成一個圓圈墩划，把花盡快的傳遞給旁邊的人。某一時刻傳花停止嗡综，這個時候花落在誰手里乙帮，誰就退出圓圈結(jié)束游戲。重復(fù)這個過程极景，直到只剩下一個孩子察净。例子如下：
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