【数据结构】队列（Queue）

队列

基本概念

• 定义：在表一端进行插入操作，另一端进行删除操作的线性表。
• 队头：插入操作
  队尾：删除操作
• 特点：先进先出
  
  （图源网络）

方法

• enqueue：入列，向队列尾部增加一个元素
• dequeue：出列，移除队列头部的一个元素并返回被移除的元素
• front：获取队列的第一个元素
• isEmpty：判断队列是否为空
• size：获取队列中元素的个数

代码实现

//队列
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;
    }
}

优先队列

基本概念

• 定义：带有优先级的队列
• 优先级：数值越小，优先级越高。
• 特点：出队操作是把队列中优先级最高的元素出队列。
• 实现：优先级高的元素入列时将排到低优先级元素之前（使用二维数组实现）

方法

• enqueue：入列，按照优先级排序插入，优先级高的将排在优先级低的之前（即值小的排在值大的之前）
• dequeue：出列，移除队列头部的一个元素并返回被移除的元素
• front：获取队列的第一个元素
• isEmpty：判断队列是否为空
• size：获取队列中元素的个数

代码实现

//优先队列(给每个元素赋予优先级，优先级高的元素入列时将排到低优先级元素之前)
function PriorityQueue() {
    //优先队列采用二维数组存放值，每个元素第2个值为优先级，数值越小，优先级越高
    var collection = [];
    //打印队列
    this.print = function() {
        console.log(collection);
    }

    //入队列(优先级高的元素入列时将排到低优先级元素之前)【数值越低，优先级越高。因此是将值小的排到大的之前】
    this.enqueue = function(element) {
        if (this.isEmpty()) {
            collection.push(element);
        } else {
            var added = false;
            for (let i = 0; i < collection.length; i++) {
                if (element[1] < collection[i][1]) {
                    // 使用splice方法，实现将element添加到collection的第i个位置，即往前排
                    collection.splice(i, 0, element);
                    added = true;
                    break;
                }
            }
            if (!added) {
                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;
    }
}

//测试
var pQ = new PriorityQueue();
pQ.enqueue(['gannicus', 3]);
pQ.enqueue(['spartacus', 1]);
pQ.enqueue(['crixus', 2]);
pQ.enqueue(['oenomaus', 4]);
pQ.print();