Detaillierte Beispiele mit Bildern und Texten zur Implementierung von Warteschlangen in JavaScript

Verwandte Empfehlungen: Javascript-Tutorial

1. Warteschlangendatenstruktur

• Warteschlange ist eine Art FIFO-Datenstruktur (First In, First Out). Das erste in die Warteschlange eingereihte Element (Eingabe) ist das erste aus der Warteschlange entfernte Element (Ausgabe).
• Die Warteschlange hat zwei Zeiger: Kopf und Schwanz. Das älteste in der Warteschlange befindliche Element befindet sich am Anfang und das neueste in der Warteschlange befindliche Element am Ende.
• Die Warteschlange ähnelt dem Anstehen in der U-Bahn. Passagiere in der Nähe der Tür stehen an der Spitze der Warteschlange, und Passagiere, die gerade in die Warteschlange eingetreten sind, stehen am Ende der Warteschlange.

Aus übergeordneter Sicht ist eine Warteschlange eine Datenstruktur, die es uns ermöglicht, jedes Datenelement in der Reihenfolge zu verarbeiten, in der es in der Datenbank gespeichert ist.

2. Operationen in der Warteschlange

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.

• Enqueue-Operation <br/>Bei der Enqueue-Operation wird ein Element am Ende der Warteschlange eingefügt, und das eingefügte Element wird zum Ende der Warteschlange.

Der Enqueue-Vorgang in der obigen Abbildung fügt Element 8 am Ende ein und 8 wird zum Ende der Warteschlange.

queue.enqueue(8);

• Vorgang zum Entfernen aus der Warteschlange <br/> Der Vorgang zum Entfernen aus der Warteschlange besteht darin, das Element am Anfang der Warteschlange zu extrahieren, und das nächste Element in der Warteschlange wird zum Kopfelement.

Im Bild oben kehrt der Vorgang zum Entfernen aus der Warteschlange zurück und entfernt Element 7 aus der Warteschlange. Nach dem Entfernen aus der Warteschlange wird Element 2 zum neuen Kopfelement.

queue.dequeue(); // => 7

• Inspektionsoperation <br/> Die Inspektionsoperation liest den Anfang der Warteschlange, ohne die Warteschlange zu ändern.

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

• Warteschlangenlänge Die Längenoperation berechnet, wie viele Elemente die Warteschlange enthält.

In der Warteschlange im Bild befinden sich 4 Elemente: 4, 6, 2 und 7. Daher beträgt die Warteschlangenlänge 4.

queue.length; // => 4

• Zeitkomplexität der Warteschlangenoperation Das Wichtigste für alle Warteschlangenoperationen (Einreihen, Entfernen, Anzeigen und Länge) ist, dass alle diese Operationen in einer festen Zeit O(1) ausgeführt werden müssen.

Konstante Zeit O(1) bedeutet, dass unabhängig von der Warteschlangengröße (sie kann 10 oder 1 Million Elemente haben): Einreihungs-, Aus-Warteschlangen-, Peek- und Längenoperationen alle gleichzeitig ausgeführt werden müssen.

3. Warteschlangen in JavaScript implementieren

Schauen 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.

Klassenwarteschlange {
  Konstruktor() {
    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++;
    Artikel zurücksenden;
  }

  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() ist, wie eine Instanz einer Warteschlange erstellt wird.

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() nur einen Blick von Anfang an wirft.

Schließlich zeigt queue.length an, wie viele Elemente noch in der Warteschlange sind.

Zur 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.

• Komplexität der Queue-Methoden

Die Methoden queue(), dequeue(), peek() und length() der Klasse Queue verwenden nur:

Attributzugriff (z. B. this.items[this.headIndex]),

oder arithmetische Operationen ausführen (z. B. this.headIndex++).

Daher beträgt die zeitliche Komplexität dieser Methoden die konstante Zeit O(1).

4. Zusammenfassung

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.

Warteschlangen haben 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 eine detaillierte Erklärung der Implementierung von Warteschlangen in JavaScript mit Beispielen und Bildern. Weitere Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website.