专栏首页前端鼓励师从 0 开始学习 JavaScript 数据结构与算法(四)队列

从 0 开始学习 JavaScript 数据结构与算法(四)队列

认识队列

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

受限之处:

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

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

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

image

队列图解

image

队列在程序中的应用

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

队列的实现

队列的实现和栈一样,有两种方案:

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

队列常见的操作

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

代码实现

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;
  }
}

测试代码

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

本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1],欢迎同学们 Star 和 Fork。

参考资料

[1]

GitHub 仓库: https://github.com/XPoet/js-data-structures-and-algorithms

专辑:

从 0 开始学习 JavaScript 数据结构与算法(一)前言

从 0 开始学习 JavaScript 数据结构与算法(二)数组

从 0 开始学习 JavaScript 数据结构与算法(三)栈

本文分享自微信公众号 - 前端鼓励师(FE-Cheerleaders),作者:XPoet

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从 0 开始学习 JavaScript 数据结构与算法(五)优先队列

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(三)栈

    数组是一个线性结构,并且可以在数组的任意位置插入和删除元素。但是有时候,我们为了实现某些功能,必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十一)树

    如图,树结构的组成方式类似于链表,都是由一个个节点连接构成。不过,根据每个父节点子节点数量的不同,每一个父节点需要的引用数量也不同。比如节点 A 需要 3 个引...

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十二)图

    在计算机程序设计中,图也是一种非常常见的数据结构,图论其实是一个非常大的话题,在数学上起源于哥尼斯堡七桥问题。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(八)集合

    几乎每种编程语言中,都有集合结构。集合比较常见的实现方式是哈希表,这里使用 JavaScript 的 Object 进行封装。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(九)字典

    本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1] 欢迎同学们 Star 和 Fork。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十)哈希表

    哈希表是一种非常重要的数据结构,几乎所有的编程语言都直接或者间接应用这种数据结构。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(六)单向链表

    单向链表类似于火车,有一个火车头,火车头会连接一个节点,节点上有乘客,并且这个节点会连接下一个节点,以此类推。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(七)双向链表

    本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1] 欢迎同学们 Star 和 Fork。

    XPoet
  • 从0开始的Python学习012数据结构&对象与类

    在Python中三种内建的数据结构--列表、元组和字典。学会了使用它们会使编程变得的简单。

    Happy、Liu
  • 数据结构与算法(四)| 队列、栈与Java集合

    比如,实现图的宽度优先遍历,但是要求用栈实现;实现图的深度优先遍历,但是要求用队列实现。

    行百里er
  • 重读《学习JavaScript数据结构与算法-第三版》- 第5章 队列

    本章为重读《学习JavaScript数据结构与算法-第三版》的系列文章,主要讲述队列数据结构、双端队列数据结构以及队列相关应用。

    胡哥有话说
  • 从简单的线性数据结构开始:栈与队列

    在计算机领域离不开算法和数据结构,而在数据结构中尤为重要与基础的便是两个线性数据结构:栈与队列,本文将简单的介绍栈(Stack)和队列(Queue)的实现。

    五分钟学算法
  • 数据结构与算法学习笔记之 从0编号的数组

    数组看似简单,但掌握精髓的却没有多少;他既是编程语言中的数据类型,又是最基础的数据结构;

    Dawnzhang
  • 01数据结构与算法总览_pythoner学习数据结构与算法系列

    可以简单理解为: 当一个一维的链表的分叉有两个的时候, 它就变成了一个二维的数据结构,相当于树结构

    诡途
  • 数据结构与算法学习笔记之先进先出的队列 数据结构与算法学习笔记之写链表代码的正确姿势(下)数据结构与算法学习笔记之 提高读取性能的链表(上)数据结构与算法学习笔记之 从0编号的数组数据结构与算法学

      队列是一种非常实用的数据结构,类似于生活中发排队,可应用于生活,开发中各个方面,比如共享打印机(先请求先打印),消息队列。你想知道他们是怎么工作的么。那就来...

    Dawnzhang
  • 前端学习数据结构与算法系列(一):初识数据结构与算法

    作为一个对算法没有任何认知,非科班出身的前端程序员,如果想提高自己的能力,不再只写业务代码当一个应用工程师,算法是必须掌握的一门本领。算法也是一种思想,当你去读...

    一只图雀
  • 【Java数据结构学习笔记之三】Java数据结构与算法之队列(Queue)实现

      本篇是数据结构与算法的第三篇,本篇我们将来了解一下知识点: 队列的抽象数据类型 顺序队列的设计与实现 链式队列的设计与实现 队列应用的简单举例 优先队列的设...

    Angel_Kitty
  • 前端学习数据结构与算法系列(三):栈与队列的基础知识

    何为栈?何为队列?先进先出和后进先出的区别,本文就跟大家分享下栈与队列这两种数据结构的优缺点以及适用场景,欢迎各位感兴趣的开发者阅读本文。

    一只图雀

扫码关注云+社区

领取腾讯云代金券