Heim > Artikel > Backend-Entwicklung > Unterschied zwischen Array-Warteschlange und verknüpfter Listenwarteschlange
Eine Warteschlange ist eine lineare Datenstruktur, die Warteschlangenelemente in einer bestimmten Reihenfolge einfügt und entfernt. Wir können Warteschlangen in C++ implementieren, indem wir Arrays und verknüpfte Listen verwenden. Beide Warteschlangenimplementierungen haben ihre eigenen Vorteile und Einsatzmöglichkeiten. In diesem Tutorial unterscheiden wir zwischen Array-basierten Warteschlangen und verknüpften Listen-basierten Warteschlangen.
Eine Warteschlange ist eine Reihe von Elementen, die das FIFO-Prinzip (First In, First Out) zum Einfügen und Löschen von Elementen verwenden. Warteschlangen in der Informatik ähneln Warteschlangen im wirklichen Leben. Die erste Person, die die Warteschlange betritt, wird zuerst entfernt.
Der Vorgang des Entfernens von Warteschlangendaten wird als deQueue bezeichnet. Der Vorgang des Hinzufügens von Daten zur Warteschlange wird als enQueue bezeichnet.
Die Warteschlange hat zwei Punkte -
After – Elemente aus der Warteschlange werden von hier aus eingefügt.
Front – Das Element in der Warteschlange wird von hier entfernt.
Wir können Warteschlangen auf zwei Arten implementieren -
Array-basierte Warteschlange
Listenbasierte Warteschlange oder verknüpfte Listenwarteschlange
Eine mithilfe von Arrays implementierte Warteschlange wird als Array-basierte Warteschlange bezeichnet. Es verwendet zwei Zeiger: Vorne und Hinten, die den Löschpunkt bzw. den Einfügepunkt in der Warteschlange darstellen.
In dieser Implementierung wird die Array-Größe vor dem Einfügen der Daten vordefiniert. Dies ist die einfachste Möglichkeit, Warteschlangendaten einzufügen und zu löschen.
In einer auf Listen basierenden Warteschlange oder einer auf einer verknüpften Liste basierenden Warteschlange wird die verknüpfte Liste für die Warteschlangenimplementierung verwendet. Jeder Warteschlangenknoten besteht aus zwei Teilen: Ein Teil dient zum Speichern von Daten und der andere Teil ist der Verbindungsteil oder Speicherteil.
Jedes Warteschlangenelement ist mit dem Speicher des nächsten Warteschlangenelements verbunden. In einer listenbasierten Warteschlange gibt es zwei Zeiger -
Vorheriger Zeiger – Stellt den Speicher des letzten Warteschlangenelements dar.
Zurückzeiger – Speicher, der das erste Element der Warteschlange darstellt.
S.No | lautet: Seriennummer |
Array-basierte Warteschlange |
Verknüpfte Listenbasierte Warteschlange |
|
---|---|---|---|---|
1 |
Komplexität |
Es ist einfach, Vorgänge zu implementieren und durchzuführen. |
Es ist nicht einfach umzusetzen. |
|
2 |
Suchvorgang |
Es hilft, einfach und schnell zu suchen. |
Langsam und schwierig zu suchen. |
|
3 |
Warteschlangengröße |
Definieren Sie die Warteschlangengröße zum Zeitpunkt der Initialisierung. |
Beim Initialisieren der Warteschlange muss die Warteschlangengröße nicht definiert werden. |
|
4 |
Einfüge- und Löschvorgänge |
Es ist schwierig, Daten am Anfang einzufügen, aber es ist einfach, Daten am Ende der Warteschlange einzufügen. |
Es ermöglicht eine einfache Dateneinfügung an beiden Enden der Warteschlange. |
|
5 |
Zugangsdaten |
Zufälliger Datenzugriff. |
Es bietet sequentiellen Zugriff auf Warteschlangenelemente. |
|
6 |
Anpassung der Warteschlangengröße |
Das Ändern der Warteschlangengröße ist schwierig. |
Das Anpassen der Warteschlangengröße ist einfach. |
|
7 |
Speichernutzung |
Es verbraucht weniger Speicher. |
Es verbraucht mehr Speicher. |
|
8 |
Vorteile |
|
|
|
9 |
Nachteile |
|
|
Wenn Ihre Warteschlange eine feste Größe hat und keine Notwendigkeit besteht, die Warteschlangengröße zu ändern, können Sie die Warteschlange mithilfe eines Arrays implementieren. Array-basierte Warteschlangen sind auch nützlich, wenn die Suche schnell ist und weniger Speicher verbraucht.
Die Implementierung einer auf verknüpften Listen basierenden Warteschlange ist sehr nützlich, wenn die Warteschlangengröße dynamisch ist und Warteschlangenelemente mehrmals eingefügt und gelöscht werden. Obwohl es mehr Speicher verbraucht, eignet es sich für umfangreiche Anwendungen
Die Verwendung von Array-basierten Warteschlangen und verknüpften Listen-basierten Warteschlangen hängt von den Anforderungen ab. In großen Anwendungen sind Array-basierte Warteschlangen nicht erfolgreich und stattdessen werden verknüpfte Listen-Warteschlangen verwendet.
Array-basierte Warteschlangen verbrauchen weniger Speicher, verschwenden aber viel Speicher, da nach dem Einfügen von Elementen im Backend etwas ungenutzter Speicher vor dem ersten Element verbleibt.
Das obige ist der detaillierte Inhalt vonUnterschied zwischen Array-Warteschlange und verknüpfter Listenwarteschlange. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!