2. Queue

 

 

2.1 Bedienungshinweise

Das QueueApplet wird über zwei Masken bedient. Direkt nach dem Start des Applets ist die Initialisierungsmaske sichtbar. Dort wird im Textfeld die maximale Aufnahmefähigkeit der Queue festgelegt bzw. über den "reset" Button, die Queue entleert. In der Eingabemaske wird über den "enqueue" Button, das im Textfeld spezifizierte Element, in die Queue eingefügt. Durch Klick auf "dequeue" wird das älteste Element aus der Queue entnommen. Zwischen beiden Masken wird über die Buttons "<<" oder ">>" gewechselt.

 

2.2 Funktionsweise

Eine Queue - im Volksmund Warteschlange genannt - funktioniert nach dem FIFO-Prinzip. Das Element, welches zuerst eingefügt wurde, wird als erstes wieder entnommen. Es gibt mehrere Implementierungsvarianten. Eine Möglichkeit wäre eine einfach verkettete Liste. Die Liste hat gegenüber dem Array den Vorteil, daß die Queuelänge vor der Initialisierung nicht bekannt sein muß und eigentlich nur durch die Größe des Speichers begrenzt wird. Es gibt auch noch Queues die auf der Heap Datenstruktur basieren, die sogenannten Priority Queues. Diese sollen hier jedoch nicht weiter betrachtet werden, da sie nicht strikt dem FIFO-Prinzip folgen. Vielmehr existiert dort die Möglichkeit, daß sich bestimmte Elemente (nämlich die mit der höchsten Priorität) an weniger bemittelten vorbeidrängeln. In unserem Applet soll ein Array als Queue herhalten.

Es gibt zwei wichtige Attribute einer Queue: den Kopf (head) bzw. das Ende (tail). Jedes neue Element wird ausschließlich am Ende der Queue eingefügt und am Kopf entnommen. Nach jeder Aktion wird der Kopf (bei Entnahme) bzw. das Ende (bei Einfügen) um 1 Feld erhöht. Damit diese Zeiger die regulären Arraygrenzen nicht verlassen, setzen wir entweder eine Modulo-Funktion (sehr elegant) oder eine Abfrage auf Bereichsüberschreitung (eher performant) ein. Wenn Kopf und Ende auf das gleiche Element zeigen, dann ist die Queue leer. Falls das Ende auf Kopf-1 zeigt, ist die Queue voll. Wir sollten uns immer darüber im klaren sein, daß wir kein Element einer leeren Queue entnehmen dürfen bzw. kein neues Element in eine volle Queue einfügen dürfen.

Hinweis: Der Kopf wird im QueueApplet durch einen blauen Pfeil gekennzeichnet.


© Sven Bürgel, letzte Änderung: 29.01.98