Dieser Artikel vermittelt Ihnen relevantes Wissen über Javascript. Er stellt hauptsächlich Probleme im Zusammenhang mit der Implementierung von Warteschlangen in JavaScript vor, beschreibt die Warteschlangendatenstruktur und ihre Operationen und zeigt die Warteschlangenimplementierung in JavaScript. .
Verwandte Empfehlungen: Javascript-Tutorial
Aus einer höheren Perspektive ist eine Warteschlange eine Datenstruktur, die es uns ermöglicht, jedes Datenelement der Reihe nach in der Reihenfolge zu verarbeiten, in der es gespeichert ist.
Die Warteschlange unterstützt zwei Hauptoperationen: Einreihen und Entfernen aus der Warteschlange. Darüber hinaus kann es hilfreich sein, Peek- und Längenoperationen für die Warteschlange durchzuführen.
Der Enqueue-Vorgang im obigen Bild fügt Element 8 am Ende der Warteschlange ein und 8 wird zum Ende der Warteschlange.
queue.enqueue(8);
Im Bild oben kehrt der Vorgang zum Entfernen aus der Warteschlange zurück und entfernt das Element 7 aus der Warteschlange. Nach dem Entfernen aus der Warteschlange wird Element 2 zum neuen Hauptelement.
queue.dequeue(); // => 7
Element 7 ist der Anfang der Warteschlange im Bild oben, und der Inspektionsvorgang gibt nur Header (Element) 7 zurück, ohne die Warteschlange zu ändern.
queue.peek(); // => 7
In der Warteschlange im Bild befinden sich 4 Elemente: 4, 6, 2 und 7. Daher beträgt die Warteschlangenlänge 4.
queue.length; // => 4
Konstante Zeit O(1) bedeutet, dass unabhängig von der Warteschlangengröße (sie kann 10 oder 1 Million Elemente haben): Enqueue-, Dequeue-, Peek- und Längenoperationen alle gleichzeitig ausgeführt werden müssen.
Sehen wir uns eine mögliche Implementierung einer Warteschlangendatenstruktur an, wobei die Anforderung beibehalten wird, dass alle Operationen in konstanter Zeit O(1) ausgeführt werden müssen. Mit
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; // => 3const queue = new Queue() wird eine Instanz einer Warteschlange erstellt.
Rufen Sie die Methode queue.enqueue(7) auf, um Element 7 in die Warteschlange zu stellen.
queue.dequeue() entfernt ein Kopfelement aus der Warteschlange, während queue.peek() es nur von Anfang an überprüft.
Schließlich zeigt queue.length an, wie viele Elemente noch in der Warteschlange sind.
Über die Implementierung: Innerhalb der Queue-Klasse speichert das einfache Objekt this.items die Elemente in der Warteschlange nach numerischem Index. Der Index des Kopfelements wird von this.headIndex verfolgt, und der Index des Endelements wird von this.tailIndex verfolgt.
Die Methoden queue(), dequeue(), peek() und length() der Klasse Queue verwenden nur:
属性访问（例如this.items[this.headIndex]）， 或执行算术操作（例如this.headIndex++）
Daher ist die zeitliche Komplexität dieser Methoden eine konstante Zeit O( 1).
Die Warteschlangendatenstruktur ist eine Art „First In, First Out“ (FIFO): Das früheste Element, das in die Warteschlange gestellt wird, ist das früheste Element, das aus der Warteschlange entfernt wird.
Warteschlange hat zwei Hauptoperationen: Einreihen und Entfernen aus der Warteschlange. Darüber hinaus können Warteschlangen über Hilfsoperationen wie Ansicht und Länge verfügen.
Alle Warteschlangenoperationen müssen O(1) in konstanter Zeit ausführen.
Verwandte Empfehlungen: Javascript-Lern-Tutorial
Das obige ist der detaillierte Inhalt vonDetaillierte Abbildungen und Beispiele zur Implementierung von Warteschlangen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
