Was ist ein Stack?<\/h2>\n\n\n\n
Ein Stack ist eine Sammlung von Elementen, bei der die Elemente nur auf einer Seite (in grafischen Darstellungen klassischerweise oben) eingef\u00fcgt und wieder entnommen werden k\u00f6nnen.<\/p>\n\n\n\n
Am besten stellt man sich einen Stack wie einen Tellerstapel vor:<\/p>\n\n\n\n
![\"Tellerstapel\"](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/stack-of-plates-600x150.png\")
Neue Teller k\u00f6nnen nur oben<\/em> auf den Stapel gelegt werden, und Teller k\u00f6nnen auch nur von oben<\/em> wieder entnommen werden.<\/span><\/p>\n\n\n\n Da dadurch der zuletzt hinzugef\u00fcgte Teller als erstes wieder entnommen wird, spricht man vom Last-in-First-out-Prinzip (LIFO).<\/p>\n\n\n\n Beim abstrakten Datentyp \"Stack\" k\u00f6nnte das dann in etwa wie folgt aussehen:<\/p>\n\n\n\n Die Grafik zeigt einen Stack, der einige Strings enth\u00e4lt. Als n\u00e4chstes Element wird \"grape\" auf den Stack gelegt. Danach w\u00fcrden wir \"grape\" auch als erstes wieder entnehmen m\u00fcssen.<\/p>\n\n\n\n Eine Stack-Datenstruktur bietet in der Regel die folgenden Operationen an:<\/p>\n\n\n\n Du kannst dir z. B. die Webseiten-Historie innerhalb eines Browser-Tabs als Stack vorstellen: Jedesmal, wenn du einen Link anklickst, wird die vorherige URL auf einen Stack gelegt. Beim Bet\u00e4tigen des Zur\u00fcck-Buttons wird die oberste URL des Stacks entnommen und wieder angezeigt. <\/p>\n\n\n\n In \u00e4hnlicher Weise werden bei der Ausf\u00fchrung eines Computerprogramms die R\u00fccksprungsadressen beim Aufruf von Methoden auf den sogennanten Call Stack gelegt (deutsch: \"Aufrufstapel\"), so dass nach Ausf\u00fchrung der Methode an die Aufrufposition zur\u00fcckgesprungen werden kann. Der durch eine zu tiefe Verschachtelung verursachte Auch Compiler und Parser verwenden Stacks, z. B. bei der Verarbeitung von XML- und JSON-Dokumenten oder der Evaluierung von mathematischen Ausdr\u00fccken.<\/p>\n\n\n\n Eine Einf\u00fchrung in das Thema Zeitkomplexit\u00e4t findest du im Artikel \"O-Notation und Zeitkomplexit\u00e4t \u2013 anschaulich erkl\u00e4rt<\/a>\".<\/em><\/p>\n\n\n\n In der Regel wird ein Stack mit einem Array<\/a> oder einer verketteten Liste<\/a> implementiert. Bei beiden Varianten ist der Aufwand f\u00fcr das Einf\u00fcgen oder Entnehmen eines Elements konstant und h\u00e4ngt nicht von der Anzahl der im Stack vorhandenen Elemente ab.<\/p>\n\n\n\n Die Zeitkomplexit\u00e4t lautet somit: O(1)<\/em>.<\/p>\n\n\n\n Stacks k\u00f6nnen auch mit Queues<\/a> implementiert werden \u2013 das aber eher zu Schulungszwecken. Die Zeitkomplexit\u00e4t ist dann h\u00f6her. Mehr dazu liest du im entsprechenden Teil des Tutorials.<\/p>\n\n\n\nLIFO-Prinzip beim Stack<\/h2>\n\n\n\n
![\"Stack](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/03\/stack-data-structure-600x252.png\")
Anwendungsgebiete f\u00fcr Stacks<\/h2>\n\n\n\n
StackOverflowError<\/code> ist dir vielleicht schon mal begegnet.<\/p>\n\n\n\nZeitkomplexit\u00e4t der Stack-Operationen<\/h2>\n\n\n\n