数据结构: 队列

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


分享到:


相關文章: