2. Queue(队列)
Queue和Stack有一些类似,不同的是Stack是先进后出,而Queue是先进先出。Queue在生活中的例子比如排队上公交,排在第一个的总是最先上车;又比如打印机的打印队列,排在前面的最先打印。
Queue一般具有以下常见方法:
enqueue:入列,向队列尾部增加一个元素
dequeue:出列,移除队列头部的一个元素并返回被移除的元素
front:获取队列的第一个元素
isEmpty:判断队列是否为空
size:获取队列中元素的个数
Javascript中的Array已经具备了Queue的一些特性,所以我们可以借助Array实现一个Queue类型:
function Queue() {
var collection = [];
this.print = function () {
console.log(collection);
}
this.enqueue = function (element) {
collection.push(element);
}
this.dequeue = function () {
return collection.shift();
}
this.front = function () {
return collection[0];
}
this.isEmpty = function () {
return collection.length === 0;
}
this.size = function () {
return collection.length;
}
}
Priority Queue(优先队列)
Queue还有个升级版本,给每个元素赋予优先级,优先级高的元素入列时将排到低优先级元素之前。区别主要是enqueue方法的实现:
function PriorityQueue() {
...
this.enqueue = function (element) {
if (this.isEmpty()) {
collection.push(element);
} else {
var added = false;
fo
longtestyan