JS中的算法与数据结构之队列(Queue)实例详解

JS中的算法与数据结构之队列(Queue)实例详解

什么是队列?

队列是一种线性数据结构,它是一种先进先出的数据结构(FIFO),即最先进队列的元素也最先出队列。

队列有两个基本操作:入队和出队。入队将元素添加到队列的末尾,而出队则是从队列的前端删除元素。

队列的实现方式

我们可以用数组和链表来实现队列,这里我们介绍一下使用数组来实现队列的方式。

用数组实现队列

我们可以在数组的末尾添加元素,从数组头部删除元素。当元素出队列时,我们可以将数组的第一个元素删除。这个过程可以用 shift 方法来实现,而入队操作可以使用 push 方法来往数组的末尾添加元素。

下面是一个使用数组实现队列的示例:

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

  enqueue(item) {
    this.items.push(item);
  }

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

以上代码中,我们定义了一个 Queue 类作为队列的实现,该类的构造函数里定义了一个 items 数组,这个数组存储着队列的元素。

我们使用 enqueue 方法将元素添加到数组的末尾,使用 dequeue 方法从数组的头部删除元素。

用链表实现队列

链表与数组不同,它们没有固定的大小。我们可以使用一个包含 valuenext 属性的节点来实现链表队列。

下面是一个使用链表实现队列的示例:

class QueueNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(item) {
    const node = new QueueNode(item);

    if (this.tail) {
      this.tail.next = node;
    } else {
      this.head = node;
    }

    this.tail = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return null;

    const item = this.head.value;

    if (this.head === this.tail) {
      this.tail = null;
    }

    this.head = this.head.next;
    this.length--;

    return item;
  }
}

以上代码中,我们定义了 QueueNode 类作为队列链表节点的实现,该类包含 valuenext 属性,分别对应节点的值和下一个节点。

Queue 类定义了队列链表的实现,其中的 headtail 属性分别表示队列的头节点和尾节点。我们使用 enqueue 方法向队列中添加元素,使用 dequeue 方法从队列中删除元素。

队列的应用场景

队列广泛应用于计算机科学和实际生活中诸如广告投放、大数据处理和操作系统等领域。以下是两种队列的应用场景的示例。

打印队列

考虑一个使用打印机的场景。多个人可以向打印队列中提交打印任务,队列会逐个打印所有的任务。这时我们可以使用队列来实现打印任务的队列,先进先出。

class PrintQueue {
  constructor() {
    this.queue = new Queue();
    this.timer = null;
    this.delay = 5000;
  }

  enqueue(item) {
    this.queue.enqueue(item);

    if (!this.timer) {
      this.timer = setTimeout(() => this.print(), this.delay);
    }
  }

  dequeue() {
    return this.queue.dequeue();
  }

  print() {
    if (!this.queue.length) {
      clearTimeout(this.timer);
      this.timer = null;
    } else {
      const item = this.queue.dequeue();
      console.log(`Printing ${item}...`);
      setTimeout(() => this.print(), this.delay);
    }
  }
}

const printQueue = new PrintQueue();
printQueue.enqueue("Document A");
printQueue.enqueue("Document B");

以上代码中,我们定义了一个 PrintQueue 类作为打印队列的实现,该类包含了一个队列和一个打印计时器。进入队列的任务将以先进先出的方式进行打印。

更长时间的排队队列

在很多场景中,用户在排队时可能需要等待较长时间。这里我们可以使用队列来管理排队用户。当排队人数超过一个给定的限制时,我们可以向队列中添加一个状态为等待的用户。当一个用户完成服务时,我们可以处于等待状态的用户中取出一个进行服务。

class WaitQueue {
  constructor(limit) {
    this.queue = new Queue();
    this.limit = limit;
  }

  push(item) {
    if (this.queue.length >= this.limit) return false;

    this.queue.enqueue(item);
    return true;
  }

  pop() {
    return this.queue.dequeue();
  }
}

const waitQueue = new WaitQueue(3);
waitQueue.push("User A");
waitQueue.push("User B");
waitQueue.push("User C");
waitQueue.push("User D"); // 队列已满,无法添加

console.log(waitQueue.pop()); // User A
console.log(waitQueue.pop()); // User B
console.log(waitQueue.pop()); // User C

以上代码中,我们定义了一个 WaitQueue 类作为排队队列的实现,该类有一个 limit 属性限制该队列长度。可以使用 push 方法向队列中添加元素,当队列已满时,将无法添加新元素。可以使用 pop 方法从队列中删除元素,这个队列遵循先进先出的原则。

总结

队列是一种先进先出的线性数据结构,适合于任务管理和排队等业务场景。在 JavaScript 中,我们可以使用数组或链表来实现队列。

以上是我对“JS中的算法与数据结构之队列(Queue)实例详解”的完整攻略,包括队列的实现方式、应用场景和示例说明。感谢阅读!

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:JS中的算法与数据结构之队列(Queue)实例详解 - Python技术站

(0)
上一篇 2023年5月27日
下一篇 2023年5月27日

相关文章

  • php正则表达式基本知识与应用详解【经典教程】

    “PHP正则表达式基本知识与应用详解【经典教程】”是一篇关于PHP正则表达式的详细讲解文章,包含了从正则表达式基础知识到应用实例的全面介绍。 一、正则表达式基础知识 文章首先详细介绍了正则表达式的基础知识,包括元字符、定界符、字符集、量词等内容。针对每个知识点,作者都进行了详细的讲解并给出了示例说明。 例如,对于元字符一节,作者列出了常见的元字符,并给出了它…

    JavaScript 2023年6月10日
    00
  • 解决微信二次分享不显示摘要和图片的问题

    让微信二次分享能够正确显示摘要和图片,需要在网页head部分添加相关的meta标签。以下是具体的步骤: 在head部分添加以下meta标签: <meta property="og:title" content="网页标题"/> <meta property="og:description&q…

    JavaScript 2023年6月11日
    00
  • jquery ajax post提交数据乱码

    下面是详细的攻略: 一、问题描述 当使用 jQuery 的 AJAX 功能来提交表单数据时,有时会出现提交的中文乱码的问题。问题表现为:在后台处理接收到的数据的时候,中文字符会被解析为乱码,这给我们的开发和调试带来了不必要的麻烦。 二、问题分析 出现该问题的原因是因为,提交数据时如果没有指定编码方式,浏览器会使用当前页面的默认编码方式,而当前页面的编码方式不…

    JavaScript 2023年5月19日
    00
  • JS实现时间校验的代码

    以下是使用JavaScript实现时间校验的完整攻略: 步骤一:获取当前时间 首先,需要获取当前时间以供后续校验。使用JavaScript中的 Date() 函数可以获取当前时间。 const currentDate = new Date(); 步骤二:设置有效时间段 根据业务需求,需要设置一个有效时间段。使用JavaScript的 Date() 函数,可以…

    JavaScript 2023年5月27日
    00
  • JavaScript 数据结构之集合创建(2)

    让我们来详细讲解一下“JavaScript 数据结构之集合创建(2)”的完整攻略。 一、什么是集合? 集合是一种数据结构,用于存储一组不重复的元素。集合可以使用数组或对象实现,但是使用数组的方式会占用更多内存,因为数组需要存储每个元素的值和索引。 二、如何创建集合? 在JavaScript中,可以使用对象表示集合。每个键(key)都是集合中的一个元素,并且每…

    JavaScript 2023年5月28日
    00
  • JavaScript实现页面无缝滚动效果

    下面是我总结的“JavaScript实现页面无缝滚动效果”的完整攻略。 前置知识 在学习“JavaScript实现页面无缝滚动效果”之前,需要先了解一些基础知识,包括: HTML基础知识:HTML文档的结构、基本标签的使用等。 CSS基础知识:CSS样式基础语法、布局、盒模型等。 JavaScript基础知识:变量、函数、循环、条件语句等。 实现思路 在实现…

    JavaScript 2023年6月11日
    00
  • JavaScript对象封装的简单实现方法(3种方法)

    下面将详细讲解“JavaScript对象封装的简单实现方法(3种方法)”的完整攻略。 什么是JavaScript对象封装? JavaScript对象封装是指使用面向对象编程的思想,将数据和方法封装在一起,通过暴露公共方法的方式来实现数据的访问和操作保护。 实现JavaScript对象封装的三种方法 1. 利用构造函数实现对象封装 构造函数是一种用于创建对象的…

    JavaScript 2023年5月27日
    00
  • js几个不错的函数 $$()

    当我们在操作 DOM 元素时,选择器是一个非常重要的部分。虽然在实现选择器时,使用 querySelector() 和 querySelectorAll() 不是最佳选择,但它们确实是使用最频繁的选择器。 然而,现在有一个新兴的 DOM 选择器,即 $$() 函数,它是一个 querySelectorAll() 的别名。虽然在一些场景下不如 querySel…

    JavaScript 2023年5月27日
    00
合作推广
合作推广
分享本页
返回顶部