JavaScript数据结构与算法(三) 优先级队列的实现

TypeScript方式实现源码

// Queue类和PriorityQueue类实现上的区别是，要向PriorityQueue添加元素，需要创建一个特殊的元素。这个元素包含了要添加到队列的元素（它可以是任意类型）及在队列中的优先级
class QueueElement {
    element;
    priority;
    constructor(element, priority) {
        this.element = element;
        this.priority = priority;
    }
}
class PriorityQueue {
    items = [];
    public enqueue(element, priority) {
        let queueElement = new QueueElement(element, priority);

        if (this.isEmpty()) {
            this.items.push(queueElement);
        } else {
            let added = false;
            for (let i = 0; i < this.items.length; i++) {
                if (queueElement.priority < this.items[i].priority) {
                    this.items.splice(i, 0, queueElement);
                    added = true;
                    break;
                }
            }
            if (!added) {
                this.items.push(queueElement);
            }
        }
    }
    public dequeue() {
        return this.items.shift();
    }
    public front() {
        return this.items[0];
    }
    public isEmpty() {
        return this.items.length == 0;
    }
    public clear() {
        this.items = [];
    }
    public size() {
        return this.items.length;
    }
    public print() {
        console.log(this.items.toString());
    }
}
// 使用方法
let priorityQueue = new PriorityQueue();
priorityQueue.enqueue('John', 2);
priorityQueue.enqueue('Jack', 1);
priorityQueue.enqueue('Camila', 1);
priorityQueue.print();

// 下图中可以看到每条命令的结果

 

JavaScript方式实现源码

var QueueElement = (function () {
    function QueueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }
    return QueueElement;
}());
var PriorityQueue = (function () {
    function PriorityQueue() {
        this.items = [];
    }
    PriorityQueue.prototype.enqueue = function (element, priority) {
        var queueElement = new QueueElement(element, priority);
        if (this.isEmpty()) {
            this.items.push(queueElement);
        }
        else {
            var added = false;
            for (var i_1 = 0; i_1 < this.items.length; i_1++) {
                if (queueElement.priority < this.items[i_1].priority) {
                    this.items.splice(i_1, 0, queueElement);
                    added = true;
                    break;
                }
            }
            if (!added) {
                this.items.push(queueElement);
            }
        }
    };
    PriorityQueue.prototype.dequeue = function () {
        return this.items.shift();
    };
    PriorityQueue.prototype.front = function () {
        return this.items[0];
    };
    PriorityQueue.prototype.isEmpty = function () {
        return this.items.length == 0;
    };
    PriorityQueue.prototype.clear = function () {
        this.items = [];
    };
    PriorityQueue.prototype.size = function () {
        return this.items.length;
    };
    PriorityQueue.prototype.print = function () {
        console.log(this.items.toString());
    };
    return PriorityQueue;
}());

 

代码角度解读：
    PriorityQueue对比Queue.PriorityQueue为每个队列元素包裹了一个对象，该对象用于优先级的标记，添加时会对队列中所有数据进行便利计算.其他使用接口一致
抽象：
    优先队列的应用场景非常多比如排队买票、地铁安检、飞机登机、任务计划、项目排期.等等都是队列,优先队列是对队列的扩展，比如排队买票只有一个窗口,出于人道主义,
老人与小朋友可以优先.这时优先队列便可以将他们安排到队列前面
总结：
    当Queue能解决应用场景问题时不推荐使用PriorityQueue，以此来优化内存开支