队列 --js实现

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

function Queue () {
  let items = []
  //队尾添加项
  this.enqueue=function(v){
    items.push(v)   
  }
  //移除队列第一项
  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.print=function(){
   console.log(items.toString())
}
}

应用1:优先队列

现实中的例子，头等舱的人比经济舱的人先上飞机

//最小优先队列
function PriorityQueue(){
  let items=[]
  function QueueElement(element,priority){
    this.element=element
    this.priority=priority
   }
  this.enqueue=function(element,priority){
    let queueElement=new QueueElement(element,priority)
    let add=false
    for(let i=0;i<items.length;i++){
      if(queueElement.priority<items[i].priority){
        items.splice(i,0,queueElement)//确保按照优先级排序，之前插入的元素已经的按序排列的
        add=true
        break
      }
    }
   if(!add){
     items.push(queueElement)//优先级不满足上面的条件则添加在队尾
    }
  }
  this.print=function(){
    for(let i=0;i<items.length;i++){
      console.log(`${items[i].element}-${items[i].priority}`)
    }
  }
    this.front=function(){
    return items[0]
  }
  //检查是否为空
  this.isEmpty=function(){
    return items.length==0
  }
  //返回队列长度
  this.size=function(){
    return items.length
  } 
}

队列应用2：击鼓传花

击鼓传花：百度百科