Informatik · Klasse 12 · Datenstrukturen und Algorithmen · 1. Halbjahr

Stacks und Queues

Die Schülerinnen und Schüler implementieren und analysieren die Funktionsweise von Stacks (LIFO) und Queues (FIFO) und deren Anwendungen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Strukturieren und Vernetzen
• KMK: Sekundarstufe II - Modellieren und Implementieren

Über dieses Thema

Sortier- und Suchverfahren sind die klassischen Anwendungsbeispiele für algorithmisches Denken. In der Oberstufe vertiefen Schüler ihr Wissen über effiziente Verfahren wie Quicksort und Mergesort und vergleichen sie mit einfacheren Methoden wie Bubblesort. Dabei steht das Prinzip 'Divide and Conquer' (Teile und Herrsche) im Mittelpunkt, das eine fundamentale Strategie der Informatik darstellt. Die KMK-Standards fordern hier die Kompetenz zum 'Modellieren und Implementieren', da die Lernenden diese Algorithmen nicht nur verstehen, sondern auch in Code umsetzen müssen.

Ein weiterer Schwerpunkt ist die binäre Suche, die die Bedeutung sortierter Daten unterstreicht. Schüler lernen, dass die Wahl des richtigen Algorithmus oft von der Struktur der Eingangsdaten abhängt. Dieses Thema eignet sich hervorragend für handlungsorientierten Unterricht, bei dem Algorithmen physisch nachgespielt werden. Durch das 'Tanzen' oder 'Legen' von Sortierfolgen werden die oft komplexen Vertauschungs- und Teilungsschritte transparent und logisch nachvollziehbar.

Leitfragen

1. Vergleichen Sie die Prinzipien von Stacks und Queues und identifizieren Sie typische Anwendungsfälle.
2. Erklären Sie, wie ein Stack zur Überprüfung von Klammerausdrücken verwendet werden kann.
3. Entwerfen Sie eine Lösung für ein Problem, das die FIFO-Eigenschaft einer Queue nutzt.

Lernziele

• Vergleichen Sie die Funktionsweise von Stacks (LIFO) und Queues (FIFO) hinsichtlich ihrer Zugriffsprinzipien und Effizienz.
• Analysieren Sie die Eignung von Stacks für die Überprüfung der korrekten Verschachtelung von Klammern in mathematischen oder Programmierungsausdrücken.
• Entwerfen Sie eine Implementierung einer Queue zur Simulation von Warteschlangenszenarien, z.B. bei der Bearbeitung von Druckaufträgen.
• Demonstrieren Sie die Anwendung eines Stacks zur Verwaltung von Funktionsaufrufen und Rücksprungadressen in einem einfachen Programmablauf.
• Bewerten Sie die Vorteile der Verwendung von Stacks oder Queues gegenüber einfachen Listen für spezifische algorithmische Probleme.

Bevor es losgeht

Grundlagen der Programmierung: Variablen und Datentypen

Warum: Schüler müssen grundlegende Datentypen verstehen, um die Elemente, die in Stacks und Queues gespeichert werden, handhaben zu können.

Kontrollstrukturen: Schleifen und Bedingungen

Warum: Die Implementierung und Nutzung von Stacks und Queues erfordert das Verständnis von Schleifen zur Iteration und Bedingungen zur Überprüfung von Zuständen (z.B. ob ein Stack leer ist).

Einführung in Algorithmen

Warum: Ein grundlegendes Verständnis von Algorithmen ist notwendig, um die Funktionsweise und die Effizienz von Stack- und Queue-Operationen bewerten zu können.

Schlüsselvokabular

Stack (LIFO)	Eine Datenstruktur, die nach dem Last-In, First-Out (LIFO) Prinzip arbeitet. Das zuletzt hinzugefügte Element ist das erste, das entfernt wird.
Queue (FIFO)	Eine Datenstruktur, die nach dem First-In, First-Out (FIFO) Prinzip arbeitet. Das zuerst hinzugefügte Element ist das erste, das entfernt wird.
Push	Die Operation, ein Element auf den Stack zu legen. Dies geschieht am 'oberen' Ende des Stacks.
Pop	Die Operation, das oberste Element vom Stack zu entfernen und zurückzugeben. Nur bei einem nicht-leeren Stack möglich.
Enqueue	Die Operation, ein Element am 'hinteren' Ende der Queue hinzuzufügen.
Dequeue	Die Operation, das vorderste Element aus der Queue zu entfernen und zurückzugeben. Nur bei einer nicht-leeren Queue möglich.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Quicksort ist immer der schnellste Sortieralgorithmus.

Was Sie stattdessen lehren sollten

Im schlimmsten Fall (Worst Case) kann Quicksort auf O(n²) abfallen, während Mergesort stabil bei O(n log n) bleibt. Durch gezieltes Testen mit 'ungünstigen' Datenmengen im Unterricht entdecken Schüler diese Nuancen selbst.

Häufige Fehlvorstellung

Sortieren ist nur wichtig, damit Menschen Listen besser lesen können.

Was Sie stattdessen lehren sollten

Sortieren ist oft die notwendige Vorbereitung für andere effiziente Algorithmen, wie die binäre Suche. In Projekten erkennen Schüler, dass die Rechenzeit für das Sortieren durch die spätere Zeitersparnis beim Suchen oft vielfach wettgemacht wird.

Ideen für aktives Lernen

Planspiel: Sortier-Algorithmen-Tanz

Schüler erhalten Karten mit Zahlen und müssen sich nach den Regeln von Quicksort oder Mergesort sortieren. Ein Moderator gibt die algorithmischen Schritte vor, während die Schüler die Positionen tauschen und Gruppen bilden.

40 Min.·Ganze Klasse

Forschungskreis: Der Sortier-Wettbewerb

In Kleingruppen implementieren Schüler verschiedene Sortierverfahren und testen sie mit unterschiedlichen Datensätzen (bereits sortiert, umgekehrt sortiert, zufällig). Sie dokumentieren, welcher Algorithmus in welcher Situation gewinnt.

60 Min.·Kleingruppen

Ich-Du-Wir (Denken-Austauschen-Vorstellen): Warum ist Binärsuche so schnell?

Schüler vergleichen das Suchen in einem unsortierten Stapel Karten mit der Suche in einem sortierten Stapel durch ständiges Halbieren. Sie diskutieren zu zweit den Aufwand des Sortierens im Verhältnis zum Nutzen der schnellen Suche.

20 Min.·Partnerarbeit

Bezüge zur Lebenswelt

• In Webbrowsern wird die 'Zurück'-Funktion oft mittels eines Stacks implementiert. Jeder besuchte Link wird auf den Stack gelegt, und beim Drücken von 'Zurück' wird das oberste Element (die letzte Seite) vom Stack genommen und angezeigt.
• Druckersysteme verwenden häufig Queues, um Druckaufträge zu verwalten. Jeder Auftrag wird hinten in die Queue gestellt und in der Reihenfolge seiner Ankunft (FIFO) abgearbeitet, um Fairness zu gewährleisten.
• Die Verwaltung von Funktionsaufrufen und Rücksprungadressen in Programmiersprachen nutzt die Stack-Struktur. Wenn eine Funktion eine andere aufruft, wird die Rücksprungadresse auf den Stack gelegt, um nach Beendigung der aufgerufenen Funktion dorthin zurückkehren zu können.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Stellen Sie den Schülern eine Liste von Operationen (z.B. 'Element A hinzufügen', 'Element B entfernen', 'Element C hinzufügen', 'Element A entfernen') und fragen Sie: 'Ist dies die Beschreibung einer Stack- oder einer Queue-Operation? Begründen Sie kurz.'

Lernstandskontrolle

Geben Sie jedem Schüler eine Karte mit einer kurzen Beschreibung eines Problems (z.B. 'Rückgängig-Funktion in einem Texteditor', 'Bearbeitung von Anfragen an einen Webserver'). Die Schüler schreiben auf die Karte: 'Diese Anwendung nutzt am besten einen Stack, weil...' oder 'Diese Anwendung nutzt am besten eine Queue, weil...'.

Diskussionsfrage

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie entwickeln ein System zur Verwaltung von Notrufen. Welche Datenstruktur (Stack oder Queue) wäre für die Reihenfolge der Bearbeitung besser geeignet und warum? Welche Probleme könnten bei der Wahl der 'falschen' Struktur auftreten?'

Häufig gestellte Fragen

Was ist das Prinzip 'Divide and Conquer'?

Es ist eine Strategie, bei der ein großes Problem in kleinere Teilprobleme zerlegt wird, bis diese einfach zu lösen sind. Die Teillösungen werden dann zur Gesamtlösung kombiniert. Mergesort ist das Paradebeispiel: Liste teilen, Teillisten sortieren, sortierte Listen mischen.

Warum wird Bubblesort in der Schule gelehrt, wenn es ineffizient ist?

Bubblesort ist didaktisch wertvoll, um das Grundprinzip des Vergleichens und Vertauschens sowie einfache Schleifenstrukturen zu verstehen. Es dient als perfekter Kontrast, um die enorme Effizienzsteigerung durch fortgeschrittene Verfahren wie Quicksort zu verdeutlichen.

Wie kann man Mergesort ohne Computer visualisieren?

Mit Spielkarten lässt sich Mergesort wunderbar darstellen. Man teilt den Stapel immer wieder in zwei Hälften, bis man nur noch einzelne Karten hat, und fügt diese dann paarweise in der richtigen Reihenfolge wieder zusammen. Das macht den rekursiven Prozess begreifbar.

Welche Rolle spielt die Stabilität bei Sortieralgorithmen?

Ein stabiler Sortieralgorithmus behält die relative Reihenfolge von Elementen mit gleichem Schlüssel bei. Das ist wichtig, wenn man Daten nach mehreren Kriterien nacheinander sortiert (z.B. erst nach Vorname, dann nach Nachname). Mergesort ist stabil, Quicksort in der Standardform nicht.