Ein Leitfaden für Anfänger zum Verständnis von Warteschlangen und Prioritätswarteschlangen

Als Programmierer arbeiten Sie je nach Umfang Ihrer Projekte mit unterschiedlichen Datenstrukturen. Ein solches Konzept ist eine Warteschlangen-Datenstruktur; Warteschlangen sind für Schüler unerlässlich und werden in vielen wichtigen Algorithmen verwendet. Wie Warteschlangen haben Prioritätswarteschlangen ein ähnliches Konzept, weisen jedoch einige grundlegende Unterschiede auf.

Lesen Sie weiter, um Warteschlangen und Prioritätswarteschlangen zu verstehen.

Was ist eine Warteschlange?

Eine Warteschlange ist eine einfache Datenstruktur, die eine Vielzahl von Anwendungen in realen Codierungsprojekten hat. Datenstrukturen sind von Natur aus abstrakt, aber der Einfachheit halber stellen wir uns vor, dass eine Warteschlangen-Datenstruktur eine lineare Form mit zwei verschiedenen Enden hat.

Hinsichtlich der Zeitkomplexität ermöglicht eine Warteschlange das Einfügen (Enqueue) und Löschen (Dequeue) in der O(1)-Zeit. Aufgrund ihrer asymptotischen Effizienz sind Warteschlangen für große Datensätze effizient. Warteschlangen sind von Natur aus first-in-first-out (FIFO), d. h. auf ein zuerst eingefügtes Datenelement wird zuerst zugegriffen. Im Gegensatz dazu haben Stacks einen Last-in-First-out-Charakter (LIFO) und haben nur ein offenes Ende.

Stellen Sie sich eine Ticketschlange in einem Kino vor; Jeder neue Kunde, der ankommt, reiht sich an einem Ende in die Warteschlange ein. Jeder Kunde kauft nacheinander ein Ticket und verlässt die Warteschlange am Frontend. Die Warteschlangen-Datenstruktur funktioniert genau wie jede reale Warteschlange, und Daten werden an einem Ende eingefügt (in die Warteschlange gestellt) und am anderen Ende entfernt (in die Warteschlange gestellt). Sie können jetzt hoffentlich verstehen, warum Warteschlangen einer FIFO-Methodik folgen.

Eine Warteschlange hat viele reale Codierungsanwendungen. Es wird häufiger in Anwendungen verwendet, bei denen Daten nicht sofort, sondern in einer FIFO-Reihenfolge verarbeitet werden müssen. Disk Scheduling, asynchrone Datenübertragung, Semaphoren sind einige typische Anwendungen. First-Come-First-Serve-Scheduling-Aufgaben wie Druckspooling oder Eingabegerätepuffer verwenden ebenfalls eine Warteschlange.

Was ist eine Prioritätswarteschlange?

Eine Prioritätswarteschlange ähnelt einer Warteschlange, hat jedoch zusätzliche Eigenschaften. Wenn ein Datenelement in die Prioritätswarteschlange eingereiht wird, erhält es eine Prioritätsnummer. Im Gegensatz zum Entfernen aus einer Standardwarteschlange werden Datenelemente mit hoher Priorität vor Datenelementen mit niedriger Priorität aus der Warteschlange entfernt. Priorität ersetzt die Ankunftsreihenfolge in einer Prioritätswarteschlange, weshalb Prioritätswarteschlangen keine konsistente FIFO-Natur haben.

Verwandt: Algorithmen, die jeder Programmierer kennen sollte

Programmierer können eine Prioritätswarteschlange auf verschiedene Weise implementieren. Eine einfache Implementierung besteht darin, ein Array mit einem Struktur-/Klassendatenelement zu verwenden, und das Datenelement enthält die Priorität jedes Datenelements und die Daten selbst. Eine andere Implementierung einer primitiven Prioritätswarteschlange besteht darin, eine verknüpfte Liste zu verwenden. Durch verknüpfte Listen implementierte Prioritätswarteschlangen sind funktional, aber aufgrund ihrer Leistung nicht ideal.

Mit einem Heap können Sie eine Warteschlange mit besserer Priorität implementieren. Wenn Sie sich erinnern, liefern binäre Heaps das maximale oder minimale Element in 0(1)-Zeit, und das Einfügen dauert nur 0(logN)-Zeit. Mit Hilfe von Heaps bieten Prioritätswarteschlangen im Vergleich zu Warteschlangen oder Arrays asymptotisch eine bessere Leistung.

Eine Prioritätswarteschlange hat auch eine Vielzahl von wesentlichen Anwendungen. Prioritätswarteschlangen sind in Graphalgorithmen wie dem Minimum Spanning Tree von Prim und dem Shortest Path-Algorithmus von Dijkstra von entscheidender Bedeutung. Sie sind auch ideal für Prozessplanungsalgorithmen von Computerprozessoren (CPU).

Datenstrukturen lernen

Queues und Priority Queues sind wichtige Datenstrukturen für alle Anfänger. Es ist entscheidend, dass die Studierenden diese Datenstrukturen implementieren und in verschiedenen Projekten verwenden können.

Andere Datenstrukturen wie Heaps, Stacks und Trees sind für Studenten und Fachleute gleichermaßen wichtig. Es ist auch üblich, dass Interviewer Bewerber zu Datenstrukturen befragen.

Nachdem Sie diesen Artikel gelesen haben, sollten Sie nun eine gute Vorstellung davon haben, wie Warteschlangen und Prioritätswarteschlangen funktionieren. Wenn immer noch alles etwas unklar erscheint, werden Sie sich damit auseinandersetzen, wenn Sie mehr Erfahrung mit ihnen sammeln.

Haufen vs. Stapel: Was zeichnet sie aus?

Sie haben von Heaps and Stacks gehört, aber wann sollten Sie eines über dem anderen verwenden?

Weiter lesen

Über den Autor