Explication détaillée de la structure des données de file d'attente, comment l'implémenter en js ?

Être un excellent programmeur nécessite de vastes connaissances. La première chose est de comprendre le langage de programmation que vous avez choisi. Si vous lisez cet article, vous utilisez probablement JavaScript.

Cependant, après vous être familiarisé avec le langage de programmation, vous devez également comprendre comment manipuler les données facilement et efficacement en fonction de la tâche. C'est là qu'interviennent les structures de données.

Dans cet article, je décrirai la structure des données de file d'attente : quelles opérations elles ont et comment les implémenter en JavaScript.

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

Si vous aimez voyager, vous devez avoir suivi la procédure d'enregistrement des billets à la gare. Si beaucoup de gens veulent prendre un train, il est naturel qu'une file d'attente se forme. Les personnes qui viennent d’entrer dans la gare rejoignent la file d’attente. Les gens de l'autre côté qui venaient de passer le contrôle des billets sont sortis de la file d'attente. Ceci est un exemple de file d'attente et fonctionne de la même manière que la structure de données de file d'attente.

Une file d'attente est une structure de données qui suit la règle du premier entré, premier sorti (FIFO). Le premier élément à entrer dans la file d’attente (entrée) est le premier à sortir de la file d’attente (sortie).

La file d'attente a 2 pointeurs : la tête de file d'attente et la queue de file d'attente. Le premier élément à mettre en file d'attente est situé en avant de la file d'attente, tandis que le dernier élément à mettre en file d'attente est situé en queue de la file d'attente.

En repensant à l'exemple de la gare, la première personne à s'enregistrer est en tête de file d'attente. Les personnes qui viennent d’entrer dans la file d’attente se retrouvent en fin de file.

À un niveau élevé, une file d'attente est une structure de données qui vous permet de traiter des éléments en séquence.

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 sur la programmation, veuillez visiter : Vidéo de 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!