阅读 3

数据结构-队列

队列的特性

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队的元素遵循先进先出的原则。 如图:

实现思路

通过使用javascript提供的数组实现队列先进先出的特性,同时实现队列的大小,是否为空,添加、删除等基本功能,即可。

代码实现

var Queue = function(){
    // 保存数据
    var items = [];

    /** 入队列 */
    this.enQueue = function(element){
        items.push(element);
    }

    /** 出队列 */
    this.deQueue = function(){
        return items.shift();
    }

    /** 队列顶 */
    this.front = function(){
        return items[0];
    }

    /** 队列大小 */
    this.size = function(){
        return items.length;
    }

    /** 是否为空 */
    this.isEmpty = function(){
        return items.length === 0
    }

    /** 队列内容 */
    this.values = function(){
        return items;
    }
}
复制代码

循环队列

小时候都玩过丢手绢,m个人围一圈,从一个人开始数数,数到n的时候,即数到这个数的人出局,一直淘汰直到最后剩下最后一个人,则这个人就是胜利者。

请思考下,如何选出这个胜利者? 这个一个循环数数的问题,相当于排队的人,从前面出队,插到队尾,一直循环,当数到n这数时,出队的人不再插到队尾直接淘汰,然后接着数,直到循环队列剩下最后一个人就是胜出。这就是一个循环队列的实例。以下便是代码的实现:

var cricle = function(names, number){
    var queue = new Queue();
    for(let i = 0; i< names; i++>){
        queue.enQueue(names[i]);
    }
    while(queue.size > 1){
        // 循环队列,插入队尾
        for(let i = 0; i< number-1; i++){
            queue.enQueue(queue.deQueue());
        }
        // 数到第number次,出队列
        console.log('出队列的姓名是:',que.dequeue())
    }
    // 最终结束只剩一个就是胜出者
    console.log('最终胜利者的姓名是:',que.dequeue())
}
复制代码

优先队列

火车抢票想必大家都经历过,出票的过程正常是按订购时间排队出票,然而买了加速包或者办了vip会员的人都有优先出票的权利,就不能正常排队了,同时还有黑卡会员,金卡会员等等,等级越高,肯定排队优先级不一样(无奈吧!!!)这个时候如何解决排队问题,简单的队列也就无法满足要求,这个时候我们就需要用到优先队列来解决问题。

何为加权队列?即在队列基础上加上一个优先级,在排队的时候需要按照优先级将优先级高的排在前面(也就是我们说的插队),下面就是优先队列的一个代码实现:

var PriorityQueue = function(){
    // 保存数据的
    var items = [];
    // 辅助类(包括元素和优先级)
    var priorityQueueItem = function(element, priority){
        this.element = element;
        this.priority = priority;
    }

    this.enQueue = function(element, priority){
        let queueItem = new priorityQueueItem(element, priority);
        let add = false;
        // 优先队列权限高的排前面
        for(let i = 0; i < items.length; i++){
            // 优先级大的插队排到前面
            if(queueItem.priotity > items[i].priority){
                items.spilce(i, 0, queueItem);
                add = true;
            }
        }
        /** 优先级最小 */
        if(!add){
            items.push(queueItem);
        }
    }
    /**
     * 其他队列的操作同上面普通队列的操作方法一致,这里不复述了
     */
}
复制代码

优先队列的核心在于入队列的时候需要比较元素的优先级,然后插入合适的位置,其他操作与普通队列是一致的。

关注下面的标签,发现更多相似文章
评论