笔试算法须知---用JS实现队列处理问题
2017-09-24 本文已影响0人
edisonchan
队列
- 普通队列 先进先出FIFO
- 循环队列 队首出队后，又从队尾入队
- 优先队列
如果优先值小的元素放到队列的前面，这叫做最小优先队列
反之优先值大的元素放到队列的前面，这叫做最大优先队列
队列的操作（就是医院看病排队）
- 向队列中添加元素（进入排队的队伍中）--push
- 移除队头元素（队伍最前面的人出队，进诊室）--shift
- 查看队头元素（查看队伍最前面的人）--front
- 判断队列是否为空（看看队伍中有没有人）--isEmpty
- 移除队伍全部元素（下班了，都走了吧）--clear
- 查看栈里元素个数（查看排队的有多少人）--size
实现一个队列类
function Queue(){
var queueData = [];
// FIFO=Fisrt In First Out
this.push = function(element){//入队操作---在数组尾插入新元素
queueData.push(element);
return queueData;
};
this.shift = function(element){//出队操作---在数组头删除元素
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())
}
}
最小优先队列
function PriorityQueue(){
var queueData = [];
function QueEle(element,priority){
this.element = element;
this.priority = priority;
}
//-----------与普通队列的不同是在入队过程中判断优先级，来确定元素在队列该插入的位置。
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){
//判断优先级，优先级小的放在优先级大的前面，
queueData.splice(i, 0, queObj);//插入元素
flag = true;
break;
}
}
if(!flag){
queueData.push(queObj);
}
}
}
this.shift = function(element){//出队操作---在数组头删除元素
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());
}
}
循环队列--击鼓传花问题
核心代码就是将队列变成循环队列，按照给定的次数循环队列后，将队首的元素出队，直到队列的长度为1。结束队列，返回队列中存在的最后一个值。
function JGCH(namelists,num){//nameList为姓名数组，num为一个数字用来迭代队列
var hua = new Queue();
for(var m=0;m<namelists.length;m++){
hua.push(namelists[m]);//将传入的数组存入队列中
};
var loser;
while(hua.size()>1){
for(var n=0;n<num;n++){
hua.push(hua.shift());//出队后入队，形成循环队列
}
loser = hua.shift();
console.log(loser+"淘汰");//每一次迭代完成后，将队首的出队
}
return hua.shift();
}//详细代码及测试用例如下
击鼓传花结果
