Illustrations détaillées et exemples d'implémentation de files d'attente en JavaScript

Cet article vous apporte des connaissances pertinentes sur javascript Il présente principalement les problèmes liés à l'implémentation des files d'attente en JavaScript, décrit la structure des données de file d'attente, ses opérations et montre l'implémentation de la file d'attente en JavaScript. J'espère qu'il sera utile à tout le monde. .

Recommandations associées : Tutoriel Javascript

1. Structure de données de file d'attente

• La file d'attente est un type de structure de données « premier entré, premier sorti » (FIFO). Le premier élément mis en file d'attente (entrée) est le premier retiré de la file d'attente (sortie).
• La file d'attente comporte 2 pointeurs : tête et queue. L'élément en file d'attente le plus ancien se trouve en tête et le plus récent en queue.
• La file d'attente, c'est comme nous faisant la queue dans le métro. Les passagers près de la porte sont en tête de file, et les passagers qui viennent d'entrer dans la file d'attente sont au fond de la file.

D'un point de vue supérieur, une file d'attente est une structure de données qui nous permet de traiter chaque élément de données en séquence dans l'ordre dans lequel il est stocké.

2. Opérations sur la file d'attente

La file d'attente prend en charge 2 opérations principales : mettre en file d'attente et retirer la file d'attente. De plus, il peut s'avérer utile d'effectuer des opérations d'aperçu et de longueur sur la file d'attente.

• Opération de mise en file d'attente
  L'opération de mise en file d'attente consiste à insérer un élément à la fin de la file d'attente, et l'élément inséré devient la fin de la file d'attente.

L'opération de mise en file d'attente dans l'image ci-dessus insère l'élément 8 dans la queue, et 8 devient la queue de la file d'attente.

queue.enqueue(8);

• Opération de retrait de file d'attente
  L'opération de retrait de file d'attente consiste à extraire l'élément au début de la file d'attente, et l'élément suivant dans la file d'attente devient l'élément de tête.

Dans l'image ci-dessus, l'opération de sortie de file d'attente renvoie et supprime l'élément 7 de la file d'attente. Après la sortie de la file d'attente, l'élément 2 devient le nouvel élément principal.

queue.dequeue(); // => 7

• Opérations d'inspection
  Les opérations d'inspection lisent le début de la file d'attente sans modifier la file d'attente.

L'élément 7 est le début de la file d'attente dans l'image ci-dessus, et l'opération d'inspection ne renvoie que l'en-tête (élément) 7 sans modifier la file d'attente.

queue.peek(); // => 7

• Longueur de la file d'attente
  L'opération de longueur calcule le nombre d'éléments que contient la file d'attente.

Il y a 4 éléments dans la file d'attente sur l'image : 4, 6, 2 et 7. Par conséquent, la longueur de la file d'attente est de 4.

queue.length; // => 4

• Complexité temporelle des opérations de file d'attente
  Il est important de noter que pour toutes les opérations de file d'attente (Mise en file d'attente, Retirer la file d'attente, Afficher et Longueur), toutes ces opérations doivent exécuter O(1) à un temps fixe.

Le temps constant O(1) signifie que quelle que soit la taille de la file d'attente (elle peut contenir 10 ou 1 million d'éléments) : les opérations de mise en file d'attente, de retrait de la file d'attente, de coup d'oeil et de longueur doivent toutes être effectuées simultanément.

3. Implémentation de files d'attente en JavaScript

Examinons une implémentation possible d'une structure de données de file d'attente tout en conservant l'exigence selon laquelle toutes les opérations doivent être effectuées en temps constant O(1).

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  get length() {
    return this.tailIndex - this.headIndex;
  }
}

const queue = new Queue();

queue.enqueue(7);
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(4);

queue.dequeue(); // => 7

queue.peek();    // => 2

queue.length;    // => 3

const queue = new Queue() explique comment créer une instance de file d'attente.

Appelez la méthode queue.enqueue(7) pour mettre l'élément 7 dans la file d'attente.

queue.dequeue() supprime un élément principal de la file d'attente, tandis que queue.peek() le vérifie simplement depuis le début.

Enfin, queue.length indique combien d'éléments restent dans la file d'attente.

À propos de l'implémentation : à l'intérieur de la classe Queue, l'objet simple this.items contient les éléments de la file d'attente par index numérique. L'index de l'élément de tête est suivi par this.headIndex, et l'index de l'élément de queue est suivi par this.tailIndex.

• Complexité des méthodes de file d'attente

Les méthodes queue(), dequeue(), peek() et length() de la classe Queue utilisent uniquement :

属性访问（例如this.items[this.headIndex]），

或执行算术操作（例如this.headIndex++）

Par conséquent, la complexité temporelle de ces méthodes est en temps constant O( 1).

4. Résumé

La structure de données de la file d'attente est un type de « premier entré, premier sorti » (FIFO) : le premier élément mis en file d'attente est le premier élément retiré de la file d'attente.

La file d'attente a 2 opérations principales : mettre en file d'attente et retirer la file d'attente. De plus, les files d'attente peuvent avoir des opérations auxiliaires telles que l'affichage et la longueur.

Toutes les opérations de file d'attente doivent exécuter O(1) en temps constant.

Recommandations associées : Tutoriel d'apprentissage Javascript

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!