Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Queue

Queue

Eine Queue funktioniert genau umgekehrt zu einem Stack. Das Element, welches als Erstes eingefügt wurde, wird auch als Erstes wieder herausgenommen. Das Prinzip ist von der Warteschlange an einer Supermarktkasse her vertraut.

ADT Queue: = ggfs. leere Folge von Elementen zusammen mit einem ggfs. undefinierten Frontelement

Grafisch stellt sich die Situation wie folgt dar:

Graphische Darstellung einer Queue

Bei einer Queue kann man nur am Kopf lesen und nur am Schwanz einfügen. Dieses Verhalten kennt man von Warteschlangen. Elemente innerhalb der Warteschlange werden nicht verschoben.

Eine Queue kennt folgende Operationen

• newQueue() $\rightarrow$ Queue
• isEmpty(q) $\rightarrow$ boolean
• enq(x, q) $\rightarrow$ Queue
• front(q) $\rightarrow$ Element
• deq(q) $\rightarrow$ Queue

Die Operation zum Anfügen heißt enq im Gegensatz zum Stack für sie jedoch am Ende ein. Die deq Operation entfernt das erste Element am Kopf der Schlage. Durch die Operation front wird das Kopfelement der Schlange zurückgeliefert, jedoch nicht entfernt.

Praktische Beispiele für die Verwendung von Queue sind einfache Prozessoren, welche die Befehle aus dem Befehlsspeicher nacheinander abarbeiten. Ein weiteres Beispiel sind Callcenter. Hier ist zu beachten, dass es mehrere Verbraucher gibt, welche Elemente aus der Queue entfernen. Somit sind Synchronisationsstrukturen notwendig. Auch bei Webservern finden Queues Verwendung, da sie ihre Anfragen in der Reihenfolge des Eingangs bearbeiten.

Im folgenden Beispiel betrachten wir eine Liste zur Implementierung einer Queue:

Einfügen eines neuen Elements in eine als Liste implementierte Queue

Neben, der Liste mit den Elementen x, y und z benötigen wir sowohl einen Zeiger head auf den Kopf der Liste als auch einen Zeiger tail auf das letzte Element der Liste

deq()
  head := head.next