Eine Operationsfolge mit neuen und wartenden Elementen verfolgen
Den Übergang zwischen leerer und nichtleerer Queue erklären
Verständlich erklärt
Eine Queue arbeitet nach FIFO: First In, First Out. Von den noch vorhandenen Elementen wird das zuerst eingetroffene als Nächstes entfernt. enqueue fügt hinten hinzu, dequeue entfernt vorne und gibt dieses Element zurück. front beziehungsweise peek liest nur das vorderste Element. In unseren waagerechten Darstellungen steht vorne links und hinten rechts. Eine normale Warteschlange ohne Sonderprioritäten kann zum Beispiel eingehende Aufträge in Ankunftsreihenfolge bedienen. Ein späterer Auftrag überholt dabei keinen noch wartenden früheren Auftrag. Für sichere Operationen mit ganzzahligen Nutzdaten vereinbaren wir: Bei leerer Queue wird None zurückgegeben, ohne etwas zu verändern.
Eine verkettete Implementierung kann zwei Referenzen halten: vorn auf den ersten und hinten auf den letzten Knoten. Nach dem Einfügen in die leere Queue zeigen beide auf denselben Knoten. Nach dem Entfernen des einzigen Knotens müssen beide None sein. Mit bekanntem Endknoten kann hinten angefügt werden, ohne die ganze Liste zu durchsuchen.
Für kurze Python-Übungen verwenden wir eine Liste, append zum Einfügen und pop(0) zum Entfernen vorne. Das zeigt die FIFO-Semantik, ist aber kein Beleg für eine konstante Laufzeit: pop(0) verschiebt in einer Python-Liste die übrigen Elemente. Queue und Stack sind unterschiedliche Schnittstellen; die gemeinsame Verwendung einer Liste macht ihr Verhalten nicht gleich.
Hinten statt vorne entfernen und dadurch einen Stack bilden
front mit einer entfernenden Operation verwechseln
Nach dem letzten Entfernen eine veraltete Endreferenz behalten
Die Laufzeit einer konkreten Python-Liste ungeprüft auf jede Queue übertragen
Kurz zusammengefasst
Neue Elemente kommen hinten an, bedient wird vorne. Prüfe beim Leerwerden beide Referenzen und unterscheide das FIFO-Verhalten von der gewählten Speicherform.
Abi-Bezug
Kennzeichne Anfang und Ende eindeutig. Verfolge die Reihenfolge wartender Aufträge und begründe besonders den Leerfall einer verketteten Queue.
Jetzt selbst ausprobieren
Prüfe deine Lösung automatisch. Bei Bedarf helfen dir ein Tipp und anschließend die Musterlösung.
BPE 7J21 Punkteleicht
Aufträge fair nach Ankunft bedienen
Noch nicht begonnen
Aufgabenstellung
Druckaufträge sollen ohne Sonderprioritäten in ihrer Ankunftsreihenfolge bearbeitet werden. Welche Struktur passt zu dieser Regel?
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Vergleiche die geforderte Reihenfolge mit FIFO und LIFO.
Der zuerst eingetroffene, noch vorhandene Auftrag soll vorne stehen.
Lösung anzeigen
FIFO hält die Reihenfolge der noch wartenden Aufträge ein. Ein Stack würde dagegen den zuletzt angekommenen Auftrag zuerst entnehmen.
BPE 7J21 Punkteleicht
Hinten einfügen, vorne entfernen
Noch nicht begonnen
Aufgabenstellung
Die Queue ist leer. Es folgen enqueue(K1), enqueue(K2), dequeue(), enqueue(K3). Welche Aufträge warten danach von vorne nach hinten? Antworte kommagetrennt.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Neue Aufträge kommen rechts hinzu; entfernt wird links.
Beim einzigen dequeue wartet K1 schon länger als K2.
Lösung anzeigen
K2, K3. dequeue entfernt K1, den zuerst angekommenen Auftrag. K3 stellt sich hinter K2 an.
BPE 7J22 Punktemittel
Rückgaben einer Warteschlange
Noch nicht begonnen
Aufgabenstellung
Vorne links steht die Queue [K4, K5, K6]. Es folgen dequeue(), enqueue(K7), dequeue(), front(). Gib nur die Rückgaben der beiden dequeue-Aufrufe und von front kommagetrennt an.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
enqueue verändert den Inhalt, liefert hier aber keinen gefragten Rückgabewert.
Der neue Auftrag K7 darf die noch wartenden älteren Aufträge nicht überholen.
Lösung anzeigen
K4, K5, K6. K4 und K5 werden nacheinander vorne entnommen. K7 wartet hinter K6; front liest K6, ohne es zu entfernen.
BPE 7J22 Punktemittel
front und dequeue unterscheiden
Noch nicht begonnen
Aufgabenstellung
Welche Aussagen gelten für eine nichtleere Queue? Wähle alle richtigen Antworten.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Beide Namen beschreiben einen Zugriff auf den Anfang der Queue.
Prüfe zusätzlich, ob die Operation nur beobachtet oder den Inhalt verändert.
Lösung anzeigen
Beide Operationen beziehen sich auf vorne. Nur dequeue verändert die Anzahl der Elemente. FIFO verlangt weder alphabetische Sortierung noch Entfernen hinten.
BPE 7J22 Punktemittel
FIFO ausschreiben
Noch nicht begonnen
Aufgabenstellung
Eine Queue entnimmt unter den noch wartenden Elementen das zuerst eingefügte zuerst. Schreibe die englischen Wörter der Abkürzung FIFO aus.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Gesucht sind vier kurze Wörter, nicht der Name einer Python-Methode.
Die ersten beiden Wörter bezeichnen zuerst hinein; die letzten beiden zuerst heraus.
Lösung anzeigen
First In, First Out: Das zuerst eingefügte, noch vorhandene Element verlässt die Warteschlange zuerst.
BPE 7J22 Punktemittel
Vordersten Auftrag bedienen
Noch nicht begonnen
Aufgabenstellung
Implementiere bediene(wartend). Die Python-Liste enthält ganzzahlige Auftragsnummern; vorne ist Index 0. Entferne die vorderste Nummer und gib sie zurück. Bei leerer Liste gib None zurück. Die übergebene Liste soll entsprechend verändert werden. Dieses einfache Listenmodell prüft FIFO, nicht eine optimierte Laufzeit.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Der Leerfall muss vor einem Zugriff auf Index 0 behandelt werden.
pop(0) entfernt genau das erste Element; pop() ohne Index würde dagegen hinten entfernen.
Lösung anzeigen
def bediene(wartend):
if not wartend:
return None
return wartend.pop(0)
BPE 7J23 Punkteanspruchsvoll
Den letzten Queue-Knoten entfernen
Noch nicht begonnen
Aufgabenstellung
Eine verkettete Queue speichert die Referenzen vorn und hinten. Anfangs sind beide None. Nach enqueue(R) wird sofort dequeue() ausgeführt. Welche Werte müssen danach in vorn, hinten stehen? Antworte in dieser Reihenfolge, kommagetrennt.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Nach enqueue auf einer leeren Queue zeigen beide Referenzen auf denselben Knoten.
Nach der anschließenden Entnahme existiert kein erster und kein letzter Queue-Knoten mehr.
Lösung anzeigen
None, None. Nach dem Entfernen des einzigen Knotens ist die Queue leer. Auch hinten darf nicht mehr auf den entfernten Knoten zeigen.