发布日期: 2022-07-01

队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的方法

enqueue(element):向队列尾部添加一个(或多个)新的项。
dequeue()︰移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front():返回队列中第一个元素__最先被添加，也将是最先被移除的元素。队列不做任何变动(不移除元素只返回元素信息-与Stack类的peek方法非常类似)。
isEmpty():如果队列中不包含任何元素，返回true，否则返回false。
size():返回队列包含的元素个数，与数组的length属性类似。
toString():将队列中的内容,转成字符串形式

队列的简单封装

// 队列的封装 先进先出 
function Queue (element) {
  // 属性
  this.items = []
  // 方法     
  // 1. 将元素加入队列
  Queue.prototype.enqueue = function (element) {
    this.items.push(element)
  }
  // 2. 从队列取出前端元素并删除
  Queue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 3. 查看一下前端元素
  Queue.prototype.front = function () {
    return this.items[0]
  }
  // 4. 判断队列是否为空
  Queue.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // 5. 获取队列中元素的个数
  Queue.prototype.size = function () {
    return this.items.length
  }
  // 6. toString 方法
  Queue.prototype.toString = function () {
    return this.items.join(' ')
  }
}

调用

let q = new Queue()
q.enqueue('地区乌当区')
q.enqueue('地区乌')
q.enqueue('地区乌23')
q.enqueue(123)
q.enqueue(1)
alert(q)
alert(q.dequeue())
alert(q.front())
alert(q.isEmpty())
alert(q.size())
alert(q.toString())

面试题 –> 击鼓传花

// 击鼓传花
  function passGame (nameList, num) {
    // 1. 创建一个队列
    let queue = new Queue()
    // 2. 把所有人依次添加到队列
    for (let i = 0; i < nameList.length; i++) {
      queue.enqueue(nameList[i])
    }
    /* 3. 开始数数字
          不是nam的时候,重新添加到队列的末尾
          是num数字的时候,将其在队列中删除
       3.1 num数字之前的重新放入到队列的末尾
    */
   while (queue.size() > 1) { 
    for (let i = 0; i < num - 1; i++) {
      queue.enqueue(queue.dequeue())
    }
    // 3.2 num对于的数字删除
    queue.dequeue()
   }
    // 4. 获取剩下的那个人
    // alert(queue.size())
    let endName = queue.front()
    alert('最后剩下的人是: ' + endName)
    return nameList.indexOf(endName)
  }
  let arr = ['Lily', 'Lucy', 'Tom', 'Lilei', 'Why']
  alert(passGame(arr, 3))

图解

在这里插入图片描述

优先队列的实现

// 封装优先级队列
function ProorityQueue () {
  // PriorityQueue里创建一个类: 内部类
  function QueueElement (element, priority) {
    this.element = element
    this.priority = priority
  }
  // 封装属性
  this.items = []

  ProorityQueue.prototype.enqueue = function (element, priority) {
    // 创建QueueElement对象
    let queueElement = new QueueElement(element, priority)
    // 数组没有元素时不用比较直接添加
    if (this.items.length === 0) {
      this.items.push(queueElement)
    } else {
      let added = false
      // 遍历元素进行比较
      for (let i = 0 ; i < this.items.length ; i++) {
        // 判断优先级
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement)
          added = true
          break;
        }
      }
      if (!added) {
        this.items.push(queueElement)
      }
    }
  }
  // 2. 从队列取出前端元素并删除
  ProorityQueue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 3. 查看一下前端元素
  ProorityQueue.prototype.front = function () {
    return this.items[0]
  }
  // 4. 判断队列是否为空
  ProorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // 5. 获取队列中元素的个数
  ProorityQueue.prototype.size = function () {
    return this.items.length
  }
  // 6. toString 方法
  ProorityQueue.prototype.toString = function () {
    // return this.items.join(' ')
    let str = ''
    this.items.forEach((item, i) => {
      str += item.element + ' ' + item.priority + '--  '
    })
    return str
  }
}