Implémenter un tampon en anneau de file d'attente circulaire en JavaScript

Circular Queue

Circular Queue est une structure de données linéaire, son fonctionnement est basé sur le principe FIFO (premier entré, premier sorti), et la dernière position est reconnectée à la première position, formant une boucle. On l'appelle également « tampon en anneau ».

L'un des avantages d'une file d'attente circulaire est que nous pouvons utiliser l'espace devant la file d'attente. Dans une file d'attente normale, une fois la file d'attente pleine, nous ne pouvons pas insérer l'élément suivant même s'il y a de l'espace devant la file d'attente. Mais en utilisant une file d'attente circulaire, nous pouvons utiliser l'espace pour stocker de nouvelles valeurs.

Problème

Nous devons concevoir l'implémentation d'une file d'attente circulaire en JavaScript pour prendre en charge les opérations suivantes :

• MyCircularQueue(k) - Constructeur, définit la taille de la file d'attente sur k.

• Front() - Récupère l'élément de premier plan de la file d'attente. Si la file d'attente est vide, -1 est renvoyé.

• Rear() - Récupère le dernier élément de la file d'attente. Si la file d'attente est vide, -1 est renvoyé.

• enQueue(value) - Insère un élément dans une file d'attente circulaire. Renvoie vrai si l'opération réussit.

• deQueue() - Supprime un élément d'une file d'attente circulaire. Renvoie vrai si l'opération réussit.

• isEmpty() - Vérifie si la file d'attente circulaire est vide.

• isFull() - Vérifiez si la file d'attente circulaire est pleine.

Exemple

Voici le code -

Démo

const CircularQueue = function(k) {
   this.size = k
   this.queue = []
   this.start1 = 0
   this.end1 = 0
   this.start2 = 0
   this.end2 = 0
}
CircularQueue.prototype.enQueue = function(value) {
   if(this.isFull()) {
      return false
   }
   if(this.end2 <= this.size - 1) {
      this.queue[this.end2++] = value
   } else {
      this.queue[this.end1++] = value
   }
   return true
}
CircularQueue.prototype.deQueue = function() {
   if(this.isEmpty()) {
      return false
   }
   if(this.queue[this.start2] !== undefined) {
      this.queue[this.start2++] = undefined
   } else {
      this.queue[this.start1++] = undefined
   }
   return true
}
CircularQueue.prototype.Front = function() {
   if(this.isEmpty()) {
      return -1
   }
   return this.queue[this.start2] === undefined ? this.queue[this.start1] :    this.queue[this.start2]
}
CircularQueue.prototype.Rear = function() {
   if(this.isEmpty()) {
      return -1
   }
   return this.queue[this.end1 - 1] === undefined ? this.queue[this.end2 - 1] :    this.queue[this.end1 - 1]
}
CircularQueue.prototype.isEmpty = function() {
   if(this.end2 - this.start2 + this.end1 - this.start1 <= 0) {
      return true
   }
   return false
}
CircularQueue.prototype.isFull = function() {
   if(this.end2 - this.start2 + this.end1 - this.start1 >= this.size) {
      return true
   }
   return false
}
const queue = new CircularQueue(2);
console.log(queue.enQueue(1));
console.log(queue.enQueue(2));
console.log(queue.enQueue(3));
console.log(queue.Rear());
console.log(queue.isFull());
console.log(queue.deQueue());
console.log(queue.enQueue(3));
console.log(queue.Rear());

Sortie

true
true
false
2
true
true
true
3

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!