Datenstrukturen und Algorithmen: Warteschlangen

Dec 08 2022

Kürzlich haben wir die Stack-Datenstruktur gesehen und wie wir unsere eigene Version von Stacks mit JavaScript implementieren. In diesem Artikel werden wir eine andere Art von Datenstruktur sehen, die in denselben Bucket gehört und häufig neben Stacks erwähnt wird.

Warteschlangen: Konzepte

Warteschlangen sind in der Welt der Informatik genauso wichtig wie Stapel. Sie werden in vielen verschiedenen Situationen verwendet. Ich könnte behaupten, dass sie in jedem großen und großen System, das viel Kommunikation, Planung und Priorisierung erfordert, ein Muss sind.

# Was sind Warteschlangen?

Eine Warteschlange ist eine lineare Datenstruktur, in der Elemente nacheinander angeordnet sind. Genauso wie Stacks haben sie einige Einschränkungen, wenn es darum geht, wie Operationen (Einfügen und Löschen) auf ihnen durchgeführt werden. In Warteschlangen werden Operationen an zwei Enden durchgeführt und nicht an einem einzigen Ende wie im Fall von Stapeln. Eine Warteschlange funktioniert nach dem Prinzip First In First Out (FIFO). Wenn wir Warteschlangen mit einem Beispiel aus unserem täglichen Leben veranschaulichen möchten, könnten wir die Schlange von Menschen in einem Starbucks-Laden beobachten, die auf ihren Kaffee warten. Wer zuerst kommt, wird zuerst bedient und so weiter...

Wenn also jemand kommt, um einen Kaffee zu kaufen, würde er sich ans Ende der Schlange stellen. In Bezug auf Datenstrukturen würden wir sagen, dass wir uns in die Warteschlange einreihen . Mit anderen Worten, wir fügen ein neues Element am Ende der Warteschlange ein. Auf der anderen Seite, wenn der vorderste in der Schlange bedient wird, würde er seinen Platz dem nächsten überlassen und so weiter. Auch in Bezug auf Datenstrukturen würden wir sagen, dass wir ein Element aus der Warteschlange entfernen oder ein Element aus dem Kopf der Warteschlange entfernen.

# Warum sollten Sie Warteschlangen verwenden?

Ich kann die verschiedenen Szenarien nicht zählen, in denen Warteschlangen besser geeignet sind als jede andere Art von Datenstruktur. Dennoch möchte ich zwei Hauptgründe auflisten, die Ihnen einen Einblick geben könnten, dass Sie möglicherweise Warteschlangen für eine bestimmte Situation verwenden müssen.

Warten…

2. Eine faire Bestellung…

Wenn das Problem, das Sie lösen, garantieren soll, dass der Erste, der kommt, auch der Erste ist, der bedient wird, dann eine Warteschlange für die Rettung. Die Tatsache, dass Warteschlangen dem FIFO-Prinzip folgen, garantiert eine faire Ordnung.

Warteschlangen: Implementierung in JavaScript

Jetzt werden wir unsere benutzerdefinierte Version von Warteschlangen mit JavaScript implementieren. Im letzten Artikel haben wir erwähnt, dass Stacks je nach Bedarf entweder mit Arrays oder verknüpften Listen implementiert werden können. Für die Warteschlangendatenstruktur wäre die Verwendung einer verknüpften Liste jedoch ein klügerer Ansatz. Wieso den?

Einfach ausgedrückt, wenn wir Arrays verwenden, würde die Dequeue- Operation zum Beispiel jedes Mal das Verschieben des Arrays erfordern, wenn wir ein Element aus der Warteschlange entfernen. Dies wäre zeitaufwändig. Daher erhöht es die zeitliche Komplexität Ihrer Lösung. Unter der Annahme, dass Sie nach dem Entfernen eines Elements keine Verschiebung vornehmen, kann dies außerdem zu einer Verschwendung von Speicher führen, da Sie Leerzeichen im Array hinterlassen. Auch dies führt zu einer Erhöhung der Platzkomplexität Ihrer Lösung.

Lassen Sie uns jetzt stattdessen verknüpfte Listen verwenden …

Wir sind noch nicht fertig… Dieser Codeabschnitt muss noch verbessert werden…

Warteschlangen: Jetzt sind Sie dran…

# Aufgabe Eins

Verwenden Sie Ihre bevorzugte Programmiersprache, um eine neue Operation back() hinzuzufügen, um den Wert am Ende der Warteschlange anzuzeigen.

# Aufgabe zwei

Wir brauchen eine Operation, um die Warteschlange zu drucken, können Sie das bitte für uns erledigen? Verwenden Sie trotzdem Ihre bevorzugte Programmiersprache …