Dynamische Datenstrukturen und Queue

Lernziele

Nach diesem Kapitel kannst du:

• die Zugriffsregel einer Warteschlange von ihrer technischen Umsetzung unterscheiden,
• die Grundidee verketteter Knoten (content + next) beschreiben,
• die vier Queue-Methoden (enqueue, dequeue, front, isEmpty) anwenden und die Ausgabe vorhersagen,
• ein Objektdiagramm einer Queue mit head, tail und next zeichnen,
• für eine konkrete Operation Vorteile und Grenzen von Array und Verkettung begründen.

Leitfrage: Wie organisierst du eine wachsende Warteschlange, die immer den ältesten Auftrag zuerst bearbeitet?

Dein Lernweg

A1 und A2 sowie der Kompetenzcheck sind der gemeinsame Kern. A3 nutzt du bei Unsicherheit zum leeren Zustand. Wähle danach den Shop-Transfer oder einen eigenen FIFO-Kontext mit denselben Anforderungen; A4/A5 sind zusätzliche Vertiefung.

Mermaid-Diagramm wird geladen…

Arbeitsweise: Abruffragen und Kompetenzchecks beantwortest du zuerst allein ohne Unterlagen und KI. Speichere deine eigene Antwort, bevor du die Rückmeldung öffnest. Im Übungsteil darfst du Hilfen nutzen; nenne anschließend, welche Hilfe du gebraucht hast. Bei jedem Programm: erst erwartete Ausgabe und einen Leerfall notieren, dann ausführen und vergleichen.

Voraussetzungen

Phase 1: Einstieg — Aufträge in Ankunftsreihenfolge

Die Warteschlange wächst

An einem Schulfest kommen Druckaufträge A, B und C an. Nach dem Drucken von A kommt D hinzu. Alle sollen in Ankunftsreihenfolge bedient werden.

Exploration – 4 Minuten allein, ohne KI: Zeichne zwei Zustände. Wie könntest du die Aufträge in einem Array verwalten? Was passiert mit freien Plätzen nach dem Drucken? Was tust du, wenn alle Plätze belegt sind? Notiere einen eigenen Vorschlag, bevor du die Auswertung öffnest.

Phase 2: Konzeptaufbau — Verkettung statt feste Plätze

Abruf 2 – ohne Nachlesen: Welche Reihenfolge muss die Druckerwarteschlange nach A entfernen und D anfügen haben? Was ändert sich an einer Referenz beim Umlenken?

Beim folgenden Beispiel ohne KI: Sage das Ergebnis vorher. Erkläre anschließend einer anderen Person, welche Zeile die Datenstruktur verändert. Erst dann ausführen.

2.1 Was ist eine dynamische Datenstruktur?

Queue und Stack beschreiben vor allem erlaubte Zugriffe. Die hier verwendeten NRW-Klassen setzen diese Regeln durch Verkettung um. Zugriffsregel und Implementierung sind zwei verschiedene Ebenen.

2.2 Verkettete Knoten — der Grundbaustein

Jeder Knoten (Node) enthält zwei Dinge:

• content — eine Referenz auf das eigentliche Datenobjekt (z.B. einen Patienten)
• next — eine Referenz auf den nächsten Knoten (oder null, wenn es der letzte ist)

Mermaid-Diagramm wird geladen…

2.3 Die Queue — Warteschlange nach dem FIFO-Prinzip

Eine Queue arbeitet nach dem FIFO-Prinzip (First In, First Out): Wer zuerst eingefügt wird, wird zuerst entnommen. Wie eine Warteschlange beim Arzt.

Die verkettete NRW-Queue hat zwei Referenzen:

• head — zeigt auf den ersten Knoten (vorne, wird als nächstes entnommen)
• tail — zeigt auf den letzten Knoten (hinten, dort wird eingefügt)

2.4 Die vier Queue-Methoden

Sage vorher, dann teste:

Vorhersage: Wer wird zuerst behandelt?

Reflexionsfrage: Warum gibt front() auf einer leeren Queue null zurück statt abzustürzen? Was ist der Vorteil für den Programmierer?

Objektdiagramm: Queue mit 3 Elementen

Nach enqueue(Ada), enqueue(Ben), enqueue(Cem):

Mermaid-Diagramm wird geladen…

Ruhige Sicherung: Was die Queue einfacher macht

Code-Patterns

// Sicher ein Element entnehmen
if (!q.isEmpty())
{
    Typ element = q.front();  // Ansehen
    q.dequeue();              // Entfernen
    // element weiterverarbeiten
}

Zwei Mini-Checks vor der Übung

1. Eine Queue enthält A,B. Was steht nach zweimal front() vorne?

2. Beim letzten dequeue: Wohin zeigen head und tail danach?

Fading – Hilfen nach Bedarf

Wähle Parsons oder Completion. Schreibe vor dem Ausführen: „Die Ausgabe ist Ada; danach steht Ben vorne.“ Beim Modify-Auftrag muss dieselbe Reihenfolge erhalten bleiben.

Hilfen zu den Queue-Aufgaben

Phase 3: Üben

Abgabe-Aufgaben

Queue<String> q = new Queue<String>();
q.enqueue("X");
q.enqueue("Y");
q.enqueue("Z");
System.out.println(q.front());   // ?
q.dequeue();
System.out.println(q.front());   // ?
q.enqueue("W");
q.dequeue();
System.out.println(q.front());   // ?
System.out.println(q.isEmpty()); // ?

Queue<Patient> q = new Queue<Patient>();
q.enqueue(new Patient("Ada"));
q.dequeue();
 
// Nächsten Patienten anzeigen
System.out.println(q.front().getName());

Kompetenzcheck – allein, 8–10 Minuten (Pflicht)

Beantworte die drei Aufgaben ohne Vorlage, Ausführen oder KI. Speichere deine erste Antwort vor dem Vergleich. Eine Partnerlösung ersetzt deine Antwort nicht.

1. Eine leere Queue erhält A und B. Danach folgen dequeue() und enqueue(C). Nenne front() und die gesamte Entnahmereihenfolge.
2. Zeichne für diesen Zustand die Queue, ihre Knoten und Inhalte mit head, tail, next und content. Erkläre, warum front() allein kein Element entfernt.
3. Nach vollständiger Entnahme: Was liefern front() und isEmpty()? Was tut dequeue()? Warum wäre front().toString() gefährlich?

Neuer Versuch nach gezielter Übung

Neue leere Queue: enqueue(P), enqueue(Q), dequeue(), enqueue(R), dequeue(). Zeichne den Endzustand und erkläre das anschließende Leeren.

Phase 4: Transfer und Vernetzung

Transferaufgabe

Vernetzung

Heute gelöst: FIFO legt die Reihenfolge fest; Verkettung ist eine mögliche Umsetzung. Die NRW-Queue wächst durch neue Knoten. Welche Umsetzung sinnvoll ist, hängt von den benötigten Operationen ab.

Noch offen: Die Queue ist bequem, solange du nur vorne bedienen willst. Schwieriger wird es, wenn du etwas wissen möchtest: Wie viele Bestellungen sind offen? Ist eine bestimmte Bestellung dabei? Dafür musst du in die Queue hineinschauen, und das geht nur, indem du Elemente entnimmst.

Nächster Schritt: Im nächsten Kapitel wird genau diese Zugriffskrise gelöst: Wie untersucht man eine Queue, ohne sie zu zerstören?

Reflexion

Selbstdiagnose

• Ich kann erklären, warum Arrays bei dynamischen Daten unpraktisch sind.
• Ich kenne die 4 Queue-Methoden und kann die Ausgabe vorhersagen.
• Ich kann ein Objektdiagramm einer Queue zeichnen (head, tail, next, content).
• Ich weiß, dass dequeue() das Objekt nicht löscht, sondern nur aus der Queue aushängt.

Partnerprüfung oder Solo-Erklärung (5 Minuten)

Erkläre 2 Minuten lang deine gewählte Methode. Dein Gegenüber prüft einen Randfall und fragt: „Warum bleibt die Reihenfolge hier erhalten oder ändert sich?“ Wechselt dann die Rollen. Allein: Schreibe die Erklärung und beantworte dieselbe Frage schriftlich. Vergleiche mit dem passenden Beispiel und verbessere einen unklaren Satz.

Selbstdiagnose: Welchen Ablauf, welche Begründung und welchen Randfall kannst du ohne Hilfe erklären? Nenne jeweils eine konkrete Aufgabe als Beleg. Wie sicher bist du (1–5)? Bei 1–2 bearbeitest du eine passende Hilfe und den neuen Versuch; bei 4–5 wählst du eine eigene Erweiterung.