队列简介

队列是是一种受限的线性表，特点为先进先出（FIFO：first in first out）。

  • 受限之处在于它只允许在表的前端（front）进行删除操作；
  • 在表的后端（rear）进行插入操作；

image-20200707202837579

相当于排队买票，先来的先买票，后来的后买票。

image-20200707202850483

队列的应用：

  • 打印队列：计算机打印多个文件的时候，需要排队打印；
  • 线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待CPU处理；

队列类的实现：

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

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

队列的常见操作：

  • enqueue(element)：向队列尾部添加一个（或多个）新的项。

    dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。

    front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。

    isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。

    size()：返回队列包含的元素个数，与数组的length属性类似。

封装队列类

使用ES5实现

测试代码：

// 创建队列
let queue = new  Queue()

// 将元素加入到队列中
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue);												
// 从队列中删除元素
queue.dequeue()
console.log(queue);												
queue.dequeue()
console.log(queue);												

//front
console.log(queue.front());								 	

// 验证其他方法
console.log(queue.isEmpty());
console.log(queue.size());
console.log(queue.toString());

测试结果：

image-20200707203038195

使用ES6实现

export class Queue {
  constructor () {
    this.items = []
  }

  enqueue (element) {
    this.items.push(element)
  }

  dequeue () {
    return this.items.shift()
  }

  front () {
    if (this.items.length === 0) return null
    return this.items[0]
  }

  isEmpty () {
    return this.items.length === 0
  }
  
  size () {
    return this.items.length
  }
}

优先级队列

优先级队列的特点

  • 我们知道, 普通的队列插入一个元素, 数据会被放在后端. 并且需要前面所有的元素都处理完成后才会处理前面的数据.
  • 但是优先级队列, 在插入一个元素的时候会考虑该数据的优先级.(和其他数据优先级进行比较)
  • 比较完成后, 可以得出这个元素正确的队列中的位置. 其他处理方式, 和队列的处理方式一样.
  • 也就是说, 如果我们要实现优先级队列, 最主要是要修改添加方法. (当然, 还需要以某种方式来保存元素的优先级)

优先级队列应用

  • 一个现实的例子就是机场登机的顺序
    • 头等舱和商务舱乘客的优先级要高于经济舱乘客。
    • 在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级。
  • 另一个现实中的例子是医院的（急诊科）候诊室。
    • 医生会优先处理病情比较严重的患者。
    • 通常，护士会鉴别分类，根据患者病情的严重程度放号。
  • 计算机中, 我们也可以通过优先级队列来重新排序队列中任务的顺序
    • 比如每个线程处理的任务重要性不同, 我们可以通过优先级的大小, 来决定该线程在队列中被处理的次序.

实现优先级队列主要考虑的问题

    1. 封装元素和优先级放在一起(可以封装一个新的构造函数)
    1. 添加元素时, 将当前的优先级和队列中已经存在的元素优先级进行比较, 以获得自己正确的位置.

使用ES5实现

// 封装优先级队列
function PriorityQueue() {

  //内部类：在类里面再封装一个类;表示带优先级的数据
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  } 

  // 封装属性
  this.items = []

  // 1.实现按照优先级插入方法
  PriorityQueue.prototype.enqueue = (element, priority) => {
    // 1.1.创建QueueElement对象
    let queueElement = new QueueElement(element, priority)

    // 1.2.判断队列是否为空
    if(this.items.length == 0){
      this.items.push(queueElement)
    }else{
      // 定义一个变量记录是否成功添加了新元素
      let added = false
      for(let i of this.items){
        // 让新插入的元素与原有元素进行优先级比较(priority越小，优先级越大)
        if(queueElement.priority < i.priority){
          this.items.splice(i, 0, queueElement)
          added = true
          // 新元素已经找到插入位置了可以使用break停止循环
          break
        }
      }
      // 新元素没有成功插入，就把它放在队列的最前面
      if(!added){
        this.items.push(queueElement)
      }
    }
  }

  // 2.dequeue():从队列中删除前端元素
  PriorityQueue.prototype.dequeue = () => {
    return this.items.shift()
  }

  // 3.front():查看前端的元素
  PriorityQueue.prototype.front = () => {
    return this.items[0]
  }

  // 4.isEmpty():查看队列是否为空
  PriorityQueue.prototype.isEmpty = () => {
    return this.items.length == 0;
  }

  // 5.size():查看队列中元素的个数
  PriorityQueue.prototype.size = () => {
    return this.items.length
  }

  // 6.toString():以字符串形式输出队列中的元素
  PriorityQueue.prototype.toString = () => {
    let resultString = ''
      for (let i of this.items){
        resultString += i.element + '-' + i.priority + ' '
      }
      return resultString
    }
}

测试代码：

// 测试代码
let pq = new PriorityQueue();
pq.enqueue('Tom',111);
pq.enqueue('Hellen',200);
pq.enqueue('Mary',30);
pq.enqueue('Gogo',27);
// 打印修改过后的优先队列对象
console.log(pq);

测试结果：

image-20200707203321036

使用ES6实现

继承自上面的队列即可，部分方法重新封装

class QueueElement {
  constructor (element,priority) {
    this.element = element;
    this.priority = priority
  }
}

export class PriorityQueue extends Queue {
  enqueue (element, priority) {
    const 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++) {
        const element = this.items[i];
        if (element.priority > queueElement.priority) {
          this.items.splice(i, 0, queueElement)
          added = false
          break
        }
      }
      if (!added) {
        this.items.push(queueElement)
      }
    }
  }
}

代码解析

  • 封装了一个QueueElement, 将element和priority封装在一起.
  • 在插入新的元素时, 有如下情况下考虑:
    • 根据新的元素先创建一个新的QueueElement对象.
    • 如果元素是第一个被加进来的, 那么不需要考虑太多, 直接加入数组中即可.
    • 如果是后面加进来的元素, 需要和前面加进来的元素依次对比优先级.
    • 一旦优先级, 大于某个元素, 就将该元素插入到元素这个元素的位置. 其他元素会依次向后移动.
    • 如果遍历了所有的元素, 没有找到某个元素被这个新元素的优先级低, 直接放在最后即可.

队列的应用(击鼓传花)

使用队列实现小游戏：击鼓传花，传入一组数据和设定的数字num，循环遍历数组内元素，遍历到的元素为指定数字num时将该元素删除，直至数组剩下一个元素。

击鼓传花的规则

  • 原游戏规则:
    • 班级中玩一个游戏, 所有学生围成一圈, 从某位同学手里开始向旁边的同学传一束花.
    • 这个时候某个人(比如班长), 在击鼓, 鼓声停下的一颗, 花落在谁手里, 谁就出来表演节目.
  • 修改游戏规则:
    • 我们来修改一下这个游戏规则.
    • 几个朋友一起玩一个游戏, 围成一圈, 开始数数, 数到某个数字的人自动淘汰.
    • 最后剩下的这个人会获得胜利, 请问最后剩下的是原来在哪一个位置上的人?

代码实现

function passGame (nameList, num) {
  const queue = new Queue()
  for (let i = 0; i < nameList.length; i++) {
    const element = nameList[i];
    queue.enqueue(element)
  }
  while (queue.size() > 1 ) {
    for (let i = 1; i < num - 1; i++) {
      queue.enqueue(queue.dequeue())
    }
    queue.dequeue()
  }
  return queue.front()
}

详解：

// 队列应用：面试题：击鼓传花
let passGame = (nameList, num) => {
  //1.创建队列结构
  let queue = new Queue()
  //2.将所有人依次加入队列
  // 这是ES6的for循环写法，i相当于nameList[i]
  for(let i of nameList){
    queue.enqueue(i)
  }
  
  // 3.开始数数
 while(queue.size() > 1){//队列中只剩1个人就停止数数
  // 不是num的时候，重新加入队列末尾
  // 是num的时候，将其从队列中删除
  // 3.1.num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后)
  for(let i = 0; i< num-1; i++ ){
    queue.enqueue(queue.dequeue())
  }
  // 3.2.num对应这个人，直接从队列中删除
  /*
    思路是这样的，由于队列没有像数组一样的下标值不能直接取到某一元素，所以采用，把num前面的num-1个元素先删除后添加到队列末尾，这样第num个元素就排到了队列的最前面，可以直接使用dequeue方法进行删除
  */
  queue.dequeue()
 }

  //4.获取剩下的那个人
  console.log(queue.size());									
  let endName = queue.front()
  console.log('最终剩下的人：' + endName);						   	
  
  return nameList.indexOf(endName);
}

//5.测试击鼓传花
let names = ['lily', 'lucy', 'Tom', 'Lilei', 'Tony']
console.log(passGame(names, 3));

图解

image-20200707204152363

注意点

关于数组方法splice用法：

  • splice（1，0，’Tom’）：表示在索引为1的元素前面插入元素’Tom‘（也可以理解为从索引为1的元素开始删除，删除0个元素，再在索引为1的元素前面添加元素’Tom’）；
  • splice（1，1，’Tom’）：表示从索引为1的元素开始删除（包括索引为1的元素），共删除1个元素，并添加元素’Tom’。即把索引为1的元素替换为元素’Tom’。

数组的push方法在数组、栈和队列中的形式：

  • 数组：在数组[0，1，2]中，pop(3)，结果为[0，1，2，3]；
  • 栈：执行pop(0)，pop(1)，pop(2)，pop(3)，从栈底到栈顶的元素分别为：0，1，2，3；如果看成数组，可写为[0，1，2，3]，但是索引为3的元素3其实是栈顶元素；所以说栈的push方法是向栈顶添加元素（但在数组的视角下为向数组尾部添加元素）；
  • 队列：enqueue方法可以由数组的push方法实现，与数组相同，相当于在数组尾部添加元素。

可以这样想：栈结构是头朝下（索引值由下往上增大）的数组结构。

image-20200707203728995