隊(duì)列
- 普通隊(duì)列 先進(jìn)先出FIFO
- 循環(huán)隊(duì)列 隊(duì)首出隊(duì)后，又從隊(duì)尾入隊(duì)
- 優(yōu)先隊(duì)列
如果優(yōu)先值小的元素放到隊(duì)列的前面，這叫做最小優(yōu)先隊(duì)列
反之優(yōu)先值大的元素放到隊(duì)列的前面，這叫做最大優(yōu)先隊(duì)列
隊(duì)列的操作（就是醫(yī)院看病排隊(duì)）
- 向隊(duì)列中添加元素（進(jìn)入排隊(duì)的隊(duì)伍中）--push
- 移除隊(duì)頭元素（隊(duì)伍最前面的人出隊(duì)，進(jìn)診室）--shift
- 查看隊(duì)頭元素（查看隊(duì)伍最前面的人）--front
- 判斷隊(duì)列是否為空（看看隊(duì)伍中有沒有人）--isEmpty
- 移除隊(duì)伍全部元素（下班了，都走了吧）--clear
- 查看棧里元素個(gè)數(shù)（查看排隊(duì)的有多少人）--size
實(shí)現(xiàn)一個(gè)隊(duì)列類
function Queue(){
var queueData = [];
// FIFO=Fisrt In First Out
this.push = function(element){//入隊(duì)操作---在數(shù)組尾插入新元素
queueData.push(element);
return queueData;
};
this.shift = function(element){//出隊(duì)操作---在數(shù)組頭刪除元素
return shiftElement = queueData.shift(element);
};
this.front = function(){
return queueData[0];
};
this.size = function(){
return queueData.length;
};
this.isEmpty = function(){
return queueData.length == 0;
}
this.clear = function(){
queueData = [];
}
this.print = function(){
console.log(queueData.toString())
}
}
最小優(yōu)先隊(duì)列
function PriorityQueue(){
var queueData = [];
function QueEle(element,priority){
this.element = element;
this.priority = priority;
}
//-----------與普通隊(duì)列的不同是在入隊(duì)過程中判斷優(yōu)先級(jí)，來確定元素在隊(duì)列該插入的位置。
this.push = function(element,priority){
var queObj = new QueEle(element,priority);
if(this.isEmpty()){
this.push(queObj);
}else{
var flag = false;
for(var i=0;i<queueData.length;i++){
if(queObj.priority<queueData[i].priority){
//判斷優(yōu)先級(jí)，優(yōu)先級(jí)小的放在優(yōu)先級(jí)大的前面，
queueData.splice(i, 0, queObj);//插入元素
flag = true;
break;
}
}
if(!flag){
queueData.push(queObj);
}
}
}
this.shift = function(element){//出隊(duì)操作---在數(shù)組頭刪除元素
return shiftElement = queueData.shift(element);
};
this.front = function(){
return queueData[0];
};
this.size = function(){
return queueData.length;
};
this.isEmpty = function(){
return queueData.length == 0;
}
this.clear = function(){
queueData = [];
}
this.print = function(){
var temp = [];
for(var j=0;j<queueData.len;j++){
temp.push(queueData[i].ele);//只輸出元素的名字
}
console.log(temp.toString());
}
}
循環(huán)隊(duì)列--擊鼓傳花問題
核心代碼就是將隊(duì)列變成循環(huán)隊(duì)列，按照給定的次數(shù)循環(huán)隊(duì)列后，將隊(duì)首的元素出隊(duì)，直到隊(duì)列的長(zhǎng)度為1。結(jié)束隊(duì)列，返回隊(duì)列中存在的最后一個(gè)值。
function JGCH(namelists,num){//nameList為姓名數(shù)組，num為一個(gè)數(shù)字用來迭代隊(duì)列
var hua = new Queue();
for(var m=0;m<namelists.length;m++){
hua.push(namelists[m]);//將傳入的數(shù)組存入隊(duì)列中
};
var loser;
while(hua.size()>1){
for(var n=0;n<num;n++){
hua.push(hua.shift());//出隊(duì)后入隊(duì)，形成循環(huán)隊(duì)列
}
loser = hua.shift();
console.log(loser+"淘汰");//每一次迭代完成后，將隊(duì)首的出隊(duì)
}
return hua.shift();
}//詳細(xì)代碼及測(cè)試用例如下
擊鼓傳花結(jié)果
