队列

队列的定义

队列是遵循先进先出原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

队列的方法

enqueue(element)：向队列末尾添加一个新的项。

dequeue()：移除队列的第一项（即排在队列最前面的项），并返回被移除的元素。

clear()：清空队列。

front()： 返回队列中第一个元素（最先被添加、也将是将是最先被移除的元素）。队列不做任何变动。

isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。

size()：返回队列包含的元素的个数。

创建队列

用一个类来表示队列

function Queue() {
    // 用一个数组来存储队列的元素
    var items = [];

    // 队列的方法
    this.enqueue = function(element) {
        items.push(element);
    };

    this.dequeue = function() {
        return items.shift();
    };

    this.clear = function() {
        items = [];
    };

    this.front = function() {
        return items[0];
    };

    this.isEmpty = function() {
        return items.length === 0;
    };

    this.size = function() {
        return items.length;
    };

    this.print = function() {
        console.log( items.toString() );
    };
}

优先队列

优先队列的元素的添加和移除，是基于优先级的。

实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。

以下实现将会在正确的位置添加元素，因此，可以对它们使用默认的出列操作。

优先队列的创建

function PriorityQueue() {
     // 用一个数组来存储队列的元素
    var items = [];

    function QueueElement (element, priority) {
        this.element = element;
        this.priority = priority;
    }

    // 队列的方法
    // priority 值越大，优先级越小
    this.enqueue = function (element, priority) {
        var queueElement = new QueueElement(element, priority);

        if ( this.isEmpty() ) {
            items.push( queueElement );
        } else {
            var added = false;

            for (var i = 0; i < items.length; i++) {
                if ( queueElement.priority < items[i].priority ) {
                    items.splice(i, 0, queueElement);
                    added = true;
                    break;
                }
            }

            if (!added) {
                items.push( queueElement );
            }
        }
    }

    // 其余方法和默认的 Queue 实现相同
}