Flbkwikiadmin am 11. September 2026 um 06:59 Uhr

2026-09-11T06:59:16Z

← Nächstältere Version		Version vom 11. September 2026, 08:59 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	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. Sie dient der temporären Zwischenspeicherung von Datenobjekten in einer streng definierten Reihenfolge und ist ein zentraler Bestandteil der objektorientierten Anwendungsentwicklung~~[cite: 3]~~.		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. Sie dient der temporären Zwischenspeicherung von Datenobjekten in einer streng definierten Reihenfolge und ist ein zentraler Bestandteil der objektorientierten Anwendungsentwicklung.

	Objekte der abstrakten Datenstruktur (ADT) <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.		Objekte der abstrakten Datenstruktur (ADT) <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.

Flbkwikiadmin am 4. September 2026 um 07:41 Uhr

2026-09-04T07:41:28Z

Änderungen zeigen

Flbkwikiadmin: Die Seite wurde neu angelegt: „== Einführung == 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 `Stack` verwalten beliebige Elemente nach dem '''LIFO-Prinzip''' (''Last-…“

2026-09-04T07:39:25Z

Die Seite wurde neu angelegt: „== Einführung == 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-…“

Neue Seite

== Einführung ==
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]]

'''Alltagsanalogie:'''
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.

== Aufbau und Spezifikation (API) ==
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:

=== Konstruktor ===
* <code>Stack()</code>
** Ein neuer, leerer Stapel wird erzeugt.

=== Methoden ===
* <code>boolean isEmpty()</code>
** Die Anfrage liefert den Wert <code>true</code>, wenn der Stapel keine Objekte enthält. Andernfalls liefert sie den Wert <code>false</code>.
* <code>void push(Object pObject)</code>
** Das Objekt <code>pObject</code> wird oben auf den Stapel gelegt. Falls <code>pObject</code> den Wert <code>null</code> hat, bleibt der Stapel unverändert.
* <code>void pop()</code>
** Das zuletzt eingefügte (oberste) Objekt wird von dem Stapel entfernt. Falls der Stapel bereits leer ist, bleibt er unverändert.
* <code>Object top()</code>
** 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.

== Laufzeitanalyse (Komplexität) ==
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"
|-
! Operation !! 1. Best-Case !! 2. Average-Case !! 3. Worst-Case
|-
| <code>push(Object pObject)</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|-
| <code>pop()</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|-
| <code>top()</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|-
| <code>isEmpty()</code> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math> || <math>\mathcal{O}(1)</math>
|}

== Beispiel: Arbeitsweise der Stack-Operationen ==
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.

{| class="wikitable"
|-
! 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.
|-
| 2. || <code>push(12)</code> || <code>[12]</code> || Nach Aufruf von <code>push(12)</code> enthält der Stack genau ein Element, nämlich die Zahl 12.
|-
| 3. || <code>push(8)</code> || <code>[12, 8]</code> || Nach Aufruf von <code>push(8)</code> sind zwei Elemente im Stack enthalten. Die 8 wurde zuletzt hinzugefügt, befindet sich also oben im Stack.
|-
| 4. || <code>pop()</code> || <code>[12]</code> || Wenn <code>pop()</code> aufgerufen wird, wird die 8 wieder entfernt – sie war die zuletzt hinzugefügte Zahl.
|-
| 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.
|}

== Implementierungsbeispiel (Java) ==
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].

<syntaxhighlight lang="java">
public class Stack {

// Verweis auf das oberste Element des Stapels
private Node head;

// Innere Knoten-Klasse zur Kapselung der Daten
private class Node {
Object content;
Node nextNode;

public Node(Object pContent) {
content = pContent;
nextNode = null;
}
}

/**
* Konstruktor: Ein leerer Stapel wird erzeugt.
*/
public Stack() {
head = null;
}

/**
* Prüft, ob der Stapel leer ist.
*/
public boolean isEmpty() {
return head == null;
}

/**
* Legt ein neues Objekt oben auf den Stapel.
*/
public void push(Object pObject) {
if (pObject != null) {
Node newNode = new Node(pObject);
newNode.nextNode = head; // Das neue Element zeigt auf den bisherigen Kopf
head = newNode; // Der Kopf wird auf das neue Element gesetzt
}
}

/**
* Entfernt das oberste Objekt vom Stapel.
*/
public void pop() {
if (!this.isEmpty()) {
head = head.nextNode; // Der Kopf rutscht ein Element nach unten (das alte Top-Element wird vom Garbage Collector entfernt)
}
}

/**
* Liefert das oberste Objekt des Stapels.
*/
public Object top() {
if (this.isEmpty()) {
return null;
} else {
return head.content;
}
}
}
</syntaxhighlight>

[[Kategorie:Programmierung]]
[[Kategorie:AHR I Informatik LK]]
[[Kategorie:FI I SDM]]

Stapel - Versionsgeschichte

Flbkwikiadmin am 11. September 2026 um 06:59 Uhr

Flbkwikiadmin am 4. September 2026 um 07:41 Uhr