数据结构——队列

一、什么是队列结构

队列结构（Queue）是另一种受限的数据结构，他是一种受限的线性表，先进先出(FIFO First In First Out)

• 只允许在表的前端（font）进行删除操作
• 在表的后端(rear)进行插入操作

图解：

二、队列结构的实现

队列的实现和栈一样，有两种方案：

• 基于数组实现
• 基于链表实现

/**
 * 封装一个队列类
*/

function Queue() {
  // 属性
  this.items = []

  // 元素进入队列
  Queue.prototype.enqueue = function (element) {
    this.items.push(element)
  }
  // 移除队列第一项，并返回数据
  Queue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 返回队列第一项数据
  Queue.prototype.front = function () {
    return this.items[0]
  }
  // 判断队列是否为空
  Queue.prototype.isEmpty = function () {
    return this.items.length == 0
  }
  // 返回队列的元个数
  Queue.prototype.size = function () {
    return this.items.length
  }
  // toString方法
  Queue.prototype.toString = function () {
    let str = ''
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + ' '
    }
    return str
  }

}

let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue)  // Queue { items: [ 'a', 'b', 'c', 'd' ] }
queue.dequeue()
queue.dequeue()
console.log(queue)  // Queue { items: [ 'c', 'd' ] }
console.log(queue.front())  // c
console.log(queue.isEmpty())  // false
console.log(queue.size())   // 2

三、面试题

击鼓传花的实现

/**
 * 一群人从一开始读到特定的数字淘汰，返回最后一个人
*/
function gameOut(nameList, num) {
  // 创建一个队列结构
  let queue = new Queue()
  // 将人添加到队列中
  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }
  while (queue.size() > 1) {
    // 开始数数字，不是对应数字则添加到队列末尾，是则移出队列
    for (let i = 0; i < num - 1; i++) {
      queue.enqueue(queue.dequeue())
    }
    queue.dequeue()
  }
  // 获取仅剩的人
  let successName = queue.front()
  return successName
}

console.log(gameOut(['张三', '李四', '王五'], 2)) // 王五
console.log(gameOut(['Monkey', 'Lucy', 'Tom', 'Lilei', 'Wang'], 3)) // Lilei

四、优先级队列

普通队列插入元素，数据会被放入后端，等待前端数据处理完毕才会处理

优先级队列插入元素会考虑数据的优先级，进行比较后会得出正确的位置

• 每个数据不仅仅是一个数据，还有数据的优先级
• 添加方式中，根据优先级将数据放入正确的位置

优先级队列的封装：

/**
 * 封装一个优先级队列，使用数字代表优先级
*/

// 规定数据越小，优先级越高
function PriorityQueue() {
  // 内部类，保存数据和优先级
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  // 使用属性保存数据
  this.items = []

  // 实现插入方法
  PriorityQueue.prototype.enqueue = function (element, priority) {
    // 创建QueueElement对象
    let queueElement = new QueueElement(element, priority)
    // 判断队列是否为空
    if (this.items.length == 0) {
      this.items.push(queueElement)
    } else { // 不为空，从最大优先级开始比较
      let flag = false
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement) // 前方插入
          flag = true
          break  // 跳出循环
        }
      }

      if (!flag) { // 比较完毕，优先级是最小的，直接放到最后
        this.items.push(queueElement)
      }
    }
  }

  // 移除队列第一项，并返回数据
  PriorityQueue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 返回队列第一项数据
  PriorityQueue.prototype.front = function () {
    return this.items[0]
  }
  // 判断队列是否为空
  PriorityQueue.prototype.isEmpty = function () {
    return this.items.length == 0
  }
  // 返回队列的元个数
  PriorityQueue.prototype.size = function () {
    return this.items.length
  }
  // toString方法
  PriorityQueue.prototype.toString = function () {
    let str = ''
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i].element + ':' + this.items[i].priority + ' '
    }
    return str
  }
}

let pq = new PriorityQueue()
pq.enqueue('吃饭', 10)
pq.enqueue('睡觉', 50)
pq.enqueue('打游戏', 100)
pq.enqueue('学习', 1)
console.log(pq.toString())  // 学习:1 吃饭:10 睡觉:50 打游戏:100