Stacks und Queues

Aktives Lernen durch Simulation und Wettbewerb fördert das Verständnis von Stacks und Queues, weil die Schülerinnen und Schüler die abstrakten Konzepte direkt erleben und anwenden. Durch körperliche Bewegung und kollaborative Aufgaben wird das algorithmische Denken greifbar und bleibt nachhaltig im Gedächtnis verankert.

• Klasse 12
• Informatik Oberstufe: Von Algorithmen zur vernetzten Gesellschaft
• 3 Aktivitäten
• 20 Min.–60 Min.

Lernziele

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

Planspiel

⏱ 40 Min.·Ganze Klasse

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.

Vorbereitung & Details

Vergleichen Sie die Prinzipien von Stacks und Queues und identifizieren Sie typische Anwendungsfälle.

Moderationstipp: Lassen Sie die Schülerinnen und Schüler beim 'Sortier-Algorithmen-Tanz' die Schritte von Bubblesort und Quicksort bewusst nachvollziehen, um die Unterschiede in der Verarbeitungsgeschwindigkeit zu spüren.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Forschungskreis

⏱ 60 Min.·Kleingruppen

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.

Vorbereitung & Details

Erklären Sie, wie ein Stack zur Überprüfung von Klammerausdrücken verwendet werden kann.

Moderationstipp: Geben Sie beim 'Sortier-Wettbewerb' klare Zeitlimits vor, damit die Teams ihre Strategien priorisieren und nicht in unproduktiven Diskussionen verharren.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Ich-Du-Wir (Denken-Austauschen-Vorstellen)

⏱ 20 Min.·Partnerarbeit

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.

Vorbereitung & Details

Entwerfen Sie eine Lösung für ein Problem, das die FIFO-Eigenschaft einer Queue nutzt.

Moderationstipp: Fordern Sie die Schülerinnen und Schüler im 'Think-Pair-Share' auf, ihre Argumente für die Binärsuche mit konkreten Zahlenbeispielen zu untermauern.

Setup: Standard-Klassenzimmer; die Lernenden wenden sich dem Sitznachbarn zu

Materials: Diskussionsimpuls (projiziert oder gedruckt), Optional: Notizblatt für die Partnerarbeit

• Verstehen
• Anwenden
• Analysieren
• Selbstwahrnehmung
• Beziehungsfähigkeit

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit einfachen, alltagsnahen Beispielen wie einem Stapel Teller oder einer Warteschlange an der Kasse, um die Konzepte einzuführen. Wichtig ist, dass die Schülerinnen und Schüler zunächst die Prinzipien 'Last-In-First-Out' und 'First-In-First-Out' selbstständig formulieren. Vermeiden Sie es, zu früh auf Implementierungsdetails einzugehen – der Fokus sollte zunächst auf dem Verständnis der Struktur und ihrer Eignung für Anwendungen liegen.

Was Sie erwartet

Erfolgreiches Lernen zeigt sich darin, dass die Schülerinnen und Schüler erklären können, warum bestimmte Datenstrukturen für gegebene Probleme geeignet sind. Sie erkennen die Unterschiede zwischen Stacks und Queues in realen Anwendungsszenarien und können diese mit konkreten Operationen verknüpfen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während des 'Sortier-Algorithmen-Tanzes' könnte die Annahme entstehen, dass Quicksort immer der schnellste Sortieralgorithmus ist.

Was Sie stattdessen lehren sollten

Nutzen Sie die Gelegenheit, um mit den Schülerinnen und Schülern gezielt Worst-Case-Szenarien zu simulieren, z.B. eine bereits sortierte Liste, und beobachten Sie gemeinsam, wie Quicksort im Vergleich zu Mergesort abschneidet.

Häufige Fehlvorstellung

Beim 'Sortier-Wettbewerb' könnte die Meinung aufkommen, dass Sortieren nur für die bessere Lesbarkeit von Listen wichtig ist.

Was Sie stattdessen lehren sollten

Lenken Sie die Diskussion auf die Vorbereitung für effiziente Suchverfahren und lassen Sie die Teams berechnen, wie viel Zeit sie durch das Sortieren im Vergleich zur sequenziellen Suche sparen.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach dem 'Sortier-Algorithmen-Tanz' geben Sie den Schülerinnen und Schülern eine Liste von Operationen vor und fragen sie: 'Ist dies die Beschreibung einer Stack- oder Queue-Operation? Begründen Sie kurz.'

Lernstandskontrolle

Nach dem 'Sortier-Wettbewerb' erhalten die Schülerinnen und Schüler eine Karte mit einem Problem wie 'Rückgängig-Funktion in einem Texteditor'. Sie schreiben auf die Karte: 'Diese Anwendung nutzt am besten einen Stack, weil...' oder 'Diese Anwendung nutzt am besten eine Queue, weil...'.

Diskussionsfrage

Während der Diskussion über Stacks und Queues stellen Sie die Frage: 'Stellen Sie sich vor, Sie entwickeln ein System zur Verwaltung von Notrufen. Welche Datenstruktur wäre für die Reihenfolge der Bearbeitung besser geeignet und warum? Welche Probleme könnten bei der Wahl der 'falschen' Struktur auftreten?'

Erweiterungen & Unterstützung

• Fordern Sie schnelle Schülerinnen und Schüler auf, die Effizienz der Algorithmen mit selbstgewählten Datenmengen zu testen und die Ergebnisse grafisch darzustellen.
• Bei Schülerinnen und Schülern mit Schwierigkeiten wiederholen Sie die Grundlagen mit physischen Gegenständen wie Büchern für einen Stack oder Kaffeebechern für eine Queue.
• Vertiefen Sie die Thematik mit einer Analyse, wie Stacks und Queues in Betriebssystemen oder bei der Verwaltung von Prozessen eingesetzt werden.

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.