Implémentation de la file d'attente nodejs-Questions et réponses frontales-php.cn

Node.js est un environnement d'exécution JavaScript basé sur le moteur Chrome V8. Il adopte un modèle d'E/S non bloquant et piloté par les événements et est conçu pour améliorer l'évolutivité et les performances. Node.js est largement utilisé dans les serveurs Web et les outils de ligne de commande. Dans Node.js, une file d'attente est une structure de données commune qui traite les éléments selon le principe premier entré, premier sorti (FIFO). L'utilisation de files d'attente peut résoudre de nombreux problèmes pratiques, tels que la mise en cache, la planification des tâches, la livraison des messages, etc. Dans cet article, nous verrons comment implémenter des files d'attente dans Node.js.

Le principe de base d'une file d'attente est d'utiliser un tableau ou une liste chaînée comme conteneur et de conserver les pointeurs de tête et de queue de la file d'attente pour implémenter l'insertion et la suppression d'éléments. Les files d'attente sont divisées en files d'attente ordinaires et files d'attente prioritaires. Les éléments de la file d'attente ordinaire sont disposés dans l'ordre premier entré, premier sorti, tandis que les éléments de la file d'attente prioritaire sont disposés dans un certain ordre de priorité. Dans Node.js, nous pouvons utiliser des tableaux, des listes chaînées ou des boucles d'événements pour implémenter des files d'attente. Ci-dessous, nous présenterons respectivement leurs méthodes d'implémentation.

Utiliser des tableaux pour implémenter des files d'attente

L'utilisation de tableaux pour implémenter des files d'attente est le moyen le plus simple. En conservant un tableau d'éléments de stockage et un pointeur de tête de file d'attente, nous pouvons facilement implémenter des opérations de mise en file d'attente et de retrait. Voici un exemple de code de file d'attente basé sur l'implémentation d'un tableau :

class Queue {
  constructor() {
    this.array = [];
    this.head = 0;
  }
  
  enqueue(element) {
    this.array.push(element);
  }
  
  dequeue() {
    if (this.head < this.array.length) {
      const element = this.array[this.head];
      this.head++;
      return element;
    }
  }
  
  isEmpty() {
    return this.head >= this.array.length;
  }
}

Copier après la connexion

Dans le code ci-dessus, nous définissons une classe Queue pour représenter la file d'attente, où la variable array est utilisée pour stocker le tableau d'éléments, la variable head enregistre la position du pointeur de tête de file d'attente. La méthode enqueue est utilisée pour ajouter des éléments à la file d'attente, tandis que la méthode dequeue est utilisée pour supprimer un élément de la file d'attente et le renvoyer, et la méthode isEmpty est utilisée pour vérifiez si la file d'attente est vide. L'inconvénient de cette méthode est que lorsqu'il y a de nombreux éléments de file d'attente, le temps de fonctionnement de la file d'attente deviendra plus lent. Par conséquent, nous devons utiliser d’autres structures de données pour implémenter des files d’attente plus efficaces. Queue 类来表示队列，其中 array 变量用于存储元素数组，head 变量记录队头指针的位置。enqueue 方法用于将元素添加到队列中，而 dequeue 方法用于删除队列中的元素并返回它，isEmpty 方法则用于检查队列是否为空。该方式的缺点是，当队列元素很多时，队列的操作时间会变得较慢。因此，我们需要使用其他数据结构来实现更高效的队列。

使用链表实现队列

使用链表实现队列是一种更为高效的方式，它可以在入队和出队操作中达到 O(1) 的时间复杂度。下面是一个基于链表的队列代码示例：

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  enqueue(element) {
    const node = new Node(element);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
  }
  
  dequeue() {
    if (this.head) {
      const element = this.head.element;
      this.head = this.head.next;
      if (!this.head) {
        this.tail = null;
      }
      return element;
    }
  }
  
  isEmpty() {
    return !this.head;
  }
}

Copier après la connexion

上述代码中，我们定义了一个 Node 类来表示链表的节点，其中 element 变量用于存储元素的值，next 变量则用于指向下一个节点。我们使用 head 和 tail 来表示链表的头部和尾部节点，enqueue 方法用于将元素添加到队列尾部，而 dequeue 方法用于删除队列头部节点并返回它的元素，isEmpty 方法则检查队列是否为空。该方式的优点是入队和出队操作速度快，但消耗内存会较大。

使用事件循环实现队列

使用事件循环实现队列是一种全新的思路，它不需要维护数据结构，仅通过事件循环机制来实现队列的操作，从而使代码更为简洁。下面是一个基于事件循环实现的队列代码示例：

class Queue {
  constructor() {
    this.tasks = [];
    this.paused = false;
    this.running = false;
  }
  
  enqueue(task) {
    this.tasks.push(task);
    if (!this.paused && !this.running) {
      this.run();
    }
  }
  
  pause() {
    this.paused = true;
  }
  
  resume() {
    if (this.paused && !this.running) {
      this.paused = false;
      this.run();
    }
  }
  
  async run() {
    this.running = true;
    while (this.tasks.length > 0 && !this.paused) {
      const task = this.tasks.shift();
      await task();
    }
    this.running = false;
  }
  
  isEmpty() {
    return this.tasks.length == 0;
  }
}

Copier après la connexion

上述代码中，我们定义了一个 Queue 类来表示队列，其中 tasks 变量用于存储任务列表，paused 和 running 变量分别表示队列的暂停状态和运行状态。enqueue 方法用于添加任务到队列中，如果暂停状态已解除且队列未在运行中，则开始运行队列，pause 和 resume 方法用于开启和暂停队列，isEmpty 方法检查队列是否为空。run 方法则是使用事件循环机制来执行任务队列中的任务，具体实现就是在 while

L'utilisation d'une liste chaînée pour implémenter la file d'attente est un moyen plus efficace, qui peut atteindre une complexité temporelle O(1) dans les opérations de mise en file d'attente et de retrait de la file d'attente. Voici un exemple de code de file d'attente basé sur une liste chaînée :

Node

élément est utilisée pour stocker les éléments. La valeur de la variable <code>next

head

tail

enqueue

dequeue

isEmpty

Queue

tasks

paused

running

enqueue