一般情况下,队列都需要遵循FIFO原则,但在一些特殊的场合,我们希望队列的出队能够更加智能,不仅仅考虑入队先后顺序,同时还考虑队中元素的优先性,以保障资源能够得到更加科学有效的使用。
要实现优先队列,首先考虑如何区分不同优先级的元素,一种做法是给元素添加优先级标记/属性。
var element = {
......
this.priority = high / medium / low;
......
}
其次则是元素出队的实现,已知的方法是在出队方法/函数中添加判断逻辑,返回当前队列中最接近队首且优先级最高的元素;
function dequeue() {
var index = 0,//最接近队首且优先级最高的元素序号,初始为0(即队首)
superior = this.data.priority;//当前最高优先级
//遍历确定出队元素
for (var i = 1; i < this.data.length; ++i) {
if (this.data[i].priority > priority) {//若当前遍历元素优先级高于已知最高优先级
priority = this.data[i].priority;//更新最高优先级
index = i;//更新出队元素
}
}
return this.data.splice(index,1);
}
2017.04.12的更新
也可以考虑使用堆实现优先级队列,入队时调用restore重建堆,形成最大堆,即优先级最高的元素保持在堆顶,出队时弹出堆顶元素,然后调用restore再次重建堆,需要考虑的是如何保持同级元素的FIFO的特性;