Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|
Stack

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…

Von Expert*innen geprüfte Inhalte
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 200 Millionen kostenlose Materialien in unserer App

Stack

Speicher die Erklärung jetzt ab und lies sie, wenn Du Zeit hast.

Speichern
Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

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!

Stack in der Informatik

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“.

Stack Definition

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.

Stack LIFO-Prinzip

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.

  • Push-Operation: Man legt ein neues Element auf den Stapel.
  • Pop-Operation: Man entnimmt das oberste Element vom Stapel.
  • Peek-Operation: Man sieht sich das oberste Element auf dem Stapel an, ohne es jedoch zu entnehmen.

Doch wo wird ein Stack überhaupt in der Praxis verwendet?

Praktische Anwendungen für Stacks

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.

Zeitkomplexität bei Stack-Operationen

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.

Stack in bekannten Frameworks

In gängigen Frameworks ist normalerweise eine Implementierung der Stack-Datenstruktur bereits vorhanden. Als Beispiele sollen im Folgenden die Java- und C#-Implementierungen dienen.

Stack: Java-Implementierung

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.

Java: Stack- und Queue – Vergleich

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.

C# Stack-Implementierung

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.

Java: Array-Stack Implementierung

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;
    }
}

Rekursion und Stack

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-EbeneMethodenaufruf
1 (top)fakultaet(1)
2fakultaet(2)
3fakultaet(3)
4fakultaet(4)
5main(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.

Stack - Das Wichtigste

  • Stack Definition: Der Stack in Informatik ist eine dynamische Datenstruktur.
  • Das Stack-LIFO-Prinzip besagt, dass das zuletzt abgelegte Element zuerst wieder herausgenommen werden muss. (Last-in-first-out)
  • Der Stack in Java besitzt eine Implementierung im Framework, kann aber auch über ein Array selbst implementiert werden. Für den Stack in C# gilt das gleiche.
  • Die Java Stack und Queue Datenstrukturen unterscheiden sich vor allem hinsichtlich dessen, wo ein Element wieder entnommen werden kann.
  • Rekursion und Stack: Bei der Rekursion einer Methode wird diese für jeden Aufruf ein weiteres Mal auf dem Call Stack abgelegt.

Nachweise

  1. Güting; Dieker. (2018). Datenstrukturen und Algorithmen. Springer Vieweg.

Häufig gestellte Fragen zum Thema Stack

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.

Finales Stack Quiz

Stack Quiz - Teste dein Wissen

Frage

Was ist beim Abrufen von Elementen die Besonderheit bei einem Stack?

Antwort anzeigen

Antwort

Ein Element kann nur oben hinzugefügt und nur von oben wieder entnommen werden.

Frage anzeigen

Frage

Was ist eine deutsche Bezeichnung für einen Stack?

Antwort anzeigen

Antwort

Kellerspeicher

Frage anzeigen

Frage

Kann man beim Stack auf tiefer liegende Elemente direkt zugreifen?

Antwort anzeigen

Antwort

Nein

Frage anzeigen

Frage

Wofür steht LIFO?

Antwort anzeigen

Antwort

Last-in-first-out

Frage anzeigen

Frage

Wie heißen die 3 typischen Operationen auf einem Stack?

Antwort anzeigen

Antwort

push, pop, peek

Frage anzeigen

Frage

Wahr oder falsch

Im Java-Framework existiert keine Implementierung für den Stack.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Was ist der Unterschied zwischen Stack und Queue beim Entnehmen von Elementen?

Antwort anzeigen

Antwort

Bei einem Stack wird das Element stets von dort entnommen, wo es abgelegt wird. Bei einer Queue wird das Element von der entgegengesetzten Seite entnommen. 

Frage anzeigen

Frage

Wahr oder falsch

Ein Stack lässt sich über ein Array implementieren.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Wahr oder falsch

Die Stack-Operationen erlauben eine konstante Zeitkomplexität.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Wahr oder falsch

Die Peek-Operation entnimmt das oberste Element vom Stack.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Wahr oder falsch

Der Stack gehört zu den abstrakten Datentypen. 

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

60%

der Nutzer schaffen das Stack Quiz nicht! Kannst du es schaffen?

Quiz starten

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

Kostenloser informatik Spickzettel

Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!

Jetzt anmelden

Finde passende Lernmaterialien für deine Fächer

Alles was du für deinen Lernerfolg brauchst - in einer App!

Lernplan

Sei rechtzeitig vorbereitet für deine Prüfungen.

Quizzes

Teste dein Wissen mit spielerischen Quizzes.

Karteikarten

Erstelle und finde Karteikarten in Rekordzeit.

Notizen

Erstelle die schönsten Notizen schneller als je zuvor.

Lern-Sets

Hab all deine Lermaterialien an einem Ort.

Dokumente

Lade unzählige Dokumente hoch und habe sie immer dabei.

Lern Statistiken

Kenne deine Schwächen und Stärken.

Wöchentliche

Ziele Setze dir individuelle Ziele und sammle Punkte.

Smart Reminders

Nie wieder prokrastinieren mit unseren Lernerinnerungen.

Trophäen

Sammle Punkte und erreiche neue Levels beim Lernen.

Magic Marker

Lass dir Karteikarten automatisch erstellen.

Smartes Formatieren

Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration