Informatik · Klasse 11 · Algorithmen und Komplexität · 2. Halbjahr

Datenstrukturen: Stacks und Queues

Einführung in die Prinzipien von LIFO (Last-In, First-Out) und FIFO (First-In, First-Out).

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Strukturieren
• KMK: Sekundarstufe II - Modellieren

Über dieses Thema

Stacks und Queues bilden grundlegende Datenstrukturen in der Informatik der Oberstufe. Ein Stack folgt dem LIFO-Prinzip (Last In, First Out), wie bei einer Tellersäule: Das zuletzt eingelegte Element wird zuerst entfernt. Eine Queue hingegen arbeitet nach FIFO (First In, First Out), vergleichbar mit einer Wareschlange im Supermarkt. Schüler analysieren diese Prinzipien anhand von Alltagsbeispielen und verbinden sie mit den KMK-Standards zum Strukturieren und Modellieren.

Im Unterricht werden Anwendungsbereiche beleuchtet, etwa Stacks in Undo-Funktionen von Texteditoren oder Queues in Druckwarteschlangen. Schüler vergleichen Implementierungen mit Arrays oder Listen, bewerten Vor- und Nachteile bezüglich Speichereffizienz und Zugriffszeiten. Praktische Übungen fördern das Verständnis algorithmischer Komplexität und bereiten auf fortgeschrittene Themen vor.

Aktives Lernen ist hier besonders wirksam, weil abstrakte Konzepte durch physische Modelle und Programmieraufgaben konkret werden. Wenn Schüler Karten stapeln oder Warteschlangen simulieren, internalisieren sie LIFO und FIFO intuitiv. Solche hands-on-Aktivitäten stärken Problemlösungsfähigkeiten und machen den Stoff nachhaltig greifbar.

Leitfragen

1. Erklären Sie die Funktionsweise eines Stacks und einer Queue anhand von Alltagsbeispielen.
2. Analysieren Sie, in welchen Anwendungsbereichen Stacks und Queues besonders nützlich sind.
3. Vergleichen Sie die Implementierung von Stacks und Queues mithilfe von Arrays oder Listen.

Lernziele

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

Bevor es losgeht

Grundlagen von Variablen und Datentypen

Warum: Schüler müssen verstehen, wie Werte in Variablen gespeichert und unterschieden werden können, um Datenstrukturen zu begreifen.

Einführung in Arrays

Warum: Das Verständnis von Arrays ist notwendig, um die Array-basierte Implementierung von Stacks und Queues nachvollziehen zu können.

Grundlagen von Listen (verkettete Listen)

Warum: Die Konzepte von verketteten Listen sind wichtig, um die alternative Implementierung von Stacks und Queues zu verstehen und vergleichen zu können.

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.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Stacks und Queues sind austauschbar, da beide Elemente speichern.

Was Sie stattdessen lehren sollten

Stacks folgen LIFO, Queues FIFO: Das führt zu unterschiedlichen Anwendungen. Aktive Simulationen mit Karten helfen Schülern, Operationen selbst auszuführen und den fundamentalen Unterschied zu erleben, statt ihn nur zu merken.

Häufige Fehlvorstellung

Arrays sind immer effizienter als Listen für Stacks.

Was Sie stattdessen lehren sollten

Arrays haben feste Größe und riskieren Overflow, Listen sind dynamisch. Pair-Programmierung zeigt dies praxisnah: Schüler testen Grenzfälle und entdecken durch Trial-and-Error die passende Struktur.

Häufige Fehlvorstellung

In Queues kann man beliebig zugreifen.

Was Sie stattdessen lehren sollten

Nur an Front und Rear: Direkter Zugriff verletzt FIFO. Gruppensimulationen mit physischen Objekten verdeutlichen dies, da Schüler spüren, wie Verstöße die Reihenfolge durcheinanderbringen.

Ideen für aktives Lernen

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.

45 Min.·Kleingruppen

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.

50 Min.·Partnerarbeit

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.

30 Min.·Ganze Klasse

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.

25 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• In Webbrowsern wird die 'Zurück'-Funktion oft mithilfe eines Stacks realisiert. Jeder besuchte Link wird auf den Stack gelegt, und durch Drücken des Zurück-Buttons wird das oberste Element (die letzte Seite) vom Stack genommen und angezeigt.
• Druckwarteschlangen in Büros oder Universitäten sind ein klassisches Beispiel für Queues. Dokumente, die zum Drucken gesendet werden, reihen sich in der Reihenfolge ihres Eingangs ein und werden nacheinander abgearbeitet.
• Callcenter nutzen Queues, um eingehende Anrufe zu verwalten. Anrufer werden in der Reihenfolge ihres Anrufs mit verfügbaren Agenten verbunden, um eine faire Bearbeitung zu gewährleisten.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie jedem Schüler eine Karte mit einer der folgenden Aufgaben: 'Beschreiben Sie das LIFO-Prinzip mit einem Alltagsbeispiel.' oder 'Nennen Sie zwei Anwendungsbereiche für Queues.' Die Schüler schreiben ihre Antwort auf die Karte und geben sie ab.

Kurze Überprüfung

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?' Sammeln Sie Antworten und klären Sie Missverständnisse.

Diskussionsfrage

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 anschließend ihre Ergebnisse kurz präsentieren und vergleichen Sie die Argumente.

Häufig gestellte Fragen

Wie erkläre ich LIFO und FIFO Schülern der 11. Klasse?

Verwenden Sie Alltagsbeispiele wie Tellersäule (Stack, LIFO) und Kasse (Queue, FIFO). Lassen Sie Schüler diese mit Gegenständen nachstellen, um Operationen wie push/pop oder enqueue/dequeue zu visualisieren. Ergänzen Sie mit einfachem Pseudocode, der den Ablauf schrittweise zeigt. So wird das Prinzip greifbar und bleibt im Gedächtnis (ca. 65 Wörter).

Welche Anwendungen haben Stacks und Queues in der Praxis?

Stacks eignen sich für Rückgängig-Funktionen, Funktionsaufrufe oder Browser-History. Queues werden in Task-Scheduling, Netzwerkpaketen oder BFS-Algorithmen genutzt. Schüler analysieren reale Szenarien, um Relevanz zu erkennen und Implementierungen zu motivieren (ca. 55 Wörter).

Wie vergleiche ich Implementierungen mit Arrays und Listen?

Arrays bieten konstanten O(1)-Zugriff, aber feste Größe. Listen sind flexibel, erfordern jedoch O(n) für einige Operationen. Durch Diagramme und Code-Vergleiche lernen Schüler Komplexitäten: Arrays für kleine, bekannte Größen; Listen für dynamische Fälle (ca. 60 Wörter).

Wie fördert aktives Lernen das Verständnis von Stacks und Queues?

Aktive Methoden wie Karten-Simulationen oder Pair-Programming machen abstrakte Prinzipien erfahrbar. Schüler führen Operationen aus, begegnen Fehlern selbst und diskutieren Lösungen. Dies stärkt Modellierfähigkeiten nach KMK-Standards, verbessert Retention und verbindet Theorie mit Praxis effektiver als Frontalunterricht (ca. 70 Wörter).