StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
Hast Du Dich schon einmal gefragt, wie die Rückgängig- oder Wiederholen-Funktion in Word oder Photoshop implementiert sein könnte? Dann hast Du hier mit dem Artikel über den Stack Deine Antwort!Im Bereich der Informatik gehört der Stack zu den abstrakten Datentypen (ADT) und beschreibt eine Datenstruktur, bei der man zu jeder Zeit nur das oberste Element abrufen kann. Auf Deutsch nennt…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenHast Du Dich schon einmal gefragt, wie die Rückgängig- oder Wiederholen-Funktion in Word oder Photoshop implementiert sein könnte? Dann hast Du hier mit dem Artikel über den Stack Deine Antwort!
Im Bereich der Informatik gehört der Stack zu den abstrakten Datentypen (ADT) und beschreibt eine Datenstruktur, bei der man zu jeder Zeit nur das oberste Element abrufen kann. Auf Deutsch nennt sich der Stack deshalb auch oft „Stapelspeicher“ oder „Kellerspeicher“.
Ein Stack ist eine dynamische Datenstruktur, bei der nur das oberste Element entnommen und ein neues Element nur ganz oben abgelegt werden kann.
Ein Stack ist im Grunde eine spezielle Form der linearen Liste. Allerdings kann man bei einem Stack nicht auf tiefer liegende Elemente zugreifen, sofern man nicht alle Elemente darüber entfernt. Das LIFO-Prinzip beschreibt genau diese Eigenschaft eines Stacks.
Stelle Dir einen Stapel Bücher auf deinem Tisch vor. Zu einer gegebenen Zeit kannst Du ohne Weiteres nur jenes Buch entnehmen, welches zuletzt oben auf den Stapel gelegt wurde.
Genau das beschreibt das Last-in-first-out-Prinzip, oder kurz: LIFO-Prinzip.
Bei einem Stack gibt es drei gängige Operationen, die zum Einsatz kommen.
Doch wo wird ein Stack überhaupt in der Praxis verwendet?
Praktische Anwendung findet der Stack vor allem dort, wo man Daten nur temporär speichern möchte.
Ein Beispiel ist die Ausführung eines Programms, die aus verschachtelten Funktionsaufrufen besteht. Diese Aufrufe legt das Programm auf einem Call Stack ab und weiß somit jederzeit, in welcher Funktion es sich gerade befindet und welche Elternfunktion diese aufgerufen hat.
Entwickler nutzen den Call Stack häufig für das Debugging eines Programms.
Ein weiterer Anwendungsfall für den Stack ist die Tiefensuche (Depth-first search). Das ist ein Algorithmus, um einen Knoten in einer Baumstruktur zu finden, und häufig verwendet auch dieses Verfahren die Stack-Datenstruktur.
Die Zeitkomplexität beschreibt, wie sich die benötigte Ausführungszeit für einen Algorithmus ändert, wenn sich die Menge der Eingabedaten verändert.
Grundsätzlich ist die Zeitkomplexität eines Algorithmus immer abhängig von der Implementierung des Entwicklers. Bei den Stack-Operationen pop, push und peek ist eine konstante Zeitkomplexität möglich, d.h. ihre Laufzeit ändert sich nicht mit der Menge an Elementen im Stack.
Das lässt sich auch logisch leicht nachvollziehen: Dem Stack ist es egal, wie viele Elemente sich in der Tiefe der Datenstruktur befinden. Laut LIFO-Prinzip kann er ohnehin nur die oberste Position ansteuern.
In gängigen Frameworks ist normalerweise eine Implementierung der Stack-Datenstruktur bereits vorhanden. Als Beispiele sollen im Folgenden die Java- und C#-Implementierungen dienen.
In Java gibt es bereits die Klasse java.util.Stack, welche den Stack Datentyp implementiert. Laut Java-Dokumentation sollten Entwickler diese Klasse allerdings nicht mehr verwenden und stattdessen auf eine Implementierung der Deque-Schnittstelle zurückgreifen.
In Java lässt sich ein Stack am einfachsten mit der ArrayDeque-Klasse und ihren Methoden addFirst(e), removeFirst() und getFirst() implementieren.
Die Queue ist eine andere häufig verwendete Datenstruktur, für die in Java die Schnittstelle Queue im Namensraum java.util.queue existiert. Die Implementierung einer Queue-Klasse lässt sich wie beim Stack ebenfalls leicht über die ArrayDeque-Klasse realisieren.
Die Queue ist dem Stack sehr ähnlich, nur dass die vordersten Elemente wie bei einer Warteschlange im echten Leben zuerst an der Reihe sind. Damit funktioniert die Queue im Gegensatz zum Stack nach dem FIFO-Prinzip: Was zuerst reinkommt, kommt auch zuerst wieder raus.
Die C# Stack-Implementierung befindet sich im Namensraum System.Collections.Generic. Die nicht-generische Implementierung unter System.Collections soll laut Microsoft-Dokumentation nicht mehr verwendet werden.
In C# ist der Stack als Array implementiert. Diese Art der Implementierung wollen wir uns als nächstes ansehen.
Das Java-Framework bietet zwar eine Stack Implementierung an, wie wir gesehen haben. Es lohnt sich aber, zur Übung selbst einen Stack mit einem Array zu implementieren.
Die folgende Implementierung verwendet eine feste Array-Größe, und somit ist auch die Menge an Elementen im Stack darauf begrenzt. Außerdem verzichtet die Implementierung der Einfachheit halber auf die Überprüfung, ob der Zugriff auf das Array in einer Methode valide ist oder ob eine Exception geworfen werden sollte.
public class Stack { private Object[] elements; private int count; public Stack(int capacity) { // Array initialisieren elements = new Object[capacity]; } public void push(Object item) { // Element on top hinzufügen elements[count] = item; // Top Zeiger hochzählen count++; } public Object pop() { // Oberstes Element nehmen Object item = elements[count - 1]; // Im Array die Position auf null setzen elements[count - 1] = null; // Top Zeiger runterzählen count--; return item; } public Object peek() { // Oberstes Element nehmen und zurückgeben Object item = elements[count - 1]; return item; } }
Eine rekursiv implementierte Methode ruft sich immer wieder selbst auf, bis das gewünschte Ergebnis errechnet ist. Dadurch wird diese Methode durch das Programm mehrfach auf dem Call Stack abgelegt.
Als Beispiel soll uns hier die rekursive Berechnung der Fakultät dienen:
public static void main(String[] args) { fakultaet(4); } long fakultaet(int n) { if (n > 1) { return fakultaet(n - 1); } return 1; }
Die Methode fakultaet(int) ist rekursiv implementiert. Wie wird sich der Aufruf von fakultaet(4) nun im Call Stack widerspiegeln?
Stack-Ebene | Methodenaufruf |
1 (top) | fakultaet(1) |
2 | fakultaet(2) |
3 | fakultaet(3) |
4 | fakultaet(4) |
5 | main(String[]) |
Wenn Du den Programmablauf durchgehst, erkennst Du, dass der letzte Aufruf fakultaet(1) ist. Dieser bildet somit das oberste Element im Stack. Bei dem Rücksprung zum Aufrufer wird der Stack dann Element für Element wieder aufgelöst.
In der Informatik ist der Stack eine Datenstruktur, bei der nur das oberste Element entnommen und ein neues Element nur ganz oben abgelegt werden kann. Das nennt sich LIFO-Prinzip.
Unter Stack versteht man in der Informatik eine Datenstruktur, die eine spezielle Form der linearen Liste ist.
Ein Stack beinhaltet eine beliebige Anzahl an Elementen. Es kann jedoch nur das oberste Element abgerufen, und lediglich oben eins abgelegt werden.
Stack werden oft dort verwendet, wo Daten nur temporär gespeichert werden müssen. Beispiele sind der Call Stack einer Anwendung, oder die Rückwärts-Navigation in einem Browser.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.