Wann Stack, wann Queue?

Stack und Queue lösen unterschiedliche Reihenfolgeprobleme. Braucht man das neueste Element zuerst (Undo, Parsing, Tiefensuche mit explizitem Stack), ist der Stack passend. Soll die Ankunftsordnung erhalten bleiben (Warteschlange, Breitensuche), ist die Queue passend.

Beide ADTs können auf Arrays oder verketteten Strukturen sitzen. Die Wahl der Implementierung betrifft Konstanten und Speicher, nicht die semantische Reihenfolge.

Prüffrage: Welche Invariante gilt nach einer Folge von Operationen, und welcher Fehlerfall ist spezifiziert?

Zwei Richtungsbeispiele: Valid Parentheses [1], Implement Queue using Stacks [2].

Wo gebraucht

Routing und Crawler: BFS (Queue) für kürzeste ungewichtete Pfade, DFS/Stack für Topologie und Verschachtelung. Task-Scheduler: FIFO für Fairness, LIFO nur wenn zuletzt angestossene Arbeit zuerst fertig werden soll (Cache-Lokalität, Undo).

Vertiefung

Die passende Struktur folgt aus der gewünschten zeitlichen Ordnung. Müssen zuletzt entdeckte Teilprobleme zuerst abgeschlossen werden, passt LIFO. Muss dagegen die Reihenfolge der Ankunft oder die Entfernung vom Start erhalten bleiben, passt FIFO.

Diese Wahl verändert Algorithmen grundlegend. Bei Graphsuche führt LIFO tief in einen Zweig, während FIFO Knoten schichtweise nach ihrer Kantendistanz verarbeitet. Derselbe Graph und dieselbe Nachbarschaftsreihenfolge können daher sehr verschiedene Suchbäume ergeben.

In realen Systemen kommen Prioritäten und Begrenzungen hinzu. Ein Scheduler benötigt möglicherweise eine Prioritätsstruktur, während Rückgängig-Funktionen oft zwei LIFO-Speicher für Vorwärts- und Rückwärtsrichtung kombinieren.

Schwierigkeitsstufen

1. Alltagsabläufe einer zeitlichen Ordnung zuordnen.
2. Die Ausgabereihenfolge für dieselbe Eingabefolge vorhersagen.
3. Suchstrategie und Datenstruktur aus einer Systemanforderung ableiten.

Fallstricke

Die Struktur wird oft nach einer vertrauten Bezeichnung statt nach der benötigten Entnahmereihenfolge gewählt. Priorisierte Aufgaben sind mit keiner der beiden reinen Ordnungen vollständig modelliert.