Stack (IntroProg)
Stack (IntroProg)
- Stack: Datenstruktur, welche effizientes Entfernen in der umgekehrten Einfügereihenfolge ermöglicht.
- Last-In-First-Out (LIFO); First-In-Last-Out (FILO) Datenstruktur
- Methoden:
push/pop - Einsatzbereiche:
- Tellerstapeln
- Browser Historie
- Funktionsaufrufe! U.a. Bei der Rekursion
- Kartenstapel
Implementierung
- Die Implementierung kann als Liste erfolgen:
- push fügt am Kopf ein neues Elemente ein
- pop entnimmt das als Letztes eingefügte Element
- Beide Operationen können in O(1) durchgeführt werden.
- head ist gleichzeitig "top of stack".
Implementierung als Array
!200
- Auch in einem Array können push und pop mit Laufzeit O(1) implementiert werden.
- Nachteil: Max. Stackgröße ist fest, d.h. der Stapel kann "überlaufen" (stack overflow).
- Zugriff auf Element kann jedoch effizienter sein, als mit linked list.