Schlange

Einführung

In der Informatik bezeichnet eine Warteschlange (englisch queue) eine häufig eingesetzte dynamische Datenstruktur. Sie dient zur Zwischenspeicherung von Objekten in einer Reihenfolge, bevor diese weiterverarbeitet werden. Objekte der Klasse Queue (Warteschlange) verwalten beliebige Objekte nach dem First-In-First-Out-Prinzip, d.h., das zuerst abgelegte Objekt wird als erstes wieder entnommen.

Man kann sich eine Warteschlange wie eine Warteschlange von Kunden an einer Kasse vorstellen. Der Letzte, der sich in die Schlange stellt, wird auch als letzter bedient. Umgekehrt wird derjenige, der sich als erstes angestellt hat, als erster bedient (Quelle http://de.wikipedia.org/wiki/Warteschlange_%28Datenstruktur%29).

Mit enter (bzw. enqueue) wird ein neuer Wert (3) der Schlange hinzugefügt, und mit leave (bzw. dequeue) das am längsten gespeicherte Element (37) herausgenommen. Der einzige lesende Zugriff erfolgt mit front

und liefert das erste gespeicherte Element der Queue (hier im Beispiel 37, natürlich unter der Annahme, dass die Operation leave (bzw. dequeue) noch nicht ausgeführt wurde!).

Aufbau

Eine Schlange sollte über folgende Methoden bzw. Konstruktoren verfügen:

Konstruktor

• Queue(): Eine leere Schlange wird erzeugt.

Methoden

• boolean isEmpty(): Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthält, sonst liefert sie den Wert false.

• void enqueue(Object pObject): Das Objekt pObject wird an die Schlange angehängt. Falls pObject gleich null ist, bleibt die Schlange unverändert.

• void dequeue(): Das erste Objekt wird aus der Schlange entfernt. Falls die Schlange leer ist, wird sie nicht verändert.

• Object front(): Die Anfrage liefert das erste Objekt der Schlange. Die Schlange bleibt unverändert. Falls die Schlange leer ist, wird null zurück gegeben.