Stack-Datenstruktur in Python
Ein Stack entfernt immer das zuletzt eingefügte Element zuerst.
Was ist Stack-Datenstruktur?
Ein Stack entfernt immer das zuletzt eingefügte Element zuerst.
Implementiere Push, Pop und Peek nach dem LIFO-Prinzip.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Beispielcode
main.py
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)Erwartete Ausgabe
popped: third
top: second
stack: ['first', 'second']So funktioniert es
Python-Listen unterstützen append und pop am Ende amortisiert in O(1). Stacks werden unter anderem für Rückgängig-Funktionen und Tiefensuche verwendet.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.