Javascript数据结构与算法学习（二）——队列

什么是队列？

队列（Queue）—— 一种先入先出（FIFO）的数据结构。队列只能在队尾插入元素（push)，在队首删除元素(shift),这一点跟栈（LIFO）结构是不同的，可以看成“排队”

队列的操作

入列：enqueue 出列：dequeue 查看列头：front 不否为空：isEmpty 队列大小: size

因为JS是一门高级语言，所以对于实现队列，借助数组可以很好的实现

function Queue(){
          
   
    var items = [];
    this.enqueue = function(item){
          
   
        items.push(item)
    }
    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
    }
}

队列的实践—— 击鼓传花

描述：从0开始传，每传到第3位时，删除第3位，直到最后一们 原理：每次取出队列前一位放到队列尾，当到第三位时，移除

function delevery(names,number){
          
   
    var queue = new Queue();
    for(let i=0;i<names.length;i++){
          
   
        queue.enqueue(names[i])
    }
    while(queue.length>1){
          
   
        for(let i=1;i<number;i++){
          
   
            queue.enqueue(queue.dequeue())
        }
        queue.dequeue();
    }
    console.log(queue.front())
}
var names = [a,b,c,d,e,f];
delevery(names,3);

优先队列和辅助类

优先队列： 根据元素的优先级，队列中元素有不同的出列顺序。如 飞机–高级会员–优先登机 。 在一般情况下，从队列中删除的元素，一定是率先入队的元素。但有的特殊情况不用遵守先进先出的约定。

function PriorityQueue(){
          
   
    var items = []
    // 辅助类
    var QueueItem = function (name,priority){
          
   
        this.name = name;
        this.priority = priority
    }
    this.enqueue = function(ele,priority){
          
   
        var queueItem = new QueueItem(ele,priority);
        var added = false;
        for(let i=0;i<items.length;i++){
          
   
            if(queueItem.priority>items[i].priority){
          
   
                items.splice(i,0,queueItem)
                added= true;
                break;
            }
        }
        if(!added){
          
   
            items.push(queueItem)
        }
    }
    this.showQueue = function(){
          
   
        console.log(items)
    }
}
var test = new PriorityQueue();
test.enqueue(小明,5)
test.enqueue(小黑,12)
test.showQueue()