JavaScript 数据结构与算法（四）队列结构

认识队列

队列（Queue）是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)

受限之处：

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

生活中类似队列结构的场景：

  • 排队，比如在电影院，商场，甚至是厕所排队。
  • 优先排队的人，优先处理。 (买票、结账、WC)。

04_JavaScript数据结构与算法（四）队列 - 图1

队列图解

04_JavaScript数据结构与算法（四）队列 - 图2

队列在程序中的应用

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

队列的实现

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

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

队列常见的操作

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

代码实现

  1. class Queue {
  3.   constructor() {
  4.     this.items = [];
  5.   }
  7.   // enqueue(item) 入队，将元素加入到队列中
  8.   enqueue(item) {
  9.     this.items.push(item);
  10.   }
  12.   // dequeue() 出队，从队列中删除队头元素，返回删除的那个元素
  13.   dequeue() {
  14.     return this.items.shift();
  15.   }
  17.   // front() 查看队列的队头元素
  18.   front() {
  19.     return this.items[0];
  20.   }
  22.   // isEmpty() 查看队列是否为空
  23.   isEmpty() {
  24.     return this.items.length === 0;
  25.   }
  27.   // size() 查看队列中元素的个数
  28.   size() {
  29.     return this.items.length;
  30.   }
  32.   // toString() 将队列中的元素以字符串形式返回
  33.   toString() {
  34.     let result = '';
  35.     for (let item of this.items) {
  36.       result += item + ' ';
  37.     }
  38.     return result;
  39.   }
  40. }

测试代码

  1. const queue = new Queue();
  3. // enqueue() 测试
  4. queue.enqueue('a');
  5. queue.enqueue('b');
  6. queue.enqueue('c');
  7. queue.enqueue('d');
  8. console.log(queue.items); //--> ["a", "b", "c", "d"]
  10. // dequeue() 测试
  11. queue.dequeue();
  12. queue.dequeue();
  13. console.log(queue.items); //--> ["c", "d"]
  15. // front() 测试
  16. console.log(queue.front()); //--> c
  18. // isEmpty() 测试
  19. console.log(queue.isEmpty()); //--> false
  21. // size() 测试
  22. console.log(queue.size()); //--> 2
  24. // toString() 测试
  25. console.log(queue.toString()); //--> c d

队列的应用

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

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

代码实现

  1. // 利用队列结构的特点实现击鼓传花游戏求解方法的封装
  2. function passGame(nameList, number) {
  3.   // 1、new 一个 Queue 对象
  4.   const queue = new Queue();
  6.   // 2、将 nameList 里面的每一个元素入队
  7.   for (const name of nameList) {
  8.     queue.enqueue(name);
  9.   }
  11.   // 3、开始数数
  12.   // 队列中只剩下 1 个元素时就停止数数
  13.   while (queue.size() > 1) {
  14.     // 不是 number 时，重新加入到队尾
  15.     // 是 number 时，将其删除
  17.     for (let i = 0; i < number - 1; i++) {
  18.       // number 数字之前的人重新放入到队尾（即把队头删除的元素，重新加入到队列中）
  19.       queue.enqueue(queue.dequeue());
  20.     }
  22.     // number 对应这个人，直接从队列中删除
  23.     // 由于队列没有像数组一样的下标值不能直接取到某一元素，
  24.     // 所以采用，把 number 前面的 number - 1 个元素先删除后添加到队列末尾，
  25.     // 这样第 number 个元素就排到了队列的最前面，可以直接使用 dequeue 方法进行删除
  26.     queue.dequeue();
  27.   }
  29.   // 4、获取最后剩下的那个人
  30.   const endName = queue.front();
  32.   // 5、返回这个人在原数组中对应的索引
  33.   return nameList.indexOf(endName);
  34. }

测试代码

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