Stapel: Unterschied zwischen den Versionen

In der Informatik bezeichnet ein '''Stapelspeicher''' oder '''Kellerspeicher''' (kurz ''Stapel'' oder ''Keller'', häufig auch mit dem englischen Fachbegriff '''Stack''' bezeichnet) eine fundamentale, dynamische Datenstruktur[cite: 3]. Sie dient der Zwischenspeicherung von Datenobjekten in einer strikten Reihenfolge.

Objekte der abstrakten Datenstruktur <code>Stack</code> verwalten beliebige Elemente nach dem '''LIFO-Prinzip''' (''Last-In-First-Out''). Das bedeutet: Das Element, welches als letztes auf den Stapel gelegt wurde, wird als erstes wieder entnommen.

[[Datei:image_90523e.png|mini|Veranschaulichung des LIFO-Prinzips mittels Push- und Pop-Operationen auf einem Stapel]]

Ein Kellerspeicher lässt sich anschaulich mit einem Stapel von Umzugskisten vergleichen. Es kann immer nur eine neue Kiste oben auf den Stapel gepackt werden (dies entspricht der Operation <code>push</code>). Ebenso kann immer nur die oberste Kiste heruntergenommen werden (entspricht der Operation <code>pop</code>). Der lesende oder schreibende Zugriff ist im Regelfall streng auf das oberste Element des Stapels beschränkt. Ein Hinzufügen oder Entfernen einer Kiste weiter unten im Stapel ist strukturell nicht möglich.

Im Kontext der objektorientierten Programmierung wird die abstrakte Datenstruktur formal über eine wohldefinierte Schnittstelle abgebildet[cite: 3]. Ein Stapel verfügt über die folgenden Methoden und Konstruktoren:

** Das zuletzt eingefügte (oberste) Objekt wird von dem Stapel entfernt. Falls der Stapel bereits leer ist, bleibt er unverändert.

** Die Anfrage liefert das oberste Stapelobjekt zurück, ohne es zu entfernen. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird <code>null</code> zurückgegeben.

Eine effiziente Implementierung des Stacks (beispielsweise über eine einfach verkettete Liste, bei der stets vorne am Kopf eingefügt und gelöscht wird) garantiert hochperformante Zugriffszeiten. Dies ist für die informationstechnische Verarbeitung von Datenstrukturen in der beruflichen Praxis essenziell[cite: 4]. Da ausschließlich auf das oberste Element zugegriffen wird, müssen keine iterativen Suchvorgänge durchgeführt oder nachfolgende Elemente im Speicher verschoben werden. Es ergibt sich gemäß der [[Landau-Symbole|Landau-Notation]] folgende Laufzeitkomplexität:

{| class="wikitable"

Die Arbeitsweise und Veränderung des inneren Zustands eines Stacks lässt sich anhand einer sequenziellen Abfolge von Operationen veranschaulichen. In der folgenden Tabelle ist das jeweils oberste Element (Top) der Liste rechts angeordnet.

! Schritt !! Operation !! Zustand des Stacks (Bottom -> Top) !! Erläuterung

| 1. || <code>Stack()</code> || <code>[ ]</code> (leer) || Nach Aufruf der <code>Stack()</code>-Operation ist der Stack initialisiert, enthält aber noch keine Elemente.

| 5. || <code>push(15)</code> || <code>[12, 15]</code> || Nach <code>push(15)</code> besteht der Stack wieder aus zwei Elementen. Die 15 wurde zuletzt gepusht, also liegt sie oben auf dem Stack.

| 6. || <code>push(16)</code> || <code>[12, 15, 16]</code> || Nach <code>push(16)</code> besteht der Stack aus drei Elementen. Wieder ist die zuletzt gepushte Zahl ganz oben im Stack.

Für das tiefergehende Verständnis im Leistungskurs oder der Fachinformatiker-Ausbildung ist nachfolgend eine klassische objektorientierte Implementierung des Stacks auf Basis einer einfach verketteten Liste (Knotenstruktur) dargestellt. Dies schult das exakte, strukturierte algorithmische Denken zur Lösung informationstechnischer Problemstellungen[cite: 3].

     // Innere Knoten-Klasse zur Kapselung der Daten