數據結構: 隊列

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


分享到:


相關文章: