Explication détaillée de la façon d'implémenter la structure de file d'attente en JavaScript

Cet article vous amènera à comprendre la structure des données de file d'attente, à présenter en détail ses opérations et la méthode d'implémentation de la structure de file d'attente en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il sera utile à tout le monde.

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 est comme une file d'attente 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 de haut niveau, une file d'attente est une structure de données qui nous permet de traiter chaque élément de données dans l'ordre dans lequel il est stocké.

2. Opérations de file d'attente

La file d'attente prend en charge 2 opérations principales : mettre en file d'attente) et supprimer la file d'attente , il y a aussi un aperçu et opérations de longueur.

2.1 Opération de mise en file d'attente

L'opération de mise en file d'attente insère un élément à la fin de la file d'attente, ce qui en fait la fin de la file d'attente.

L'opération de jointure dans l'image ci-dessus insère 8 à la fin de la file d'attente, puis 8 devient la fin de la file d'attente.

queue.enqueue(8);

2.2 Opération de retrait de la file d'attente

L'opération de retrait de la file d'attente supprime le premier élément de la file d'attente et l'élément suivant de la file d'attente devient le leader de la file d'attente.

Dans l'image ci-dessus, l'opération de retrait de la file d'attente renvoie l'élément 7 et le supprime de la file d'attente. Après avoir quitté l'équipe, le projet 2 devient le nouveau chef d'équipe.

queue.dequeue(); // => 7

2.3 Opération Peek

L'opération Peek lit l'élément en tête de la file d'attente, mais ne modifie pas la file d'attente.

Sur la photo ci-dessus, 7 est le chef de l'équipe. L'opération peek renvoie uniquement la tête de file d'attente 7 mais ne modifie pas la file d'attente.

queue.peek(); // => 7

2.4 length

l'opération length renvoie le nombre d'éléments contenus dans la file d'attente.

La file d'attente dans l'image ci-dessus comporte 4 éléments : 4, 6, 2 et. 7. La longueur de la file d'attente résultante est 4.

queue.length; // => 4

2.5 Complexité temporelle des opérations de file d'attente

Points importants concernant toutes les opérations sur les files d'attente : la mise en file d'attente, le retrait de la file d'attente, le peek et la longueur doivent être exécutés avec une complexité temporelle constante O(1) .

Une complexité temporelle constante O(1) signifie que quelle que soit la taille de la file d'attente (qu'il y ait 10 ou 1 million d'éléments), ces opérations doivent être effectuées dans un temps relativement constant.

3. Utilisez JavaScript pour implémenter les files d'attente

Voyons comment implémenter la structure de données de file d'attente tout en garantissant que toutes les opérations doivent avoir une complexité temporelle constante 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() est l'instance qui crée la file d'attente. La méthode

queue.enqueue(7) stocke 7 dans la file d'attente.

queue.dequeue() supprime un élément principal de la file d'attente, tandis que queue.peek() lit uniquement l'élément principal de la file d'attente.

Le dernier Queue.Length indique combien d'éléments restent dans la file d'attente.

A propos de l'implémentation : Dans la classe Queue, l'objet ordinaire this.Items contient les éléments de la file d'attente par index numérique. L'index du premier élément de la file d'attente est suivi par Where.HeadInex, et l'index du dernier élément de la file d'attente est suivi par this.tailIndex.

La complexité des méthodes de file d'attente

existe dans les méthodes Queue queue(), dequeue(), peek() et length() :

• Accesseur de propriété (ex : this.items[this.headIndex]),
• Effectuer des opérations arithmétiques (ex : this.headidex++)

La complexité temporelle de ces méthodes est en temps constant O(1).

4. Résumé

Une file d'attente est une structure de données qui suit la règle du premier entré, premier sorti (FIFO).

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'aperçu et la longueur.

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

Défi : Améliorer les méthodes dequeue() et peek() pour générer une erreur lorsqu'elles sont exécutées sur une file d'attente vide.

Pour plus de connaissances liées à la programmation, veuillez visiter : Introduction à la programmation ! !

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!