//队列,先入先出,FIFO
function Queue() {
this.items = [];
} Queue.prototype = {
constructor: Queue,
enqueue: function(elements) {
this.items.push(elements);
},
dequeue: function() {
return this.items.shift();
},
front: function() {
return this.items[0];
},
size: function() {
return this.items.length;
},
isEmpty: function() {
return this.items.length == 0;
},
clear: function() {
this.items = [];
},
print: function() {
console.log(this.items.toString());
}
} //队列的基本使用
// var queue = new Queue();
// console.log(queue.isEmpty());
// queue.enqueue('huang');
// console.log(queue.size); //优先队列的定义 这里使用组合继承的方式继承自Queue队列
function PriorityQueue() {
Queue.call(this);
}; PriorityQueue.prototype = new Queue();
PriorityQueue.prototype.constructer = PriorityQueue;
PriorityQueue.prototype.enqueue = function(element, priority) {
function QueueElement(tempelement, temppriority) {
this.element = tempelement;
this.priority = temppriority;
}
var queueElement = new QueueElement(element, priority); if (this.isEmpty()) {
this.items.push(queueElement);
} else {
var added = false;
for (var i = 0; i < this.items.length; i++) {
if (this.items[i].priority > queueElement.priority) {
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
this.items.push(queueElement);
}
}
}
//这个方法可以用Queue的默认实现
PriorityQueue.prototype.print=function(){
var result='';
for(var i = 0; i < this.items.length;i++){
result += JSON.stringify(this.items[i]);
}
return result;
}
优先队列的使用
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("cheng", 2);
priorityQueue.enqueue("du", 3);
priorityQueue.enqueue("huang", 1);
console.log(priorityQueue.print());//{"element":"huang","priority":1}{"element":"cheng","priority":2}{"element":"du","priority":3}
console.log(priorityQueue.size());//
console.log(priorityQueue.dequeue());//{ element="huang", priority=1}
console.log(priorityQueue.size());//