优先队列,实现方法有两种:设置优先级,然后再正确的位置添加元素;入列操作添加元素,然后按照优先级移除。 此处使用第一种方法。对数组或队列不熟悉的同学请移步。
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
//否则 去找一个比要添加元素的优先级更低(priority值更大)的元素,就把新元素插入到它之前。优先级相同,先进先出
{
var added = false;
for (var i = 0; i < items.length; i++) {
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement); //splice 是数组方法
added = true;
break; //添加之后跳出循环
}
}
//如果要添加的priority的值大于任何以有元素,直接添加在末尾即可
if (!added) {
items.push(queueElement);
}
}
}
//删除队列头部第一个元素
this.dequeue = function () {
return items.shift();
}
//返回队列中第一个元素
this.front = function () {
return items[0];
}
//确定元素是否为空 为空则为true 不为空则为false
this.isEmpty = function () {
return items.length === 0;
}
//返回队列长度
this.size = function () {
return items.length;
}
//打印队列
this.print = function () {
console.log(items)
for (var i = 0; i < items.length; i++) {
console.log(items[i].element)
}
}
}
定义好优先队列之后,我们开始使用:
//赵钱孙李,周吴郑王。冯陈诸卫,蒋沈韩杨。
var pq = new priorityQueue();
pq.enqueue('周', 2);
pq.enqueue('吴', 2);
pq.enqueue('郑', 2);
pq.enqueue('王', 2);
pq.enqueue('赵', 1);
pq.enqueue('钱', 1);
pq.enqueue('孙', 1);
pq.enqueue('李', 1);
pq.enqueue('将', 4);
pq.enqueue('沈', 4);
pq.enqueue('韩', 4);
pq.enqueue('杨', 4);
pq.enqueue('冯', 3);
pq.enqueue('陈', 4);
pq.enqueue('诸', 4);
pq.enqueue('卫', 4);
pq.print();
pq.size();
打印结果如下:
这里的长度没有打印出来,但是放在print()方法中,就能打印出长度。在这里报了个错,哪位大神看到了能讲解一下哇
附上我的微信平台
不喜勿喷哈