Stack und Queue... Wann LinkedList verwenden und wann nicht?
Also, ein Stack funktioniert nach dem Last-In-First-Out (LIFO)-Prinzip, während eine Queue nach dem First-In-First-Out (FIFO)-Prinzip arbeitet...
Mir ist aufgefallen, dass man einen Stack auch ohne LinkedList implementieren kann. Eine LinkedList wäre nicht unbedingt notwendig, da wir ja nur auf das oberste Element des Stacks zugreifen müssen, oder? Wäre das dann laufzeitlich möglicherweise effizienter ein Array zu benutzten?
Aber für eine Queue dann eher doch LinkedList, da wir sowohl auf das erste als auch auf das letzte Element der Warteschlange zugreifen müssen? Aber ich könnte eine Queue auch ohne LinkedList implementieren, oder? Wovon genau hängt diese Wahl ob mit oder ohne LinkedList genau ab? Ich bin etwas verwirrt.
Und bei einer Dequeue lieber mit LinkedList?
3 Antworten
Ob Array oder LinkedList hängt vor allem davon ab, wie felxibel das sein soll und ob du vorab die benötigte Maximalgröße abschätzen kannst. Ein Array hat immer eine definierte Größe, wenn es irgendwann mal mehr Einträge geben sollte, knallt es entweder "Stack Overflow" oder der Kram muss aufwendig neu (größer) angelegt, umkopiert und alle Referenzen angepasst werden. Ansonsten ist der Zugriff auf Array-Elemente sehr schnell, weil im einfachsten Fall nur ein Speicherzugriff, der wahrscheinlich sogar im Prozessorcache liegt. Für eine Queue als Array-Implementation würde man einen Ringpuffer mit entsprechend getrennten Schreib- und Lesezeigern einsetzen.
Da bei einer LinkedList für jedes Element einzeln Speicher reserviet wird, ist das flexibler, es knallt erst wenn der Speicher wirklich voll ist, und es ist wesentlich langsamer.
Im Prozessor ist ein Stack einfach ein Speicherbereich mit einem speziellem Register "Stackpointer", der auf das oberste Element zeigt, das wird direkt vom Prozessor-Befehlssatz (PUSH/POP) unterstützt. Komplexere Datenstrukturen wie Listen landen auf dem Heap und jede Speicheranforderung muss durch das Memory Management des Betriebssystems, weswegen das eben etliche Takte länger dauert.
Welche Umsetzung Du wählst hängt unter anderem auch von den verfügbaren Mitteln der Sprache ab. Egal ob Stack oder Queue, in dem Moment wo Du a priori nicht die Größe kennst bzw. eine entsprechend hohe Dynamik hast, wird Dich ein statisches Feld nicht weit bringen - Du wirst zumindest ein dynamisches Feld brauchen.
Das bedeutet zusätzlichen Implementierungsaufwand, den Du bei dynamischer Allokation mit Pointern/Referenzen weitgehend auf die Standardbibliothek abwälzt.
Hey sparklingo
Es gibt hier keine Allgemeinlösung, es kommt immer auf den Anwendungsfall an.
Grundsätzlich spielt es keine Rolle ob du einen Stack mittels Array oder LinkedList implementierst, zumindest für die Laufzeit.
Aber: Ein Array hat nur eine begrenzte Anzahl Elemente, hast du eine unbekannt grosse Menge an Items für den Stack, kommen Kosten von O(n) für das vergrössern des Arrays dazu. Dafür sind die Kosten für die einzelnen Operationen beim Array günstiger, als bei der Liste.
Zum Thema Queue:
Ja, du kannst eine Queue auch mit 2 Stacks, also 2 Arrays implementieren. Du möchtest ja von einer LIFO Funktionalität zu einer FIFO Funktionalität kommen.
Funktionieren tut das folgendermassen:
Du fügst "A" auf den Stack 1. Nun kommt "B" in die Queue. Dann packst du "A" auf den Stack 2, packst "B" auf Stack 1 und dann wieder "A" von Stack 2 auf Stack 1.
Du schauffelst also die Elemente hin und her.
Hoffe ich konnte dir damit deine Fragen beantworten.