Detaillierte Abbildungen und Beispiele zur Implementierung von Warteschlangen in JavaScript

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

1. Warteschlangendatenstruktur

• Warteschlange ist eine Art „First In, First Out“-Datenstruktur (FIFO). Das erste in die Warteschlange eingereihte Element (Eingabe) ist das erste aus der Warteschlange entfernte Element (Ausgabe).
• Die Warteschlange hat 2 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 ist wie bei uns 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 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.

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-Vorgang
  Der Enqueue-Vorgang besteht darin, ein Element am Ende der Warteschlange einzufügen, und das eingefügte Element wird zum Ende der Warteschlange.

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

• Dequeue-Vorgang
  Der Dequeue-Vorgang 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 das Element 7 aus der Warteschlange. Nach dem Entfernen aus der Warteschlange wird Element 2 zum neuen Hauptelement.

queue.dequeue(); // => 7

• Inspektionsoperationen
  Inspektionsoperationen lesen 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
  Wichtig für alle Warteschlangenoperationen (Einreihen, Entfernen aus der Warteschlange, Anzeigen und Länge), alle diese Operationen müssen O(1) in einer festen Zeit ausführen.

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.

3. Warteschlangen in JavaScript implementieren

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;    // => 3

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

• Komplexität der Warteschlangenmethoden

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

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.

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!