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:
Show code cell content
class Warteschlange:
class Knoten:
def __init__(self, inhalt, naechster=None):
self.inhalt = inhalt
self.naechster = naechster
def __init__(self):
self.kopf: Warteschlange.Knoten|None = None
self.ende: Warteschlange.Knoten|None = None
self.hoehe = 0
def enqueue(self, daten):
"""fügt ein neues Element in die Warteschlange ein"""
neuer_knoten = Warteschlange.Knoten(daten, None)
if self.kopf is None:
self.kopf = neuer_knoten
else:
self.ende.naechster = neuer_knoten
self.ende = neuer_knoten
self.hoehe += 1
def dequeue(self):
"""entfernt das vorderste Element aus der Warteschlange und gibt es zurück"""
if self.kopf is None:
raise IndexError("Dequeue-Operation auf leerer Warteschlange nicht möglich")
inhalt = self.kopf.inhalt
self.kopf = self.kopf.naechster
if self.kopf is None:
self.ende = None
self.hoehe -= 1
return inhalt
def ist_leer(self):
"""gibt True zurück, wenn die Warterschlange leer ist, sonst False"""
return self.kopf is None
def anzahl_elemente(self):
"""gibt die Anzahl der Elemente in der Warteschlange 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
Leere Warteschlange ist leer: True
Anna, Berta und Cora stellen sich nacheinander an
Länge der Warteschlange: 3
Die erste Kundin wird bedient: Anna
Länge der Warteschlange: 2
Die zweite Kundin wird bedient: Berta
Dora stellt sich an
Länge der Warteschlange: 2
Weitere Kundinnen stellen sich an: ['Ella', 'Frieda', 'Greta']
Länge der Warteschlange: 5
Alle verbleibenden Kundinnen werden bedient:
Cora
Dora
Ella
Frieda
Greta
Länge der Warteschlange: 0