Nach den Queues wird in diesem Artikel zum Thema Datenstrukturen in Python auf Stacks eingegangen. Es handelt sich bei einem Stack (Stapelspeicher) ebenfalls um eine Datenstruktur, die eine Ähnlichkeit zur Liste aufweist. Die Implementierung eines Stacks kann (auch) mithilfe einer Liste vorgenommen werden. Bei Stacks gilt das LIFO-Prinzip (Last In, First Out). Das letzte Element, das hinzugefügt wird, ist das erste Element, das wieder entfernt wird.
Der Vorteil dieser Datenstruktur besteht in der konstanten Zeit hinsichtlich des Hinzufügens oder des Entfernens des obersten Elements (Big-O-Notation: O(1)). Es gibt aber auch einen entscheidenden Nachteil: Und zwar bezüglich des Zugriffs auf andere Elemente. Denn bevor auf diese zugegriffen werden kann, müssen erst alle anderen, darüber liegenden, Elemente entfernt werden. Und das bedeutet gemäß der Big-O-Notation einen O(n)-Wert, wobei n für die Anzahl der Elemente im Stack steht.
Hinsichtlich des Ablegens eines Elements auf dem Stack wird von einer Push-Operation gesprochen, hinsichtlich des Entfernens wird von einer Pop-Operation gesprochen. Stacks spielen insbesondere bei der Speicherverwaltung eine große Rolle.
Eine einfache Implementierung als Liste könnte wie folgt aussehen:
# Leeren Stack (Liste) erzeugen
stack = []
# Elemente hinzufügen
stack.append(24)
stack.append(32)
stack.append(17)
stack.append(51)
stack.append(4)
# Elemente des Stack ausgeben
print(stack) # -> [24, 32, 17, 51, 4]
# Ein Element vom Stack entfernen
stack.pop()
print(stack) # -> [24, 32, 17, 51]Das letzte mit append() hinzugefügte Element ist die Zahl 4, die mit der Methode pop() als erstes Element wieder entfernt wird (Last In, First Out).
Dieses Beispiel wurde in leicht abgewandelter Form der offiziellen Python-Dokumentation entnommen. Dort findet Ihr weitere Informationen und Beispiele zu Datenstrukturen in Python.
Zum Schluss sei noch angemerkt, dass auch andere Weg beschritten werden können. So wäre beispielsweise eine Implementierung mittels einer Linked List möglich.
Zuletzt aktualisiert am 21. Juni 2022