队列实现

[guyuezhai]

实现队列，具有以下功能

• enqueue : 向队尾添加一个（或几个）新元素
• dequeue : 移除队列中第一个的元素，同时返回被移除的元素
• front : 返回队列中第一个元素，不对队列做任何修改
• isEmpty : 如果队列里没有任何元素返回true，否则返回false
• size: 返回队列中元素个数
• print : 把队列中存放的元素打印出来

  ES5 实现队列

  function Queue() {
  let 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
  }
  this.print=function(){
      console.log(items.toString())
  }
  }

  ES6 实现

  
  let Queue=(function () {
  let items=new WeakMap()
  class Queue{
      constructor(){
          items.set(this,[])
      }
      enqueue(item){
          let arr=items.get(this)
          arr.push(item)
      }
      dequeue(){
          let arr=items.get(this)
          return arr.shift()
      }
      front(){
          let arr=items.get(this)
          return arr[0]
      }
      isEmpty(){
          let arr=items.get(this)
          return arr.length==0
      }
      size(){
          let arr=items.get(this)
          return arr.length
      }
      print(){
          let arr=items.get(this)
          console.log(arr.toString())
      }
  }
  return Queue
  })()

[guyuezhai]

优先级队列

function PriorityQueue() {
     let items=[]
     function QueueElement(item,priority) {
         this.item=item;
         this.priority=priority
     }
     this.enqueue=function(item,priority){
        let element=new QueueElement(item,priority)
        let add=false,length=items.length;
        for(let i=0;i<length;i++){
            if(element.priority<items[i].priority){
                items.splice(i,0,element)
                add=true
                break
            }
        }
        if(!add){
            items.push(element)
        }
     }
     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(){
        let length=items.length
        for(let i=0;i<length;i++){
            console.log("item: %s-priority: %s",items[i].item,items[i].priority)
        }

    }
 }

[guyuezhai]

队列的应用

击鼓传花

function hotPotato(nameList,num) {
     let queue=new Queue()
     let length=nameList.length
     for(let i=0;i<length;i++){
        queue.enqueue(nameList[i])
     }

     while(queue.size()>1){
         for(let i=0;i<num;i++){
             queue.enqueue(queue.dequeue())
         }
         let name=queue.dequeue()
         console.log(" %s 已经被淘汰",name)
     }
     return queue.dequeue()
 }

 let winner=hotPotato(['张三','李四','王五','王麻子','隔壁老王'],4)
 console.log('最终胜出者是---> %s',winner)

打印结果

隔壁老王 已经被淘汰 张三 已经被淘汰 王五 已经被淘汰 王麻子 已经被淘汰 最终胜出者是---> 李四