学习Javascript数据结构与算法 — 优先队列

上一篇文章我们讲了队列

队列：http://www.jianshu.com/p/9a35962d5ad5

这一章我们看一看优先队列。优先队列即在队列的基础上多了一个优先级，我们选择一个对象用来存储队列的每一个元素，使用一个属性来存储元素的优先级。存储整个优先队列我们还是使用数组。

实现：

<code>
function priorityQueue(){
var items = [];
function priorityQueueElement(element,priority){
this.element = element;
this.priority = priority;
}
this.enqueue = function(element,priority){
var Node = new priorityQueueElement(element,priority);
if(items.length == 0){
items.push(Node)
}else{
var added = false;
for(var i=0;i<items.length;i++){
if(Node.priority < items[i].priority){
items.splice(i,0,Node);
added = true;
break;
}
}
if(!added){
items.push(Node);
}
}
}
this.print =function(){
console.log(items);
}
}
var pQ = new priorityQueue();
pQ.enqueue("a",1);
pQ.enqueue("b",2);
pQ.enqueue("c",3);
pQ.enqueue("d",1);
pQ.print();

</code>

在上述代码中打印结果应该是：

[ priorityQueueElement { element: 'a', priority: 1 },
priorityQueueElement { element: 'd', priority: 1 },
priorityQueueElement { element: 'b', priority: 2 },
priorityQueueElement { element: 'c', priority: 3 } ]

这样的一个数组，其中每一个元素都是一个 priorityQueueElement 对象。

叩叩叩（手动敲黑板），划重点：

1. 使用数组存取元素，
2. 使用 priorityQueueElement 辅助类来创建一个带有优先级的元素。
3. 每次入队时需要提供元素本身的值（this.element）,以及元素本身的优先级（this.priority）;通过这两个属性，我们可以创建一个带有优先级的元素。
4. 如果保存队列的数组是空数组，我们直接 push 进去。
5. 如果数组不为空，我们先声明一个变量用来存储是否入队的状态，开始遍历数组，如果遇到一个元素的优先级大于需要入队的元素，那么我们把当前元素插入这个元素之前，使用 splice 方法。
6. 如果遍历玩一遍都没有发现有元素大于新元素，那么我们把新元素push到结尾。

进度有点慢，明天更新，循环队列。～～