Detaillierte Erklärung der Warteschlangendatenstruktur. Wie implementiert man sie in js?

Um ein ausgezeichneter Programmierer zu sein, ist ein breites Wissen erforderlich. Das erste, was Sie tun müssen, ist, die von Ihnen gewählte Programmiersprache zu verstehen. Wenn Sie diesen Artikel lesen, verwenden Sie höchstwahrscheinlich JavaScript.

Nachdem Sie sich jedoch mit der Programmiersprache vertraut gemacht haben, müssen Sie auch verstehen, wie Sie Daten je nach Aufgabenstellung einfach und effektiv manipulieren können. Hier kommen Datenstrukturen ins Spiel.

In diesem Artikel beschreibe ich die Struktur von Warteschlangendaten: welche Operationen sie haben und wie man sie in JavaScript implementiert.

1. Warteschlangendatenstruktur

Wenn Sie gerne reisen, müssen Sie das Ticket-Check-in-Verfahren am Bahnhof durchlaufen haben. Wenn viele Leute mit der Bahn fahren wollen, ist es normal, dass sich eine Warteschlange bildet. Personen, die gerade den Bahnhof betreten haben, reihen sich in die Warteschlange ein. Auf der anderen Seite verließen Leute, die gerade die Ticketkontrolle passiert hatten, die Warteschlange. Dies ist ein Beispiel für eine Warteschlange und funktioniert auf die gleiche Weise wie die Datenstruktur der Warteschlange.

Eine Warteschlange ist eine Datenstruktur, die der First-In-First-Out-Regel (FIFO) folgt. Das erste Element, das in die Warteschlange gelangt (Eingabe), ist das erste, das aus der Warteschlange entfernt wird (Ausgabe).

Die Warteschlange hat zwei Zeiger: den Kopf der Warteschlange und das Ende der Warteschlange. Das erste Element, das in die Warteschlange gelangt, befindet sich am vorne in der Warteschlange, während sich das letzte Element, das in die Warteschlange gelangt, am Ende der Warteschlange befindet.

Wenn ich auf das Bahnhofsbeispiel zurückblicke: Die erste Person, die das Ticket kontrolliert, steht an der Spitze der Warteschlange. Personen, die gerade in die Warteschlange eingetreten sind, stehen am Ende der Warteschlange.

Auf hoher Ebene ist eine Warteschlange eine Datenstruktur, die es Ihnen ermöglicht, Elemente nacheinander zu verarbeiten.

2. Warteschlangenoperationen

Die Warteschlange unterstützt zwei Hauptoperationen: enqueue(enqueue) und dequeue(dequeue), zusätzlich zu Peek- und Längenoperationen.

2.1 Enqueue-Vorgang

Der Enqueue-Vorgang fügt ein Element am Ende der Warteschlange ein und macht es so zum Ende der Warteschlange.

Der Verbindungsvorgang im obigen Bild fügt 8 am Ende der Warteschlange ein, und dann wird 8 zum Ende der Warteschlange. 8，之后 8 成为队列的队尾。

queue.enqueue(8);

2.2 出队操作

出队操作取出队列中第一个项目，此时队列中的下一个项目成为队首。

在上图中，出队操作返回项目7并从队列中删除。 出队之后之后，项目 2 成为新的队首。

queue.dequeue(); // => 7

2.3 Peek 操作

Peek 操作读取队首的项目，但是不改变队列。

上图中  7 是队首。 peek 操作只需返回队首 7 但是不修改队列。

queue.peek(); // => 7

2.4 length

length 操作返回队列中包含项目的数量。

上图中的队列有 4 项：4、6、2 和。7。结果队列长度为 4。

queue.length; // => 4

2.5 队列操作的时间复杂度

关于队列所有操作的重点：enqueue，dequeue，peek 和 length 必须以常数时间复杂度 O(1) 执行。

常数时间复杂度 O(1) 意味着无论队列大小如何（不管是有 10 个还是 100 万个项目），这些操作都必须在相对一致的时间内执行。

3. 用 JavaScript 实现队列

来看一下怎样在保证所有操作必须以常数时间复杂度O(1) 要求实现队列这种数据结构。

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() 是创建队列的实例。

queue.enqueue(7) 方法将 7 存入队列中。

queue.dequeue() 从队列中取出一个头部项目，而 queue.peek() 只读队首项。

最后的 Queue.Length 显示队列中还有多少个项目。

关于实现：在 Queue 类中，普通对象  this.Items  将队列的项目通过数值索引保持。 队首项的索引由 Where.HeadInex 跟踪，队尾项由 this.tailIndex 跟踪。

队列方法的复杂度

在 Queue 的 queue()、 dequeue()、 peek() 和 length() 方法中存在：

• 属性访问器（如:this.items[this.headIndex]），
• 执行算数操作（如:this.headidex++）

这些方法的时间复杂度是恒定的时间 O(1)rrreee

🎜2.2 Vorgang zum Entfernen aus der Warteschlange🎜🎜🎜Der Vorgang zum Entfernen aus der Warteschlange entfernt das erste Element in der Warteschlange und das nächste Element in der Warteschlange wird zum Anführer der Warteschlange. 🎜🎜🎜🎜at In der obigen Abbildung gibt der Vorgang zum Entfernen aus der Warteschlange das Element 7 zurück und löscht es aus der Warteschlange. Nachdem Gegenstand 2 aus der Warteschlange entfernt wurde, wird er zum neuen Teamleiter. 🎜rrreee🎜🎜2.3 Peek-Operation 🎜🎜🎜Die Peek-Operation liest das Element an der Spitze der Warteschlange, ändert jedoch nicht die Warteschlange. 🎜🎜🎜🎜Up Im Bild ist 7 der Anführer des Teams. Die Peek-Operation gibt lediglich den Kopf der Warteschlange 7 zurück, verändert die Warteschlange jedoch nicht. 🎜rrreee🎜🎜2.4 Länge🎜🎜🎜Die Längenoperation gibt die Anzahl der in der Warteschlange enthaltenen Elemente zurück. 🎜🎜🎜🎜Up Die Warteschlange im Bild besteht aus 4 Elementen: 4, 6, 2 und . 7. Die resultierende Warteschlangenlänge beträgt 4. 🎜rrreee🎜🎜2.5 Zeitkomplexität von Warteschlangenoperationen 🎜🎜🎜 Wichtige Punkte zu allen Operationen an Warteschlangen: Enqueue, Dequeue, Peek und Länge müssen mit konstanter Zeitkomplexität O(1) ausgeführt werden. 🎜🎜Konstante Zeitkomplexität O(1) bedeutet, dass diese Vorgänge unabhängig von der Warteschlangengröße (ob 10 oder 1 Million Elemente) in relativ konstanter Zeit ausgeführt werden müssen. 🎜🎜🎜3. Verwenden Sie JavaScript, um Warteschlangen zu implementieren. 🎜🎜🎜 Werfen wir einen Blick darauf, wie die Warteschlangendatenstruktur implementiert wird und gleichzeitig sichergestellt wird, dass alle Operationen mit konstanter Zeitkomplexität O(1) ausgeführt werden müssen. 🎜rrreee🎜const queue = new Queue() ist eine Instanz, die eine Warteschlange erstellt. 🎜🎜Die Methode queue.enqueue(7) speichert 7 in der Warteschlange. 🎜🎜queue.dequeue() entfernt ein Kopfelement aus der Warteschlange, während queue.peek() nur das Kopfelement der Warteschlange liest. 🎜🎜Der letzte Queue.Length zeigt an, wie viele Elemente noch in der Warteschlange sind. 🎜🎜Über die Implementierung: In der Klasse Queue speichert das gewöhnliche Objekt this.Items die Elemente der Warteschlange über numerische Indizes. Der Index des ersten Elements in der Warteschlange wird von Where.HeadInex verfolgt, und der Index des letzten Elements in der Warteschlange wird von this.tailIndex verfolgt. 🎜

🎜Die Komplexität der Warteschlangenmethode🎜

🎜In Queues queue(), dequeue(), Es gibt die Methoden peek() und length(): 🎜

• Eigenschafts-Accessoren (z. B.: this.items[this.headIndex] code >),
• Arithmetische Operationen ausführen (z. B.: this.headidex++)

🎜Die zeitliche Komplexität dieser Methoden ist eine konstante Zeit O (1). 🎜

4. Zusammenfassung

Queue ist eine Datenstruktur, die der First-In-First-Out-Regel (FIFO) folgt.

Queue hat zwei Hauptoperationen: Einreihen und Entfernen aus der Warteschlange. Darüber hinaus können Warteschlangen über Hilfsoperationen wie Peek und Länge verfügen.

Alle Warteschlangenoperationen müssen in konstanter Zeit O(1) ausgeführt werden. O(1) 执行。

挑战一下：改进 dequeue() 和 peek()

Herausforderung: Verbessern Sie die Methoden dequeue() und peek(), um einen Fehler auszulösen, wenn sie in einer leeren Warteschlange ausgeführt werden.

Weitere Programmierkenntnisse finden Sie unter:

Programmiervideo🎜! ! 🎜

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung der Warteschlangendatenstruktur. Wie implementiert man sie in js?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!