Datenstrukturen: Stacks und Queues

Aktive Methoden ermöglichen es Schülern, die abstrakten Konzepte von Stacks und Queues durch eigenes Handeln zu begreifen. Die Kombination aus physischen Simulationen und praktischer Implementierung fördert ein tiefes Verständnis der LIFO- und FIFO-Prinzipien, das durch reines Zuhören oder Lesen nicht erreicht werden kann.

• Klasse 11
• Informatik in der Oberstufe: Algorithmen, Daten und Gesellschaft
• 4 Aktivitäten
• 25 Min.–50 Min.

Lernziele

1. Erklären Sie das LIFO-Prinzip anhand eines konkreten Beispiels und identifizieren Sie dessen Anwendung in einem Software-Kontext.
2. Beschreiben Sie das FIFO-Prinzip mit einer Alltagsanalogie und nennen Sie zwei Anwendungsfälle in der Informatik.
3. Vergleichen Sie die Vor- und Nachteile der Implementierung eines Stacks mittels eines Arrays gegenüber einer verketteten Liste in Bezug auf Speicherplatz und Effizienz.
4. Entwerfen Sie eine einfache Simulation einer Warteschlange (Queue) unter Verwendung einer Liste in einer gewählten Programmiersprache.

Planspiel

⏱ 45 Min.·Kleingruppen

Kartenrotation: Stack- und Queue-Simulation

Teilen Sie Karten mit Zahlen an Gruppen aus. An Station 1 bauen Schüler einen Stack (LIFO) und entnehmen Elemente. An Station 2 simulieren sie eine Queue (FIFO). Nach 10 Minuten pro Station notieren sie Operationen und diskutieren Unterschiede.

Vorbereitung & Details

Erklären Sie die Funktionsweise eines Stacks und einer Queue anhand von Alltagsbeispielen.

Moderationstipp: Stellen Sie sicher, dass alle Schüler in der Kartenrotation abwechselnd die Rolle des 'Stacks' und der 'Queue' übernehmen, um beide Prinzipien aktiv zu erleben.

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

Planspiel

⏱ 50 Min.·Partnerarbeit

Pair-Programming: Array-Implementierung

In Paaren implementieren Schüler einen Stack mit einem Array in Python, inklusive push und pop. Anschließend tauschen sie Code mit einer anderen Paarung und testen Queues. Abschließende Reflexion zu Overflow-Problemen.

Vorbereitung & Details

Analysieren Sie, in welchen Anwendungsbereichen Stacks und Queues besonders nützlich sind.

Moderationstipp: Fordern Sie die Pair-Programming-Paare auf, ihre Implementierungen gegenseitig zu testen und Grenzfälle wie einen leeren Stack oder eine volle Queue zu simulieren.

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

Planspiel

⏱ 30 Min.·Ganze Klasse

Ganzklasse-Diskussion: Alltagsanwendungen

Schüler listen 5 Alltagsbeispiele für Stacks und Queues auf Flipcharts. Die Klasse stimmt ab und kategorisiert sie. Gemeinsam skizzieren sie Pseudocode für eine Anwendung.

Vorbereitung & Details

Vergleichen Sie die Implementierung von Stacks und Queues mithilfe von Arrays oder Listen.

Moderationstipp: Lenken Sie die Ganzklasse-Diskussion gezielt auf Alltagsbeispiele, die die Schüler selbst nennen, um die Relevanz der Konzepte zu verdeutlichen.

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

Planspiel

⏱ 25 Min.·Einzelarbeit

Individuelle Modellierung: Listen vs. Arrays

Jeder Schüler entwirft Diagramme für Stack-Implementierungen mit Listen und Arrays. Sie berechnen Big-O-Notation und präsentieren einen Vorteil pro Variante.

Vorbereitung & Details

Erklären Sie die Funktionsweise eines Stacks und einer Queue anhand von Alltagsbeispielen.

Moderationstipp: Lassen Sie die Schüler bei der individuellen Modellierung bewusst zwischen Listen und Arrays wählen und begründen sie ihre Entscheidung schriftlich.

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

Dieses Thema unterrichten

Beginne mit konkreten, greifbaren Beispielen aus dem Alltag, um die abstrakten Konzepte zu verankern. Vermeide es, die Implementierung zu früh zu thematisieren, da dies die Schüler überfordern kann. Nutze die physischen Simulationen, um die Prinzipien zu verinnerlichen, bevor du zur codebasierten Umsetzung übergehst. Forschung zeigt, dass Schüler durch aktives Handeln und Fehlerkultur nachhaltiger lernen als durch Frontalunterricht.

Was Sie erwartet

Erfolgreiches Lernen zeigt sich daran, dass Schüler die Prinzipien von Stacks und Queues in neuen Kontexten anwenden können und die Unterschiede zwischen beiden Strukturen klar benennen. Sie erkennen, wann welche Datenstruktur sinnvoll ist und können einfache Implementierungen nachvollziehen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Kartenrotation beobachten Sie, dass Schüler Stacks und Queues als austauschbar behandeln.

Was Sie stattdessen lehren sollten

Nutzen Sie die Kartenrotation, um gezielt nachzufragen: 'Warum legen wir beim Stack das oberste Element zuerst zurück, bei der Queue aber das unterste?' Lassen Sie die Schüler die Unterschiede in der Handhabung physisch nachspielen.

Häufige Fehlvorstellung

Während der Pair-Programming-Aktivität argumentieren Schüler, Arrays seien immer die bessere Wahl für Stacks und Queues.

Was Sie stattdessen lehren sollten

Fordern Sie die Schüler auf, eine volle Array-Implementierung zu testen und die Fehlerbehandlung zu dokumentieren. Zeigen Sie ihnen, wie Listen dynamisch wachsen und damit Overflow vermeiden.

Häufige Fehlvorstellung

Während der Ganzklasse-Diskussion über Queues behaupten Schüler, man könne beliebige Elemente entfernen.

Was Sie stattdessen lehren sollten

Nutzen Sie die Supermarkt-Schlangen-Simulation, um zu demonstrieren: 'Wenn Sie in der Schlange vorpreschen, stören Sie die Reihenfolge für alle anderen.' Lassen Sie Schüler dies mit physischen Karten nachspielen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Nach der Kartenrotation erhalten alle Schüler eine Karte mit einer der Aufgaben: 'Beschreiben Sie das LIFO-Prinzip mit einem Alltagsbeispiel.' oder 'Nennen Sie zwei Anwendungsbereiche für Queues.' Die Antworten werden eingesammelt und ausgewertet.

Kurze Überprüfung

Während der Kartenrotation stellen Sie folgende Fragen an die Klasse: 'Wenn Sie eine Tellersäule aufbauen, welches Prinzip nutzen Sie? LIFO oder FIFO?' und 'Wenn Sie in einer Schlange an der Kasse stehen, welches Prinzip gilt dort? LIFO oder FIFO?' Klären Sie Missverständnisse direkt im Anschluss.

Diskussionsfrage

Nach der Pair-Programming-Aktivität teilen Sie die Klasse in zwei Gruppen. Eine Gruppe diskutiert die Vorteile der Array-Implementierung für Stacks und Queues, die andere die Vorteile von verketteten Listen. Lassen Sie jede Gruppe ihre Ergebnisse präsentieren und vergleichen Sie die Argumente im Plenum.

Erweiterungen & Unterstützung

• Fordere fortgeschrittene Schüler auf, eine Queue mit zwei Stacks zu implementieren und die Effizienz zu vergleichen.
• Biete Schülern, die unsicher sind, eine Vorlage mit unvollständigen Code-Snippets an, die sie vervollständigen müssen.
• Vertiefe die Thematik mit einer Analyse von Zeitkomplexitäten beider Datenstrukturen in verschiedenen Implementierungsvarianten.

Schlüsselvokabular

Stack	Eine Datenstruktur, die nach dem LIFO-Prinzip (Last-In, First-Out) arbeitet. Das zuletzt hinzugefügte Element ist das erste, das wieder entfernt wird.
Queue	Eine Datenstruktur, die nach dem FIFO-Prinzip (First-In, First-Out) arbeitet. Das zuerst hinzugefügte Element ist das erste, das wieder entfernt wird.
LIFO	Akronym für 'Last-In, First-Out'. Beschreibt das Prinzip, dass das zuletzt eingefügte Element zuerst verarbeitet wird.
FIFO	Akronym für 'First-In, First-Out'. Beschreibt das Prinzip, dass das zuerst eingefügte Element zuerst verarbeitet wird.
Push-Operation	Die Operation, ein Element auf einen Stack zu legen oder in eine Queue einzufügen.
Pop-Operation	Die Operation, das oberste Element von einem Stack zu entfernen oder das vorderste Element aus einer Queue zu entnehmen.