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

Dynamische Datenstrukturen: Stacks und Queues

Die Schülerinnen und Schüler implementieren und nutzen Stacks (LIFO) und Queues (FIFO) für spezifische Anwendungsfälle.

• KMK Bildungsstandards
• KMK: STD.01
• KMK: STD.02

Über dieses Thema

Automaten und formale Sprachen bilden das theoretische Rückgrat der Informatik. Schüler lernen, wie endliche Automaten genutzt werden, um einfache Abläufe wie Ticketautomaten oder Ampelsteuerungen zu modellieren. Dies führt zum Verständnis von regulären Sprachen und deren Erkennung durch Maschinen. Dies entspricht den KMK-Standards zur theoretischen Informatik und Modellierung.

Die Schüler beschäftigen sich mit Zuständen, Übergängen und Eingabealphabeten. Sie erfahren, wie Computer Programmiersprachen verstehen, indem sie diese in ihre Bestandteile zerlegen (Parsing). Dies schult das präzise, logische Denken und hilft zu verstehen, warum Computer so strikt auf Syntaxfehler reagieren. Es ist die Basis für das Verständnis von Compilern und künstlicher Intelligenz.

Durch das physische 'Durchlaufen' von Automaten auf dem Boden, bei denen Schüler von Zustand zu Zustand hüpfen, wird die abstrakte Theorie lebendig und begreifbar.

Leitfragen

1. Wofür braucht man einen LIFO-Speicher im Browser-Verlauf?
2. Wie kann eine Warteschlange (Queue) in einem Betriebssystem genutzt werden?
3. Differentiieren Sie die Anwendungsbereiche von Stacks und Queues in der Softwareentwicklung.

Lernziele

• Implementieren Sie einen Stack in einer Programmiersprache zur Verwaltung von Rückgängig-Operationen.
• Erklären Sie die Funktionsweise einer Warteschlange (Queue) am Beispiel der Druckauftragsverwaltung eines Betriebssystems.
• Vergleichen Sie die Anwendungsfälle von Stacks (LIFO) und Queues (FIFO) in der Softwareentwicklung anhand von Beispielen.
• Analysieren Sie die Effizienz von Stack- und Queue-Operationen in Bezug auf ihre Laufzeitkomplexität.
• Entwerfen Sie eine einfache Anwendung, die entweder einen Stack oder eine Queue zur Lösung eines spezifischen Problems nutzt.

Bevor es losgeht

Grundlagen von Variablen und Datentypen

Warum: Schüler müssen verstehen, wie Daten in Variablen gespeichert und manipuliert werden können, um die Implementierung von Stacks und Queues nachvollziehen zu können.

Einführung in Arrays und Listen

Warum: Stacks und Queues werden oft auf Basis von Arrays oder verketteten Listen implementiert. Grundkenntnisse dieser linearen Datenstrukturen sind daher notwendig.

Kontrollstrukturen (Schleifen und Bedingungen)

Warum: Die Implementierung und Nutzung von Stacks und Queues erfordert den Einsatz von Schleifen zur Iteration und Bedingungen zur Fehlerprüfung (z.B. ob ein Stack leer ist).

Schlüsselvokabular

Stack (LIFO)	Eine Datenstruktur, die nach dem Prinzip 'Last-In, First-Out' (zuletzt hinein, zuerst heraus) arbeitet. Das zuletzt hinzugefügte Element wird als erstes wieder entfernt.
Queue (FIFO)	Eine Datenstruktur, die nach dem Prinzip 'First-In, First-Out' (zuerst hinein, zuerst heraus) arbeitet. Das zuerst hinzugefügte Element wird als erstes wieder entfernt.
Push-Operation	Die Operation, um ein neues Element auf den Stack zu legen (hinzuzufügen).
Pop-Operation	Die Operation, um das oberste Element vom Stack zu entfernen und zurückzugeben.
Enqueue-Operation	Die Operation, um ein neues Element am Ende der Queue hinzuzufügen.
Dequeue-Operation	Die Operation, um das vorderste Element aus der Queue zu entfernen und zurückzugeben.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Ein Automat ist eine physische Maschine.

Was Sie stattdessen lehren sollten

Schüler denken oft an Roboter. Durch das Modellieren von Software-Logik (z.B. Passwort-Validierung) lernen sie, dass Automaten ein mathematisches Konzept zur Beschreibung von Abläufen sind.

Häufige Fehlvorstellung

Computer verstehen menschliche Sprache genauso wie wir.

Was Sie stattdessen lehren sollten

Oft wird die Komplexität von Sprache unterschätzt. Eine Übung zum Parsing zeigt, dass Computer strikte formale Regeln brauchen und bei kleinsten Abweichungen scheitern.

Ideen für aktives Lernen

Planspiel: Der menschliche Automat

Ein Automat wird mit Kreide auf den Boden gezeichnet. Schüler 'füttern' einen Mitschüler mit einer Zeichenfolge (z.B. 0-1-1). Der Schüler bewegt sich entsprechend der Regeln durch die Zustände bis zum Endzustand.

40 Min.·Ganze Klasse

Forschungskreis: Ticketautomat modellieren

Gruppen entwerfen einen Zustandsgraphen für einen einfachen Parkautomaten. Sie müssen alle Fälle bedenken: Genug Geld, zu wenig Geld, Abbruch-Taste.

45 Min.·Kleingruppen

Ich-Du-Wir (Denken-Austauschen-Vorstellen): Reguläre Ausdrücke

Schüler versuchen, ein Muster für gültige E-Mail-Adressen zu finden. Partner vergleichen ihre Regeln und diskutieren, warum Computer so präzise Vorgaben brauchen.

25 Min.·Partnerarbeit

Bezüge zur Lebenswelt

• Im Webbrowser wird der Zurück-Button 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.
• Betriebssysteme nutzen Queues, um Aufgaben zu verwalten, die nacheinander abgearbeitet werden müssen. Ein klassisches Beispiel ist die Druckwarteschlange, bei der Druckaufträge in der Reihenfolge ihres Eintreffens bearbeitet werden.
• In der Spieleentwicklung können Stacks verwendet werden, um den Spielverlauf zu verwalten, z.B. für die Rückgängig-Funktion von Zügen oder die Verwaltung von Spielzuständen in einem komplexen Spiel.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie jedem Schüler ein Blatt mit zwei Szenarien: 1. Ein Benutzer klickt auf 'Zurück' in seinem Browser. 2. Ein Benutzer sendet einen neuen Druckauftrag. Bitten Sie die Schüler, für jedes Szenario zu entscheiden, ob ein Stack oder eine Queue besser geeignet ist, und begründen Sie ihre Wahl kurz.

Kurze Überprüfung

Stellen Sie folgende Fragen: 'Wie würden Sie die Reihenfolge der Anrufe in einer Telefonwarteschleife beschreiben: LIFO oder FIFO?' und 'Welche Operation wird verwendet, um ein Element auf einen Stack zu legen?' Bewerten Sie die Antworten auf Verständnis der Kernprinzipien.

Diskussionsfrage

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie entwickeln ein System zur Verwaltung von Kundenanfragen per E-Mail. Welche Datenstruktur würden Sie wählen, um die eingehenden E-Mails zu speichern, und warum? Diskutieren Sie die Vor- und Nachteile Ihrer Wahl im Vergleich zur anderen Datenstruktur.'

Häufig gestellte Fragen

Was ist ein endlicher Automat?

Ein Modell, das aus einer festen Anzahl von Zuständen besteht. Es wechselt durch Eingaben von einem Zustand in den nächsten. Er wird genutzt, um Logik und Sprachen zu prüfen.

Wofür braucht man reguläre Ausdrücke?

Sie sind eine kompakte Schreibweise, um Textmuster zu beschreiben. Man nutzt sie zum Suchen und Ersetzen in Texten oder zum Prüfen von Eingaben wie Telefonnummern.

Warum ist ein schülerzentrierter Ansatz bei theoretischer Informatik wichtig?

Theorie wirkt oft trocken und fernab der Praxis. Wenn Schüler Automaten physisch ablaufen oder reale Geräte wie Ampeln selbst modellieren, wird der Nutzen der Abstraktion klar. Aktives Experimentieren mit Zuständen hilft, logische Fehler im Entwurf selbst zu entdecken. Das fördert ein tiefes Verständnis für die Funktionsweise von Software, das über reines Auswendiglernen hinausgeht.

Können Automaten alles berechnen?

Nein, endliche Automaten sind in ihrer Mächtigkeit begrenzt. Komplexere Modelle wie die Turingmaschine können mehr, stoßen aber auch an die Grenzen der Berechenbarkeit.