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.