Stack, Queue & List

Agenda

• Stack
• Queue
• List

Stack

Was ist ein Stack?

Bei einem Stack werden neue Elemente gestapelt. Man kann immer nur das oberste Element entnehmen.

Beispiel Teller

Anwendungen von Stack

• Undo/Redo
• Browserverlauf
• Depth-First-Search (Trees)

Stack Operationen

• push → Element oben hinzufügen
• pop → Element von oben entfernen
• peek → oberstes Element anschauen
• isEmpty

Demo - Stack

Performance

• Zeitkomplexität: O(1)
• Speicherkomplexität: O(N)

Wie kann man die Größe ermitteln?

Queue

Was ist eine Queue?

Bei einer Queue werden neue Elemente hinten hinzugefügt. Man kann immer nur das vorderste Element entnehmen.

Beispiel Mensa

Anwendungen von Queue

• Datenübertragung
• Warteschlangenverarbeitung
• Scheduler in Betriebssystemen

Queue Operationen

• enqueue → Element hinten hinzufügen
• dequeue → Element vorne entfernen
• peek → vorderstes Element anschauen
• isEmpty

Demo - Queue

Performance

• Zeitkomplexität: O(1)
• Speicherkomplexität: O(N)

Wie kann man die Größe ermitteln?

List

Was ist eine Liste?

Bei einer Liste werden neue Elemente hinten oder an einer bestimmten Stelle hinzugefügt. Man kann auf jedes Element über einen Index in der Liste zugreifen, die Größe ermitteln und Elemente löschen.

Beispiel ToDo Liste

List Operationen

• length
• prepend → Element vorne hinzufügen
• append → Element hinten hinzufügen
• insertAt → Element an Index hinzufügen
• remove → Element löschen
• removeAt → Element an Index löschen
• get → Element an Index zurückgeben

Demo - List

Performance

• Zeitkomplexität: O(1) → length, prepend, append
• Zeitkomplexität: O(N) → insertAt, remove, removeAt, get
• Speicherkomplexität: O(N)

Vergleich ArrayList → LinkedList