Python 3 - Lernen und professionell anwenden

Kapitel 27

Modellieren mit Kellern, Schlangen und Graphen

750

27.2 Queue (Schlange)

Der abstrakte Datentyp Queue stellt Warteschlangen dar. Sie sind den Menschen in moder-

nen Industriegesellschaften bestens bekannt. Staus auf der Autobahn, Warteschlangen

beim Check-in am Flughafen oder am Skilift gehören zu den eher unangenehmen Facetten

unseres Alltags. Die Grundidee einer Warteschlange – sagen wir am Schalter einer Air-

line – ist, dass man sich hinten anstellen muss und derjenige, der zuerst gekommen ist und

deshalb ganz vorne in der Schlange steht, als Erster bedient wird. Man nennt dieses Prinzip

first in first out oder kurz FIFO. Die Operationen, die Queues ausführen können, sind

folgende:

쐽 Eine neue leere Queue erzeugen: Queue()

쐽

Ein Objekt hinten an die Schlange anhängen: enqueue()

쐽

Ein Objekt vorne von der Schlange entfernen: dequeue()

쐽

Das vorderste Element lesen, ohne es aus der Schlange zu entfernen: front()

쐽

Testen, ob die Schlange leer ist: empty()

Das folgende Skript zeigt, wie man eine Schlange mit Python auf der Basis einer Liste

implementieren kann. Achtung! Speichern Sie das Skript nicht unter dem Namen

queue.py

ab. Denn es gibt bereits ein Standardmodul queue, in dem threadsichere Queues definiert

sind (siehe nächster Abschnitt).

Im folgenden Skript wird eine Schlange mit Inhalt gefüllt und anschließend der Inhalt wie-

der ausgegeben. Die Items werden in der gleichen Reihenfolge aus der Schlange geholt, wie

sie eingegeben wurden.

# queue_.py

class Queue:

def __init__(self):

self.__content=[]

def empty(self):

return self.__content ==[]

def enqueue(self, item):

self.__content += [item]

def dequeue(self):

if not self.empty():

item = self.__liste[0]

del self.__content[0]

r etu r n ite m

def front (self):

if not self.empty():

return self.__content[0]