Stack verstehen und programmieren

Lernziele

Nach diesem Kapitel kannst du:

• das LIFO-Prinzip erklären und von FIFO unterscheiden,
• die Stack-Methoden push, pop, top und isEmpty anwenden,
• den Zustand eines Stacks nach mehreren Operationen korrekt vorhersagen,
• Queue und Stack an einem konkreten Beispiel vergleichen,
• eine Fachklasse mit Stack implementieren (Rangierbahnhof).

Leitfrage: Wie speicherst du Aktionen so, dass immer der letzte Schritt zuerst rückgängig gemacht werden kann?

Dein Lernweg

A1, A2 und der Kompetenzcheck gelten für alle. Wähle genau eine Programmieraufgabe: Rangierbahnhof A3, Browser A4 oder Klammerprüfung im Transfer. Wer sicher ist, kann direkt dort beginnen; die Fading-Aufgaben sind Hilfen. Shop-Protokoll und Stack-mit-Queue sind optional. Danach folgt das eigene Kleinprojekt.

Mermaid-Diagramm wird geladen…

Arbeitsweise: Abruffragen und Kompetenzchecks beantwortest du zuerst allein ohne Unterlagen und KI. Speichere deine eigene Antwort, bevor du die Rückmeldung öffnest. Im Übungsteil darfst du Hilfen nutzen; nenne anschließend, welche Hilfe du gebraucht hast. Bei jedem Programm: erst erwartete Ausgabe und einen Leerfall notieren, dann ausführen und vergleichen.

Voraussetzungen

Phase 1: Einstieg — Undo braucht LIFO, nicht FIFO

Das Undo-Problem

Du baust eine Undo-Funktion für ein Zeichenprogramm. Aktionen werden gespeichert: Neue Datei, Zeichenstift, Farbeimer.

Exploration – 3 Minuten ohne KI: Welche Aktion muss beim ersten und zweiten Undo zurückgenommen werden? Zeichne einen Speicher und begründe, wo Aktionen hinzugefügt und entfernt werden. Erst danach weiterlesen.

Phase 2: Konzeptaufbau — Stack und Rangierbahnhof

Abruf 2 – ohne Nachlesen: Welche Aktion wird bei Undo zuerst zurückgenommen? Wie unterscheidet sich das vom FIFO-Prinzip? Was muss ein erhaltender Queue-Durchlauf wiederherstellen?

Beim folgenden Beispiel ohne KI: Sage das Ergebnis vorher. Erkläre anschließend einer anderen Person, welche Zeile die Datenstruktur verändert. Erst dann ausführen.

2.1 Stack: Alles passiert oben

Queue vs. Stack — gleiche Eingabe, andere Reihenfolge

Sage vorher: Was gibt jede Datenstruktur aus?

Ruhige Sicherung: Gleiche Daten, andere Ordnung

Undo-Simulation

2.2 Stack programmieren: Rangierbahnhof

Eine Fachklasse Bahnhof hat mehrere Stacks (Gleise). Waggons werden nach Farbe gruppiert. Der vorhandene Methodenname sortiereNachGleis2 meint diese Gruppierung, keine Sortierung nach Größe oder Alphabet.

Mermaid-Diagramm wird geladen…

Reflexionsfrage: Warum hat ein Stack nur head und kein tail — im Gegensatz zur Queue?

Code-Pattern

// Sicher ein Element entnehmen
if (!s.isEmpty())
{
    Typ x = s.top();  // Ansehen
    s.pop();          // Entfernen
    // x weiterverarbeiten
}

Zwei Mini-Checks vor der Übung

1. Ein Stack enthält oben A, darunter B. Was liefert zweimal top()?

2. Nach einmaligem vollständigem Umschütten auf einen Hilfsstack: gleiche Reihenfolge?

Fading – Hilfen nach Bedarf

Hilfen zur gewählten Anwendung

Phase 3: Üben

Abgabe-Aufgaben

push("A")  // → Stack: ?
push("B")  // → Stack: ?
push("C")  // → Stack: ?
top()      // → gibt ? zurück, Stack: ?
pop()      // → Stack: ?
push("D")  // → Stack: ?

Kompetenzcheck – allein, 8–10 Minuten (Pflicht)

Beantworte die drei Aufgaben ohne Vorlage, Ausführen oder KI. Speichere deine erste Antwort vor dem Vergleich. Eine Partnerlösung ersetzt deine Antwort nicht.

1. Ein Stack erhält A, B, C. Danach folgen top(), pop(), push(D). Nenne die Rückgabe von top und den Endzustand (oben links).
2. Wähle für Druckaufträge und das Rücknehmen von Zeichenaktionen jeweils Queue oder Stack und begründe die Zugriffsregel. Zeichne zusätzlich eine verkettete Stack-Umsetzung mit head und next.
3. Was liefern beziehungsweise bewirken top() und pop() auf dem leeren NRW-Stack? Wie entnimmst du ein Element so, dass du es anschließend noch verarbeiten kannst?

Neuer Versuch nach gezielter Übung

Stack: push(P), push(Q), pop(), push(R). Gib die Entnahmereihenfolge an und erkläre, weshalb pop nicht direkt an eine String-Variable zugewiesen werden darf.

Phase 4: Transfer und Vernetzung

Transferaufgabe

Ohne KI: Plane zuerst 4 Minuten deinen Algorithmus und einen Fehlerfall. Du bearbeitest diese Aufgabe nur, wenn du sie als Programmierweg gewählt hast.

Wahlübung: Aktionsprotokoll für einen Warenkorb

Vernetzung

Heute gelöst: Du kennst jetzt beide Grundprinzipien: FIFO bei der Queue und LIFO beim Stack. Du kannst erklären, warum Undo, Browser-Zurück und Rangieren nicht mit einer Queue gelöst werden sollten.

Noch offen: Bisher war der Stack vor allem ein Speicher für letzte Aktionen. Interessant wird er, wenn er nicht nur speichert, sondern beim Denken hilft: beim Sortieren, Zurückgehen und systematischen Suchen.

Nächster Schritt: In Meine Mini-Welt entscheidest du selbst, wie Queue und Stack zusammenarbeiten. Danach kannst du Sortieren und Backtracking vertiefen.

Reflexion

Selbstdiagnose

• Ich kann LIFO erklären und von FIFO unterscheiden.
• Ich kann den Zustand eines Stacks nach mehreren Operationen vorhersagen.
• Ich kann eine Fachklasse mit Stack implementieren.

Partnerprüfung oder Solo-Erklärung (5 Minuten)

Erkläre 2 Minuten lang deine gewählte Methode. Dein Gegenüber prüft einen Randfall und fragt: „Warum bleibt die Reihenfolge hier erhalten oder ändert sich?“ Wechselt dann die Rollen. Allein: Schreibe die Erklärung und beantworte dieselbe Frage schriftlich. Vergleiche mit dem passenden Beispiel und verbessere einen unklaren Satz.

Selbstdiagnose: Welchen Ablauf, welche Begründung und welchen Randfall kannst du ohne Hilfe erklären? Nenne jeweils eine konkrete Aufgabe als Beleg. Wie sicher bist du (1–5)? Bei 1–2 bearbeitest du eine passende Hilfe und den neuen Versuch; bei 4–5 wählst du eine eigene Erweiterung.