Dreißig Übungen zur Schlange — von enqueue und dequeue bis zur Rotation.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig interaktive Übungen zum Klicken, Ziehen und Knobeln — von AFB I bis AFB III. Jede Übung gibt dir sofort Rückmeldung.
A1
Konzertkarten in der Reihe
AFB I
Die Abbildung zeigt die Schlange q mit den Nummern der Konzertkarten, die verkauft werden (vorn links). Danach laufen drei Aufrufe dequeue(), deren Ergebnisse nacheinander in x, y und z gespeichert werden.
Lies in der Abbildung die Reihenfolge ab und leite so her, in welcher Reihenfolge die Nummern entnommen werden: Ordne jeder Zeile die passende Begründung zu.
Ordne jeder Zeile der Herleitung die passende Begründung zu: Karte anklicken, dann das Feld neben der Zeile (oder Karte direkt auf das Feld ziehen). Mit der Tastatur: Tab zur Karte, Enter, dann Tab zum Feld und Enter. Ein Klick auf ein belegtes Feld legt die Karte zurück. Nicht alle Karten werden gebraucht.
Zu zeigen: Die Nummern werden in der Reihenfolge 41, 42, 43 entnommen.
UmformungBegründung
(1)Vorn in der Abbildung steht die Karte 41Abgelesen: Vorn ist das linke Ende der Schlange
(2)x = q.dequeue(); → x = 41
(3)y = q.dequeue(); → y = 42
(4)z = q.dequeue(); → z = 43
Vorn steht die 41, dann folgen 42 und 43. Jedes dequeue entnimmt das gerade vorderste Element, also kommen die Nummern in der Reihenfolge heraus, in der sie angestellt wurden: 41, 42, 43.
Lies zuerst ab, welche Karte vorn steht. dequeue arbeitet immer an diesem Ende.
Nach jedem dequeue rückt die nächste Karte nach vorn. Die Reihenfolge bleibt erhalten, sie wird nicht umgekehrt.
A2
Der Kartentrick
AFB II
Ein Kartentrick: Fünf Karten mit den Nummern 1 bis 5 liegen in einer Schlange q (vorn links, Reihenfolge 1, 2, 3, 4, 5). Wiederholt gilt: Die vorderste Karte wird abgelegt (dequeue), die nächste Karte wandert nach hinten (q.enqueue(q.dequeue())). Bleibt nur eine Karte übrig, wird sie abgelegt. Leite die Reihenfolge der abgelegten Karten Schritt für Schritt her.
Spiele den Rechenweg Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
Jede Runde legt die vorderste Karte ab und schiebt die nächste ans Ende: 1, dann 3, dann 5, dann 4 und zuletzt 2.
Führe jede Runde genau aus: erst die vorderste Karte ablegen, dann die nächste vorn entnehmen und hinten wieder anstellen.
Die abgelegten Karten sind nicht 1, 2, 3, 4, 5: Jede zweite Karte wandert zunächst nach hinten und kommt erst später an die Reihe.
A3
Stapel, Schlange oder DynArray?
AFB IIMix
Stapel, Schlange und dynamische Reihung (DynArray) speichern Elemente, verhalten sich aber verschieden. Erläutere die Unterschiede: Welche Struktur passt zu welcher Aussage?
Setze in jeder Zeile das passende Kreuz — hier ist es genau eins pro Zeile. Enter setzt und löscht.
Aussage
Stapel
Schlange
DynArray
Zugriff über einen Index (getItem(i))
Das am längsten wartende Element kommt zuerst heraus.
Das zuletzt abgelegte Element kommt zuerst heraus.
Einfügen von 1, 2, 3, dann Entnehmen: Ausgabe 1, 2, 3.
Einfügen von 1, 2, 3, dann Entnehmen: Ausgabe 3, 2, 1.
Einfügen in der Mitte mit insertAt
Nur die dynamische Reihung erlaubt den Zugriff über einen Index und das Einfügen in der Mitte. Bei der Schlange kommt das älteste Element zuerst heraus (Ausgabe 1, 2, 3), beim Stapel das neueste (Ausgabe 3, 2, 1).
Frage dich: Gibt es einen Index und freien Zugriff, oder kommt nur ein Element an die Reihe, das älteste oder das neueste?
Bei gleicher Eingabe 1, 2, 3 erhält der Stapel die Reihenfolge nicht, die Schlange schon.
