Implementieren Sie einen kreisförmigen Warteschlangenringpuffer in JavaScript

Circular Queue

Circular Queue ist eine lineare Datenstruktur, ihre Funktionsweise basiert auf dem FIFO-Prinzip (First In, First Out), und die letzte Position ist wieder mit der ersten Position verbunden und bildet eine Schleife. Er wird auch „Ringpuffer“ genannt.

Ein Vorteil einer kreisförmigen Warteschlange besteht darin, dass wir den Platz vor der Warteschlange nutzen können. Wenn in einer normalen Warteschlange die Warteschlange voll ist, können wir das nächste Element nicht einfügen, selbst wenn vor der Warteschlange Platz vorhanden ist. Mithilfe einer zirkulären Warteschlange können wir jedoch Speicherplatz zum Speichern neuer Werte nutzen.

Frage

Wir müssen die Implementierung einer zirkulären Warteschlange in JavaScript entwerfen, um die folgenden Operationen zu unterstützen:

• MyCircularQueue(k) – Konstruktor, legen Sie die Größe der Warteschlange auf k fest.

• Front() – Ruft das vordere Element aus der Warteschlange ab. Wenn die Warteschlange leer ist, wird -1 zurückgegeben.

• Rear() – Ruft das letzte Element aus der Warteschlange ab. Wenn die Warteschlange leer ist, wird -1 zurückgegeben.

• enQueue(value) – Ein Element in eine kreisförmige Warteschlange einfügen. Gibt true zurück, wenn der Vorgang erfolgreich ist.

• deQueue() – Entfernt ein Element aus einer kreisförmigen Warteschlange. Gibt true zurück, wenn der Vorgang erfolgreich ist.

• isEmpty() – Prüft, ob die Ringwarteschlange leer ist.

• isFull() – Überprüfen Sie, ob die Ringwarteschlange voll ist.

Beispiel

Hier ist der Code -

Demo

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());

Ausgabe

true
true
false
2
true
true
true
3

Das obige ist der detaillierte Inhalt vonImplementieren Sie einen kreisförmigen Warteschlangenringpuffer in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!