Ein Stack folgt dem LIFO-Prinzip (last in-first out). Ähnlich wie bei
einem Stapel Pfannkuchen. Den letzten Pfannkuchen, den wir aus der
Pfanne auf den Stapel legen, ist der erste, den wir vom Stapel nehmen.
Ein Stack ist wie ein Wrapper um einen Array/ eine Linked List,
welcher uns einen anderen Weg der Lagerung/des Zugangs zu den
Elementen gibt.
Beispiele für die Verwendung eines Stacks:
Webbrowser-Verlauf, Compiler-/Navigations-Aufbau(vor&zurück),
Implementierung von Undo-/Redo-Features. Ein Stack bietet drei
Hauptfunktionen:
eine, um die Spitze zu sehen (peek),
eine, um nach oben zu schieben (push), und
eine, um von der
Spitze abzuspringen (pop).
Ein Stack und eine Queue haben so ziemlich die gleiche Datenstruktur,
der einzige Unterschied besteht darin, wie sie ihre Informationen
anordnen.
Stacks und Queues eignen sich hervorragend, um die
Reihenfolge basierend auf der Einfügezeit beizubehalten.
Einfache Faustregel:
Verwende einen Stack, wenn du das neueste
Element verfolgen möchtest. Verwende eine Queue, wenn du das älteste
Element im Auge behalten möchtest.
push (item) & pop ( ) : O(1)
peek ( ) & empty ( ) : O(1)
Runtime-Complexity = O(1)