js数据结构-队列

前言

数据结构还是非常重要的, 今天我们来实现队列的数据结构.

正文

队列就是日常生活中的排队, 先进先出(first in first out),

普通队列

class Queue{
  items= [] //用数组来存放队列的数据

  //给队列添加一个元素
  enqueue(element){
    this.items.push(element)
  }

  //移除队列中的一个元素,根据先进先出原则
  dequeue(){
    return this.items.shift()
  }

  //获取当前队列的第一个元素
  front(){
    return this.items[0]
  }

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

  //清空队列中所有元素
  clear(){
    this.items = []
  }

  //获取队列的长度
  size(){
    return this.items.length
  }

  //打印队列
  print(){
    console.log(this.items.toString())
  }
}

优先队列

优先队列的应用之一就是医院看病排队, 医生会根据病人病情的轻重来确定看病优先级. 该队列和普通队列的不同之处就在于添加元素的方法不同, 也就是enqueue方法.

class PriorityQueue{

  //除了enqueue方法, 其他方法不变

  items= [] //用数组来存放队列的数据  

  //添加一个元素, 同时标注优先级, 
  enqueue(element,priority){
    // 最后添加进数组的是带有优先级的元素对象
    const priorityElement = {element,priority}

    //如果队列中没有任何元素, 直接添加
    if(this.isEmpty()){
      this.items.push(priorityElement)
    }else{
      let added = false //标记是否已经添加了
      //比较队列中优先级, 如果小于某个优先级则添加到该优先级的前面
      for(let i=0;i<this.items.length;i++){
        if(priority<this.items[i].priority){
          this.items.splice(i,0,{element,priorityElement})
          added = true
        }
      }
    }

    //如果队列中的优先级都比传入的元素优先级小, 则直接添加到队列末尾
    if(!added){
      this.items.push(priorityElement)
    }
  }
}

循环队列

击鼓传花游戏就是这种队列的应用, 首先一群学生组成一个队列(假设10个人), 第一同学开始传花, 然后老师心里默想一个数字(假如数字为10), 当传递次数到达老师心中默想的数字时, 老师喊停, 从而淘汰手中有花的同学. 每次淘汰完一个同学后, 老师重新默想一个新得数字. 如此循环直到淘汰剩下最后一个人时, 该人获胜.

下面我们来实现该循环队列逻辑

class HotPotato{//烫手山芋

  this.queue = new Queue() //保存同学的普通队列

  constructor(nameList){
    this._initQueue(nameList)
  }

  //初始化同学队列
  _initQueue(nameList){
    for(let i=0;i<nameList.length;i++){
      this.queue.enqueue(nameList[i])
    }
  }

  //玩击鼓传花游戏
  play(){
    let eliminated = ''
    //队列中超过1个人就继续游戏
    while(this.queue.size >1){
      //模拟老师内心每次生成不同的数字
      let num = this._genRandomNum()
      for(let i=0;i<num;i++){
        //每次循环把开头一个同学放到末尾
        this.queue.enqueue(this.queue.dequeue())
      }
      //当循环结束时就把手里有花的同学淘汰掉
      eliminated = this.queue.dequeue()
      console.log(`${eliminated} 在击鼓传花游戏中被淘汰了!`)
    } 
    //游戏结束后获得胜利者
    return this.queue.front()
  }

  //模拟老师每次循环结束后生成不同数字
  _genRandomNum(){
    //要使用到lodash库
    const {random} = require('lodash')
    //随机生成一个1,10的数字
    return random(1,10)
  }

}

//玩击鼓传花
const nameList = ['john','xiaohua','xiaoming','jack','sanmao']
const winner = new HotPotato().play()
console.log(winner)

总结

今天我们讨论了数据结构之队列, 这个和编程语言无关, 是一种通用知识, 编程语言会过时, 但是数据结构是不会过时的, 顶多是实现方式的优化.