数据结构与算法学习(五)队列

一.简述

队列(Queue)是一种运算受限的线性表,特性是先进先出(FIFO:First In First Out)。现实中存在的队列,就是在电影院的排队。

1.特点:

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

在这里插入图片描述
2.存在意义

CPU 资源是有限的,任务的处理速度与线程个数并不是线性正相关。相反,过多的线程反而会导致 CPU 频繁切换,处理性能下降。所以,线程池的大小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置的。

当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢?

其解决方式的底层数据结构就是队列。

若线程数没有到达核心线程数时,会创建一个线程。若达到了核心线程数,则将任务加入到任务队列。若到达核心线程数并且任务队列已满,但没有到达最大线程数,则会创建一个线程。若到达线程数并且任务队列已满,并且到达最大线程数,那么会执行拒绝策略。

3.队列在程序中的应用

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

二.队列的实现

队列的实现和栈一样,有两种方案:基于数组实现和基于链表实现。用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

对于栈来说,只需要一个栈顶指针就可以了。但是队列需要两个指针:一个是 head 指针,指向队头;一个是 tail 指针,指向队尾。

1.队列常见的操作

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

2.队列的数组实现

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

  // enqueue(item) 入队,将元素加入到队列中
  enqueue(item) {
    this.items.push(item);
  }

  // dequeue() 出队,从队列中删除队头元素,返回删除的那个元素
  dequeue() {
    return this.items.shift();
  }

  // front() 查看队列的队头元素
  front() {
    return this.items[0];
  }

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

  // size() 查看队列中元素的个数
  size() {
    return this.items.length;
  }

  // toString() 将队列中的元素以字符串形式返回
  toString() {
    let result = "";
    for (let item of this.items) {
      result += item + " ";
    }
    return result;
  }
}

3.测试代码

const queue = new Queue();

// enqueue() 测试
queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");
queue.enqueue("d");
console.log(queue.items); //--> ["a", "b", "c", "d"]

// dequeue() 测试
queue.dequeue();
queue.dequeue();
console.log(queue.items); //--> ["c", "d"]

// front() 测试
console.log(queue.front()); //--> c

// isEmpty() 测试
console.log(queue.isEmpty()); //--> false

// size() 测试
console.log(queue.size()); //--> 2

// toString() 测试
console.log(queue.toString()); //--> c d

三.队列的应用

使用队列实现小游戏:击鼓传花。

分析:传入一组数据集合和设定的数字 number,循环遍历数组内元素,遍历到的元素为指定数字 number 时将该元素删除,直至数组剩下一个元素。

// 利用队列结构的特点实现击鼓传花游戏求解方法的封装
function passGame(nameList, number) {
  // 1、new 一个 Queue 对象
  const queue = new Queue();

  // 2、将 nameList 里面的每一个元素入队
  for (const name of nameList) {
    queue.enqueue(name);
  }

  // 3、开始数数
  // 队列中只剩下 1 个元素时就停止数数
  while (queue.size() > 1) {
    // 不是 number 时,重新加入到队尾
    // 是 number 时,将其删除

    for (let i = 0; i < number - 1; i++) {
      // number 数字之前的人重新放入到队尾(即把队头删除的元素,重新加入到队列中)
      queue.enqueue(queue.dequeue());
    }

    // number 对应这个人,直接从队列中删除
    // 由于队列没有像数组一样的下标值不能直接取到某一元素,
    // 所以采用,把 number 前面的 number - 1 个元素先删除后添加到队列末尾,
    // 这样第 number 个元素就排到了队列的最前面,可以直接使用 dequeue 方法进行删除
    queue.dequeue();
  }

  // 4、获取最后剩下的那个人
  const endName = queue.front();

  // 5、返回这个人在原数组中对应的索引
  return nameList.indexOf(endName);
}


// passGame() 测试
const names = ["lily", "lucy", "tom", "tony", "jack"];
const targetIndex = passGame(names, 4);
console.log("击鼓传花", names[targetIndex]); //--> lily

四.优先队列

1.意义

排队中,有紧急情况(特殊情况)的人可优先处理。

2.重点

  • 每个元素不再只是一个数据,还包含优先级。
  • 在添加元素过程中,根据优先级放入到正确位置。

3.实现

// 优先队列内部的元素类
class QueueElement {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}

// 优先队列类(继承 Queue 类)
export class PriorityQueue extends Queue {
  constructor() {
    super();
  }

  // enqueue(element, priority) 入队,将元素按优先级加入到队列中
  // 重写 enqueue()
  enqueue(element, priority) {
    // 根据传入的元素,创建 QueueElement 对象
    const queueElement = new QueueElement(element, priority);

    // 判断队列是否为空
    if (this.isEmpty()) {
      // 如果为空,不用判断优先级,直接添加
      this.items.push(queueElement);
    } else {
      // 定义一个变量记录是否成功添加了新元素
      let added = false;

      for (let i = 0; i < this.items.length; i++) {
        // 让新插入的元素进行优先级比较,priority 值越小,优先级越大
        if (queueElement.priority < this.items[i].priority) {
          // 在指定的位置插入元素
          this.items.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }

      // 如果遍历完所有元素,优先级都大于新插入的元素,就将新插入的元素插入到最后
      if (!added) {
        this.items.push(queueElement);
      }
    }
  }

  // dequeue() 出队,从队列中删除前端元素,返回删除的元素
  // 继承 Queue 类的 dequeue()
  dequeue() {
    return super.dequeue();
  }

  // front() 查看队列的前端元素
  // 继承 Queue 类的 front()
  front() {
    return super.front();
  }

  // isEmpty() 查看队列是否为空
  // 继承 Queue 类的 isEmpty()
  isEmpty() {
    return super.isEmpty();
  }

  // size() 查看队列中元素的个数
  // 继承 Queue 类的 size()
  size() {
    return super.size();
  }

  // toString() 将队列中元素以字符串形式返回
  // 重写 toString()
  toString() {
    let result = "";
    for (let item of this.items) {
      result += item.element + "-" + item.priority + " ";
    }
    return result;
  }
}

4.使用

const priorityQueue = new PriorityQueue();

// 入队 enqueue()
priorityQueue.enqueue("A", 10);
priorityQueue.enqueue("B", 15);
priorityQueue.enqueue("C", 11);
priorityQueue.enqueue("D", 20);
priorityQueue.enqueue("E", 18);
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "A", priority: 10}
// QueueElement {element: "C", priority: 11}
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// 出队 dequeue()
priorityQueue.dequeue();
priorityQueue.dequeue();
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// isEmpty()
console.log(priorityQueue.isEmpty()); //--> false

// size()
console.log(priorityQueue.size()); //--> 3

// toString()
console.log(priorityQueue.toString()); //--> B-15 E-18 D-20