den Stack-Sortieralgorithmus mit Hilfsstapeln beschreiben und implementieren,
die Sortierrichtung und die Rolle der Hilfsstapel am Code begründen,
Backtracking als „Versuch mit Zurückgehen" erklären,
einen Backtracking-Algorithmus tracen und den Stack-Zustand zeichnen,
Suchverfahren anhand klar festgelegter Regeln und gezählter Schritte vergleichen.
Leitfrage: Wie löst du Probleme, bei denen du Entscheidungen rückgängig machen musst — und warum ist ein Stack dafür die richtige Wahl?
Dein Lernweg – Vertiefung nach dem Kleinprojekt
GK: Diese Einheit ist Wahlvertiefung. Wähle entweder die Sortierwerkstatt oder die Labyrinthsuche; bearbeite nicht alle Aufgaben. LK: Die Labyrinthsuche mit A2 und dem Kompetenzcheck ist der gemeinsame Kern. Sortieren, Acht Damen und Konfigurator sind zusätzliche Wahlaufgaben nach Absprache. Das ist eine Einstiegseinheit in Backtracking, kein Ersatz für die spätere Vertiefung mit Rekursion.
Für die Sortierwerkstatt: Phase 1, Abschnitt 2.1 und A1/A3. Für die Labyrinthsuche: Abschnitt 2.2, A2 und der Kompetenzcheck. Beginne mit einem eigenen Versuch und nutze Hilfen nur bei Bedarf.
Mermaid-Diagramm
Mermaid-Diagramm wird geladen…
Voraussetzungen
Hinweis
Du solltest push, pop, top und isEmpty aus Stack verstehen sicher anwenden. Für das Labyrinth brauchst du zusätzlich verschachtelte Arrays: feld[y][x] bezeichnet Zeile y und Spalte x; x wächst nach rechts, y nach unten. Zellen haben ganzzahlige Koordinaten ab 0.
Übergang: Vom Speicher zum Denkwerkzeug
Im letzten Kapitel hat der Stack letzte Aktionen gespeichert. push bedeutete: Schritt merken. pop bedeutete: letzten Schritt zurücknehmen.
Jetzt wird daraus mehr als Undo. Wenn man Schritte zurücknehmen kann, kann man systematisch suchen, Sackgassen verlassen und alternative Wege ausprobieren.
Die zentrale Spannung lautet: Wie löst man ein Problem, wenn man nur oben auf den Stapel schauen darf und trotzdem manchmal zurückgehen muss?
Phase 1: Einstieg — Sortieren mit eingeschränktem Zugriff
Hinweis
Retrieval-Check:
Was bedeutet LIFO — und welche Methode entfernt das oberste Element?
Was ist das Umschütt-Pattern?
Textabgabe
Das Sortierproblem
Du hast einen Stack mit den Elementen 3, 1, 4 (oben = 4). Sortiere ihn aufsteigend (kleinstes oben). Du darfst die Stack-Methoden push, pop, top, isEmpty, Vergleiche und eine temporäre Variable verwenden. Skizziere 4 Minuten ohne KI eine Strategie mit einem oder zwei Hilfsstapeln; notiere auch, wo du festhängst.
Tipp
Prüfe deinen Versuch mit Papierkarten. Beim Zurücklegen kann sich die Reihenfolge ändern. Halte nach jedem Zug fest, was bereits geordnet ist.
Phase 2: Konzeptaufbau
Abruf 2 – allein ohne Nachlesen: Was verändert pop, was liefert top? Was passiert nach einmaligem und zweimaligem vollständigem Umschütten eines Stacks? Erkläre den Unterschied zur Queue.
Textabgabe
2.1 Sortieren mit Stacks
Zwei typische Versuche: Einfaches Umschütten kehrt nur die Reihenfolge um; es sortiert nicht. Direktes Ablegen jeder Zahl oben auf einem Hilfsstapel kann dessen Ordnung verletzen. Man muss Platz schaffen, bevor man das neue Element einfügt.
Unsere Strategie: zwei Hilfsstapel. Auf sortiert liegt das kleinste Element oben. Kleinere Elemente werden kurz im Puffer geparkt, dann wird die neue Zahl eingefügt und der Puffer zurückgelegt. Der Hauptstapel wird dabei nur entleert.
Ein Hilfsstapel kann ebenfalls genügen, wenn der Hauptstapel zusätzlich als Zwischenablage dient. Zwei Hilfsstapel sind hier eine Entscheidung für einen übersichtlichen Ablauf, keine mathematische Notwendigkeit.
Ohne KI – vor dem Ausführen: Erwarte für 3,1,4,1,5 die Ausgabe 1 1 3 4 5. Erkläre, warum die Schleife kleinere Elemente beiseitelegt. Bei gleichen Werten darf keiner verloren gehen.
IDE lädt…
Sortier-Pattern
Nimm das oberste Element vom Hauptstapel.
Verschiebe kleinere Elemente vom sortierten Stapel in den Puffer.
Lege das Element auf den sortierten Stapel.
Verschiebe den Puffer zurück.
Wiederhole, bis der Hauptstapel leer ist.
Ruhige Sicherung: Warum Sortieren mit Stack schwerer ist als mit Array
Tipp
Bei einem Array kannst du direkt an Position i springen und Elemente tauschen. Beim Stack geht das nicht.
Beim Stack musst du Ordnung durch Bewegung herstellen:
oben ansehen,
oben entfernen,
passend zwischenlagern,
wieder zurücklegen.
Deshalb braucht der Algorithmus Hilfsstapel. Nicht weil der Code komplizierter sein soll, sondern weil der Zugriff absichtlich eingeschränkt ist.
2.2 Backtracking — Versuch mit Zurückgehen
Idee: Gehe vorwärts, solange es geht. Bei einer Sackgasse: Gehe zurück zum letzten Entscheidungspunkt und probiere eine andere Richtung.
Der Stack speichert den Weg. Push = ein Schritt vorwärts. Pop = ein Schritt zurück.
Mermaid-Diagramm
Mermaid-Diagramm wird geladen…
Erst selbst versuchen – 4 Minuten ohne KI: Zeichne das Gitter. Starte bei (0,0), versuche immer unten, rechts, oben, links. Markiere besuchte Zellen und halte den aktuellen Weg fest. Was machst du bei (0,2), wenn kein neuer Weg weiterführt?
S . . X. X . X. X . ZX X X X
Erwartungs-Check: Zuerst erscheinen Zurück aus (0,2) und Zurück aus (0,1), dann der Weg (0,0) (1,0) (2,0) (2,1) (2,2) (3,2). Erkläre ohne KI vor dem Ausführen den Unterschied zwischen Weg und Besuchsmarkierung.
Beispiel: Labyrinth (4×4 Gitter)
IDE lädt…
Hinweis
Suchaufwand präzise vergleichen: Diese Tiefensuche markiert besuchte Zellen und untersucht jede erreichbare Zelle höchstens einmal als neuen Ort. Der Stack speichert nur den aktuellen Weg; eine besuchte Sackgasse bleibt markiert, auch nachdem sie vom Stack entfernt wurde. Backtracking kann durch frühes Verwerfen ungültiger Teilentscheidungen Arbeit sparen, ist aber nicht immer schneller als jedes andere Suchverfahren. Bei anderen Problemen, etwa Acht Damen, muss man andere Zustände und Konfliktregeln betrachten.
Reflexionsfrage: Warum ist ein Stack (LIFO) für Backtracking besser geeignet als eine Queue (FIFO)?
Atempause ohne neuen Code: Backtracking als Wegbild
Tipp
Bevor du Backtracking programmierst, solltest du es zeichnen können:
Markiere den aktuellen Weg.
Markiere die Sackgasse.
Streiche den letzten Schritt.
Gehe zum letzten Entscheidungspunkt zurück.
Probiere die nächste Möglichkeit.
Wenn du dieses Bild erklären kannst, ist der Code nur noch die Übersetzung davon: push für vorwärts, pop für zurück.
Zwei Mini-Checks
Sortierwerkstatt: Oben liegt auf sortiert die 1, darunter die 4. Die nächste Zahl ist 3. Was muss vor dem Einfügen passieren?
Labyrinth: Eine Sackgasse wurde vom Weg entfernt. Darf sie beim nächsten Schritt als unbesucht gelten?
Fading – nur für deinen gewählten Schwerpunkt
Phase 3: Üben
Hinweis
Retrieval-Check:
Warum nutzt unsere Variante zwei Hilfsstapel? Könnte man auch den Hauptstapel als Zwischenablage verwenden?
Was passiert beim Backtracking, wenn du in einer Sackgasse steckst?
Textabgabe
Abgabe-Aufgaben
A1: Trace — Stack-Sortierung (Wahl, AFB II)
Sortiere den Stack [1, 3, 2, 4] (oben = links) mit dem Sortieralgorithmus. Zeichne den Zustand aller drei Stacks (Haupt, Sortiert, Puffer) nach jedem Schritt.
Tipp
Du kannst den Stack-Zustand als Text (z.B. Haupt: [1, 3, 2, 4], oben = links) oder als Mermaid-Flowchart darstellen. Eine Mermaid-Anleitung findest du im Kapitel Darstellungsformen.
Gegeben ist das 3×3-Gitter (S=Start, Z=Ziel, X=Wand):
S . .
. X .
X X Z
Trace den Backtracking-Algorithmus: Zeichne den Stack-Zustand und die besuchten Felder nach jedem Schritt. Wie viele Felder werden besucht?
Tipp
Du kannst den Stack-Zustand als Text (z.B. Haupt: [1, 3, 2, 4], oben = links) oder als Mermaid-Flowchart darstellen. Eine Mermaid-Anleitung findest du im Kapitel Darstellungsformen.
Textabgabe
A3: Implementierung — Sortierung (Wahl, AFB II)
Implementiere den Stack-Sortieralgorithmus in der OnlineIDE. Teste mit den Werten 5, 2, 8, 1, 9. Erwartete Entnahme: 1, 2, 5, 8, 9. Ergänze Tests für leer, ein Element und doppelte Werte. Notiere die Erwartungen vor dem Ausführen.
IDE lädt…
A4: Suchaufwand und Besuchsmarkierung (optional, AFB III)
Vergleiche zwei genau beschriebene Vorgehensweisen am Gitter aus A2:
a) Unsere Suche markiert besuchte Felder. Wie viele verschiedene Zellen betritt sie einschließlich Start und Ziel? Wie oft geht sie zurück?
b) Ein fehlerhafter Sucher bevorzugt unten, rechts, oben, links, prüft aber nur Grenzen und Wände. Er merkt sich keine besuchten Zellen. Zeige eine sich wiederholende Folge.
c) Welche zusätzliche Regel bräuchte ein fairer Vergleich zweier terminierender Suchverfahren? Erkläre, warum „Backtracking ist immer schneller“ daraus nicht folgt.
Erweitere die Klammerprüfung aus Kap. 03: Der Ausdruck kann jetzt runde (), eckige [] und geschweifte {} Klammern enthalten. Eine schließende Klammer muss zur letzten geöffneten passen.
Skizziere den Algorithmus und teste mit: {[(a+b)*c]-d} (korrekt) und {[(a+b)*c}-d] (falsch).
Textabgabe
Kompetenzcheck – allein, ohne Codeausführung oder KI
Labyrinth-Schwerpunkt / LK-Kern (8–10 Minuten):
Verwende das 3×3-Gitter aus A2. Schreibe push/pop bis zur Lösung auf, jeweils mit Koordinaten. Priorität: unten, rechts, oben, links.
Welche besuchte Zelle gehört am Ende nicht zum Lösungsweg? Begründe, warum sie markiert bleibt.
Ersetze das Ziel durch eine Wand. Wie erkennt das Programm, dass es keinen Weg gibt?
Sortier-Schwerpunkt (8–10 Minuten):
Hauptstapel oben nach unten [2,1,3]. Beschreibe die drei äußeren Schleifendurchläufe unserer Sortierung und den sortierten Endzustand.
Begründe das Vergleichszeichen und die Rolle des Puffers.
Was passiert bei einem leeren Stack und bei [2,2]? Warum bleiben beide gleichen Werte erhalten?
Textabgabe
Neuer Versuch nach gezielter Übung
Labyrinth: Ändere im 3×3-Gitter aus A2 die Zelle (0,1) zur Wand. Gib Weg und Zahl der Rückschritte an. Sortieren: Hauptstapel oben nach unten [3,1,3]. Beschreibe den zweiten und dritten Einfügeschritt und prüfe die Mehrfachwerte.
Textabgabe
Phase 4: Transfer und Vernetzung
Wähle eine Herausforderung: ein eigenes Labyrinth mit nachweisbarer Sackgasse, die erweiterte Klammerprüfung, Acht Damen oder die Konfiguratoranalyse. Skizziere zunächst 5 Minuten ohne KI eine eigene Lösung oder Vermutung. Danach darfst du Hilfen nutzen. Notiere bei eigenem Code zuerst erwartete Ergebnisse und prüfe einen Randfall.
Partnerprüfung (6 Minuten): Erklärt euch je 2 Minuten euren Ablauf; die andere Person sucht je 1 Minute ein Gegenbeispiel. Allein: Schreibe Ablauf und Gegenbeispiel auf und vergleiche anschließend mit dem ausgeführten Programm.
Transferaufgabe
Das Acht-Damen-Problem (optionale Herausforderung, AFB III)
8 Damen auf einem 8×8-Schachbrett so platzieren, dass keine eine andere bedroht. Beschreibe in Pseudocode, wie du mit Backtracking und einem Stack systematisch eine Lösung findest.
Tipp: Platziere in jeder Zeile eine Dame. Der Stack speichert die Spaltenpositionen. Bei Konflikt: pop und nächste Spalte versuchen.
Textabgabe
Wahltransfer: Braucht dieser Produktkonfigurator seinen Stack?
Durchgaengiges Projekt: Online-Shop
Ein Produktkonfigurator prüft Kombinationen. Der folgende Code nutzt drei Schleifen und protokolliert jede Kombination auf einem Stack. Untersuche kritisch, ob dieser Stack die Suche tatsächlich steuert.
Projektstand Online-Shop
Du kennst FIFO und LIFO. Nun prüfst du eine Modellierungsentscheidung anhand ihrer tatsächlichen Wirkung im Programm.
Ein Stack im Quellcode macht eine Enumeration noch nicht zu einer stackgesteuerten Suche. Ein geeigneter Test ist: Ändert sich die Suche, wenn man die Stack-Operationen entfernt?
Online-Shop: Produktkonfigurator
Ein Kunde konfiguriert ein T-Shirt in drei Schritten:
Farbe: Rot, Blau, Gruen
Groesse: S, M, L
Material: Baumwolle, Polyester
Nicht alle Kombinationen sind lieferbar. Die Schleifen probieren trotzdem alle 18 Kombinationen aus. Erst die vollständige Kombination wird geprüft.
Der Stack protokolliert die gerade geprüfte Kombination. Nach jeder Kombination wird er geleert, auch bei einem Treffer.
Studiere den Code, fuehre ihn aus und beantworte:
Welche Kombination ist zuerst verfügbar? Wie viele Kombinationen werden geprüft und wie viele sind verfügbar?
Entferne im Editor die Stack-Erzeugung sowie push/pop. Bleiben verfügbare Kombinationen und Reihenfolge gleich? Begründe.
Skizziere, wie eine Suche mit frühen Konfliktprüfungen den Zweig Rot/L vor der Materialwahl verwerfen könnte. Welche Entscheidung müsste gespeichert werden, um später die nächste Alternative zu versuchen?
IDE lädt…
Textabgabe
Vernetzung
Heute gelöst: Du hast gesehen, dass ein Stack nicht nur Aktionen speichert. Er kann Algorithmen steuern: Sortieren mit eingeschränktem Zugriff und Backtracking bei Sackgassen.
Noch offen: Queue und Stack sind absichtlich blind. Die Queue sieht nur vorne, der Stack nur oben. Das macht sie klar, aber für viele alltägliche Aufgaben unbequem: Was, wenn du gezielt in der Mitte arbeiten willst?
Nächster Schritt: Die List öffnet diese Einschränkung. Sie erlaubt sequenziellen Zugriff über einen Cursor. Damit kommt mehr Freiheit, aber auch mehr Verantwortung.
Reflexion
Hinweis
Beantworte die Leitfrage: Warum ist ein Stack die richtige Datenstruktur, wenn du Entscheidungen rückgängig machen musst? Erkläre am Beispiel Backtracking.
Textabgabe
Selbstdiagnose
Ich kann den Stack-Sortieralgorithmus beschreiben und implementieren.
Ich kann Backtracking erklären und den Stack-Zustand tracen.
Ich kann die Rolle der Hilfsstapel und die Sortierrichtung begründen.
Ich kann Suchaufwand unter ausdrücklich genannten Regeln vergleichen.
Reflexion: Welche deiner ursprünglichen Vermutungen hat der Test bestätigt oder widerlegt? Nenne eine korrigierte Aussage. Bewerte deine Sicherheit von 1–5 und plane eine gezielte Wiederholung bei 1–2.
