11.9 Queue, die Schlange 

Eine Queue arbeitet nach dem FIFO-Prinzip (First-In-First-Out) und unterscheidet sich von einem Stack durch den Zugriff auf die Elemente. Bei einer Queue werden die Elemente, die zuerst eingefügt wurden, zuerst herausgegeben, getreu dem Motto: »Wer zuerst kommt, malt zuerst.«

In der Klassenbibliothek von Java gibt es bisher keine Queue-Klasse. Wir wollen daher eine einfache und kurz gehaltene Klasse programmieren. Wir wählen hier keine effiziente Implementierung auf der Basis eines Arrays von Object, sondern bedienen uns der Klasse Vector. Hier wiederholen wir allerdings nicht den Designfehler und erben von Vector, sondern benutzen ihn nur. Das Hinzufügen eines Elements ist in einer Queue sehr einfach und es kann sofort an den Vektor weitergeleitet werden. Wird ein Element angefordert, so nehmen wir das erste Element aus dem Vektor. Nun müssen alle anderen Elemente nachrutschen. Schlaue Implementierungen würden einen Ausschnitt eines zyklisch indizierten Arrays als Ringspeicher verwenden, aber, wie gesagt, wir machen es uns einfach und denken nicht an die Geschwindigkeit – das erste Element wird daher mit removeElementAt(0) gelöscht.

Listing 11.7   QueueTest.java, Teil 1

import java.util.*;

class Queue
{
  public void enqueue( Object newElement )
  {
    vectorQueue.addElement( newElement );
  }

  public synchronized Object dequeue()
  {
    if ( !empty() )
    {
      Object first = vectorQueue.elementAt( 0 );
      vectorQueue.removeElementAt( 0 );

      return first;
    }
    return null;
  }

  public boolean empty()
  {
    return vectorQueue.isEmpty();
  }

  private Vector vectorQueue = new Vector();
}

dequeue() ist so implementiert, dass null als Endelement eingeführt wird. In Vector ist null auch als normales Element erlaubt.

Nun benötigen wir nur noch eine kleine Klasse zum Testen. Sie füllt die Schlange mit einigen Werten und liest sie dann wieder aus. Hier ist es wichtig, mit empty() nachzufragen, ob noch Elemente in der Queue sind. Es wurde eine Implementierung gewählt, die bei leerer Queue statt des nicht vorhandenen Elements einfach null liefert. Es bleibt als Übung den Lesern überlassen, die Klasse so zu erweitern, dass die dequeue()-Methode gegebenenfalls eine Exception auslöst.

Listing 11.8   QueueTest.java, Teil 2

public class QueueTest
{
  public static void main( String args[] )
  {
    Queue queue = new Queue();
    queue.enqueue( "Fischers" );
    queue.enqueue( "Fritze" );
    queue.enqueue( "fischt" );
    queue.enqueue( "frische" );
    queue.enqueue( "Fische" );
    queue.dequeue();
    queue.enqueue( "Nein, es war Paul!" );
    while ( !queue.empty() )
      System.out.println( queue.dequeue() );
  }
}