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