Impressum
< Stack Inhalt Liste >

Queue (Warteschlange)

Eine Queue ist ein FIFO-Puffer. Das heißt, man kann beliebig viele Elemente einfügen (mit enqueue(element)) und entnehmen (mit dequeue()).
Das Element, das als erstes eingefügt wurde, wird als erstes entnommen (FIFO = First-In-First-Out).
Wir kennen Queues aus dem Alltag:

Operationen

Eine Queue hat folgende Opterationen:

Queue in Python

Man kann in Python einen Queue mittels eines Arrays realisieren:
Wenn man sich für die Queue-Operationen in Python Unterprogramm schreibt, sieht das so aus: 
def enqueue(queue, ding):
    queue.append(ding)
    
def dequeue(queue):
    return queue.pop(0)

def isEmpty(queue):
    return len(queue)==0

queue = []
for i in range(1,10):
    enqueue(queue, i)
    print("Nach dem Einfügen von",i,":",queue)

print("auslesen")
while not isEmpty(queue):
    print(dequeue(queue))

Ausprobieren

Aufgaben

  1. In eine Queue werden nacheinander Werte eingefügt und aus ihr entnommen.
    Geben Sie nach jeder Operation den Inhalt der Queue an.
    enqueue(Ding 1)
enqueue(Ding 2)
enqueue(Ding 3)
dequeue()
dequeue()
enqueue(Ding 4)

  2. In einem Callcenter gehen viele Anrufe ein. Bis der Anrufer zu einem Mitarbeiter durchgestellt wird, befindet er sich in einer Warteschlange und hört die lustige Musik der Warteschleife.
    Folgendes ist ein Auszug der Anrufe:
    Um 08:00  enqueue(0731-115)
Um 08:10  enqueue(0731-555 555)
Um 08:20  dequeue()
Um 08:30  enqueue(0900-555)
Um 08:32  dequeue()
    1. Wie viele Anrufer sind um 08:35 noch in der Warteschleife?
    2. Welcher Anrufer ist um 08:35 noch in der Warteschleife?
    3. Welcher Anrufer wird um 08:20 durchgestellt?
    4. Geben Sie die Queue nach jedem enqueue() und dequeue() an.
  3. Am Bahnhof in Ulm warten die Taxis in einer Reihe.
    Neue Taxis stellen sich hinten an und Taxis fahren vorne ab.
    Hier ist ein Auszug aus dem Einfahrt-/Ausfahrtprotokoll:
    09:30 Taxi 123 Einfahrt
    10:29 Taxi 092 Einfahrt
    10:52 Taxi 545 Einfahrt
    11:20 Taxi 222 Einfahrt
    12:14 Taxi 123 Ausfahrt
    12:15 Taxi 092 Ausfahrt
    12:51 Taxi 0815 Einfahrt
    13:29 Taxi 545 Ausfahrt
    14:21 Taxi 222 Ausfahrt
    14:24 Taxi 12 Einfahrt
    15:06 Taxi 123 Einfahrt
    15:33 Taxi 0815 Ausfahrt
    1. Welcher Datenstruktur entspricht dieses Vorgehen und ist dieses Vorgehen gerecht?
    2. Um 12:10 kommt Ute am Taxistand an. Sie will von ihrer Freundin Mia im Taxi 092 gefahren werden. Wie viele Fahrgäste muss sie vorlassen?

    3. Geben Sie die Taxis am Taxi-Stand tabellarisch an.
      Jede Uhrzeit, zu welcher sich etwas verändert ist eine Zeile mit den wartenden Taxis in der richtigen Reihenfolge.