4.3. Warteschlangen#
Warteschlangen (engl. Queue) arbeiten nach dem FIFO-Prinzip (First In, First Out), d.h.
wer zuerst kommt, wird zuerst bedient. Konkret bedeutet das, dass ein neues Element
hinten an die Warteschlange angehängt werden (mit der Operation queue()) und Elemente vorne aus der
Warteschlange entnommen werden (mit der Operation dequeue()).
Abb. 4.2 Klassendiagramm für den Datentyp Warteschlange (Queue) (FoSa 5.3)#
Aufgabe:
Nimm den folgenden Code als Vorlage und baue daraus die Klasse Warteschlange,
entsprechend dem UML-Diagramm aus Abb. 4.2.
Hinweis
Du brauchst ein zusätzliches Attribut. Das Klassendiagramm zeigt dir, welches!
Ändere auch die Methodennamen und Kommentare.
# Nimm diese Klasse als Vorlage und baue sie in die Klasse Warteschlange um
class Stapel:
class Knoten:
def __init__(self, inhalt, naechster=None):
self.inhalt = inhalt
self.naechster = naechster
def __init__(self):
self.anfang: Stapel.Knoten|None = None
self.hoehe = 0
def push(self, daten):
"""legt ein neues Element auf den Stapel"""
neuer_knoten = Stapel.Knoten(daten, self.anfang)
self.anfang = neuer_knoten
self.hoehe += 1
def pop(self):
"""entfernt das oberste Element vom Stapel und gibt es zurück"""
if self.anfang is None:
raise IndexError("Pop-Operation auf leerem Stapel nicht möglich")
inhalt = self.anfang.inhalt
self.anfang = self.anfang.naechster
self.hoehe -= 1
return inhalt
def top(self):
"""gibt das oberste Element des Stapels zurück, ohne es zu entfernen"""
if self.anfang is None:
raise IndexError("Top-Operation auf leerem Stapel nicht möglich")
return self.anfang.inhalt
def ist_leer(self):
"""gibt True zurück, wenn der Stapel leer ist, sonst False"""
return self.anfang is None
def anzahl_elemente(self):
"""gibt die Anzahl der Elemente auf dem Stapel zurück"""
return self.hoehe
# Test
print("Tests für Warteschlange")
q = Warteschlange()
print("Leere Warteschlange ist leer:", q.ist_leer())
print("Anna, Berta und Cora stellen sich nacheinander an")
q.enqueue("Anna")
q.enqueue("Berta")
q.enqueue("Cora")
print("Länge der Warteschlange:", q.anzahl_elemente())
erste = q.dequeue()
print("Die erste Kundin wird bedient:", erste)
print("Länge der Warteschlange:", q.anzahl_elemente())
print("Die zweite Kundin wird bedient:", q.dequeue())
print("Dora stellt sich an")
q.enqueue("Dora")
print("Länge der Warteschlange:", q.anzahl_elemente())
weitere = ["Ella", "Frieda", "Greta"]
print("Weitere Kundinnen stellen sich an:", weitere)
for kundin in weitere:
q.enqueue(kundin)
print("Länge der Warteschlange:", q.anzahl_elemente())
print("Alle verbleibenden Kundinnen werden bedient:")
while not q.ist_leer():
print(q.dequeue())
print("Länge der Warteschlange:", q.anzahl_elemente())
Tests für Warteschlange
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
Cell In[1], line 46
44 # Test
45 print("Tests für Warteschlange")
---> 46 q = Warteschlange()
47 print("Leere Warteschlange ist leer:", q.ist_leer())
48 print("Anna, Berta und Cora stellen sich nacheinander an")
NameError: name 'Warteschlange' is not defined
Lösung: