JavaScript队列是一种遵从先进先出（FIFO）原则的有序集合

队列在尾部添加新元素，从顶部移除元素

队列的理解

队列在我们生活中最常见的场景就是排队了

队列这个名字也已经很通俗易懂了

和栈很像，这不过队列是先入先出的数据结构

队列的前面是队头

队列的后面是队尾

出队从队头出

入队从队尾入

队列的创建

和栈类似，这里我就不就不啰嗦了

同样需要实现一些功能

这里我类比生活中的排队上厕所

• 向队列中添加元素（进入排队的队伍中）
• 移除队头元素（队伍最前面的人出队进入厕所）
• 查看队头元素（查看队伍最前面的人）
• 判断队列是否为空（看看队伍中有没有人）
• 移除队伍全部元素（厕所炸了，都散了吧）
• 查看栈里元素个数（查看排队的有多少人）

于是我们可以创建一个完整队列实现，同样是利用我们的数组实现

数组头就是队列头

function Queue() {
    var items = [];
    this.enqueue = function (ele) {
        items.push(ele);
    };//入队
    this.dequeue = function () {
        return items.shift();
    };//出队
    this.front = function () {
        return items[0];
    };//查看队头元素
    this.isEmpty = function () {
        return items.length === 0;
    };//判断队列是否为空
    this.size = function () {
        return items.length;
    };//队列大小
    this.clear = function () {
        items = [];
    };//清空队列
    this.print = function () {
        console.log(items.toString());
    };//打印队列
}
var queue = new Queue();  //声明队列的实例

队列的使用

下面我们就用这个队列简单模拟排队

var queue = new Queue();
console.log("队列是否为空： " + queue.isEmpty());
queue.enqueue('Mr.A');
queue.enqueue('Mr.B');
queue.enqueue('Mr.C');
console.log("当前队列：");
queue.print();
console.log("出队的人： " + queue.dequeue());
console.log("当前队列：");
queue.print();

控制台打印：

优先队列

在我们排队上厕所的时候，来了一位拥有VIP会员卡的朋友，插到了队伍的最前面

过了一会儿又来了一位拥有SVIP会员卡的朋友，插到了VIP的前面

虽然这个比喻可能不恰当，但是生活中可能存在有优先级的队列

优先级高的人可以查到优先级低的人前面

这就是循环队列

如果优先值小的元素放到队列的前面，这叫做最小优先队列

反之优先值大的元素放到队列的前面，这叫做最大优先队列

但其实他们两个仅仅是一个判断的改变，实现方式是一样的

优先队列较普通队列的区别也就是入队要判断优先级，并且需要对我们的元素进行处理，其他方法不变

这处理也就是把元素包装为一个拥有优先级的对象

既然所有对象都有着同样的属性，那我们毫无疑问就应该使用工厂构建

我们可以稍微修改一下我们的队列类

来实现一个最小优先队列

function PriorityQueue() {
    var items = [];
    function QueEle(ele, priority){ //封装我们的元素为一个对象
        this.ele = ele; //元素
        this.priority = priority; //优先级
    }
    this.enqueue = function (ele, priority) {
        var queObj = new QueEle(ele, priority); //创建队列元素对象
        if(this.isEmpty()){ //如果队列是空的，直接插入
            this.push(queObj);
        }else{
            var bAdded = false;
            for(var i = 0, len = items.length; i < len; i++){ 
                if(priority < items[i].priority){
                    items.splice(i, 0, queObj); // 循环队列，如果优先级小于这个位置元素的优先级，插入
                    bAdded = true;
                    break;
                }
            }
            if(!bAdded){
                items.push(queObj); // 如果循环一圈都没有找到能插队的位置，直接插入队列尾部
            }
        }
    };
    this.dequeue = function () {
        return items.shift();
    };
    this.front = function () {
        return items[0];
    };
    this.isEmpty = function () {
        return items.length === 0;
    };
    this.size = function () {
        return items.length;
    };
    this.clear = function () {
        items = [];
    };
    this.print = function () {
        //这个地方稍微修改一下下
        var temp = [];
        for(var i = 0, len = items.length; i < len; i++){
            temp.push(items[i].ele);
        }
        console.log(temp.toString());
    };
}

解释我已经在代码里说的很明白

下面我们就用这个优先队列同样来模拟排队上WC

var pQueue = new PriorityQueue();
pQueue.enqueue('Mr.A', 3);
pQueue.enqueue('Mr.B', 3);
pQueue.enqueue('Mr.C', 3);
console.log("原队列:");
pQueue.print();
pQueue.enqueue('VIP', 2);
pQueue.enqueue('SVIP', 1);
console.log("新队列:");
pQueue.print();

控制台打印：

循环队列

循环队列典型的例子击鼓传花

还记得在我上高中的时候我们晚自习一停电就玩这个

拿一个东西当“花”，轮着传，“鼓”一停，拿到花的同学就要站起来唱歌

可以把循环队列当作是队列的应用

下面我们来模拟实现循环队列击鼓传花

function hotPotato(pepoleList, frequency){ //参数：表示人的数组，传花的频率
    var queue = new Queue();
    for(var i = 0, len = pepoleList.length; i < len; i++){
        queue.enqueue(pepoleList[i]); //初始化，进入队列
    }
    var eliminated;//被淘汰的同学
    while(queue.size() > 1){ //只要队列至少还有两个人，就一直循环
        for(var i = 0; i < frequency; i++){//出队入队，模拟循环效果
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();//清算
        console.log(eliminated + '被淘汰');
    }
    return queue.dequeue();//返回队列中的最后一人
}
var pepole = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F'];
var gameWinner = hotPotato(pepole, 12);
console.log('全场最佳:' + gameWinner);

控制台输出：

以上就是JavaScript下的队列实现