Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage
<< | < | > | >> | API | Kapitel 15 - Collections II

## 15.4 Eine eigene Queue-Klasse

- 15.4 Eine eigene Queue-Klasse
  - 15.4.1 Anforderungen
  - 15.4.2 Implementierung

### 15.4.1 Anforderungen

Nachdem wir gezeigt haben, wie vordefinierte Collections verwendet werden, wollen wir uns nun ansehen, wie man eigene Collections erstellen kann. Wir wollen dazu die Datenstruktur einer Queue implementieren, die folgende Eigenschaften hat:

- Zu Beginn ist die Queue leer.
- Durch Aufruf von `add` wird ein neues Element am Ende der Queue angefügt.
- Ein Aufruf von `retrieve` gibt das erste Element der Queue zurück und entfernt es aus der Queue. Besitzt die Queue keine Elemente, wird eine Ausnahme des Typs `NoSuchElementException` ausgelöst.
- Die Methode `size` liefert die Anzahl der Elemente in der Queue.
- Mit `clear` werden alle Elemente aus der Queue entfernt.
- Die Methode `iterator` liefert einen Iterator für alle Elemente der Queue. Beim Aufruf von `remove` wird eine Ausnahme des Typs `UnsupportedOperationException` ausgelöst.

Die Elemente sollen als einfach verkettete Liste von Elementen gehalten werden. Jedes Element wird in einer Instanz der lokalen Klasse `ElementWrapper` gehalten, die neben dem Element selbst auch den Zeiger auf sein Nachfolgeelement verwaltet. Um (ganz nebenbei) den Umgang mit Listenstrukturen mit Zeigern zu zeigen, wollen wir die Daten nicht einer Collection des Typs `LinkedList` halten, sondern die Zeigeroperationen selbst implementieren.

### 15.4.2 Implementierung

Zunächst definieren wir ein Interface `Queue`, in dem wir die abstrakten Eigenschaften unserer Queue-Klasse spezifizieren:

    001 /* Queue.java */
    002
    003 import java.util.*;
    004
    005 /**
    006  * Das Interface der Queue-Collection.
    007  */
    008 public interface Queue
    009 {
    010   /**
    011    * Fügt das Element o am Ende der Queue an. Falls
    012    * keine Ausnahme ausgelöst wurde, gibt die Methode
    013    * true zurück.
    014    */
    015   public boolean add(Object o);
    016
    017   /**
    018    * Liefert das erste Element der Queue und entfernt es
    019    * daraus. Falls die Queue leer ist, wird eine Ausnahme
    020    * des Typs NoSuchElementException ausgelöst.
    021    */
    022   public Object retrieve()
    023   throws NoSuchElementException;
    024
    025   /**
    026    * Liefert die Anzahl der Elemente der Queue.
    027    */
    028   public int size();
    029
    030   /**
    031    * Entfernt alle Elemente aus der Queue.
    032    */
    033   public void clear();
    034
    035   /**
    036    * Liefert einen Iterator über alle Elemente der Queue.
    037    */
    038   public Iterator iterator();
    039 }
| Queue.java

Listing 15.3: Das Interface Queue

Dieses Interface kann nun verwendet werden, um konkrete Ausprägungen einer Queue zu implementieren. Wir wollen die Queue als verkettete Liste realisieren und definieren dazu die Klasse `LinkedQueue`:

    001 /* LinkedQueue.java */
    002
    003 import java.util.*;
    004
    005 /**
    006  * Die folgende Klasse realisiert eine Queue-Collection
    007  * auf der Basis einer einfach verketteten linearen Liste.
    008  * Die LinkedQueue kann im Prinzip beliebig viele Elemente
    009  * aufnehmen. Die Laufzeiten der Einfüge- und Löschmethoden
    010  * sind O(1). Der von iterator() gelieferte Iterator
    011  * besitzt KEINE Implementierung der Methode remove().
    012  */
    013 public class LinkedQueue
    014 implements Queue
    015 {
    016   protected ElementWrapper first;
    017   protected ElementWrapper last;
    018   protected int count;
    019
    020   public LinkedQueue()
    021   {
    022     first = last = null;
    023     count = 0;
    024   }
    025
    026   public boolean add(Object o)
    027   {
    028     if (count == 0) {
    029       //insert first element
    030       first = new ElementWrapper();
    031       last = first;
    032       count = 1;
    033     } else {
    034       //insert element into non-empty queue
    035       last.next = new ElementWrapper();
    036       last = last.next;
    037       ++count;
    038     }
    039     last.element = o;
    040     last.next = null;
    041     return true;
    042   }
    043
    044   public Object retrieve()
    045   throws NoSuchElementException
    046   {
    047     if (count <= 0) {
    048       throw new NoSuchElementException();
    049     }
    050     ElementWrapper ret = first;
    051     --count;
    052     first = first.next;
    053     if (first == null) {
    054       last = null;
    055       count = 0;
    056     }
    057     return ret.element;
    058   }
    059
    060   public int size()
    061   {
    062     return count;
    063   }
    064
    065   public void clear()
    066   {
    067     while (first != null) {
    068       ElementWrapper tmp = first;
    069       first = first.next;
    070       tmp.next = null;
    071     }
    072     first = last = null;
    073     count = 0;
    074   }
    075
    076   public Iterator iterator()
    077   {
    078     return new Iterator()
    079     {
    080       ElementWrapper tmp = first;
    081
    082       public boolean hasNext()
    083       {
    084         return tmp != null;
    085       }
    086
    087       public Object next()
    088       {
    089         if (tmp == null) {
    090           throw new NoSuchElementException();
    091         }
    092         Object ret = tmp.element;
    093         tmp = tmp.next;
    094         return ret;
    095       }
    096
    097       public void remove()
    098       {
    099         throw new UnsupportedOperationException();
    100       }
    101     };
    102   }
    103
    104   /**
    105    * Lokale Wrapperklasse für die Queue-Elemente.
    106    */
    107   class ElementWrapper
    108   {
    109     public Object element;
    110     public ElementWrapper next;
    111   }
    112 }
| LinkedQueue.java

Listing 15.4: Die Klasse LinkedQueue

Die einzelnen Elemente der Queue werden in Objekten der Wrapperklasse `ElementWrapper` gehalten. Die beiden `ElementWrapper`-Zeiger `first` und `last` zeigen auf das erste bzw. letzte Element der Liste und werden zum Einfügen und Löschen von Elementen gebraucht. Der Zähler `count` hält die Anzahl der Elemente der Queue und wurde eingeführt, um die Methode `size` performant implementieren zu können. Die Methoden `add` und `retrieve` führen die erforderlichen Zeigeroperationen aus, um Elemente einzufügen bzw. zu entfernen, sie sollen hier nicht näher erläutert werden. In `clear` werden alle Elemente durchlaufen und ihr jeweiliger Nachfolgezeiger explizit auf `null` gesetzt, um dem Garbage Collector die Arbeit zu erleichtern.

Interessanter ist die Implementierung von `iterator`. Hier wird eine anonyme lokale Klasse definiert und zurückgegeben, die das Interface `Iterator` implementiert. Sie besitzt eine Membervariable `tmp`, mit dem die Elemente der Queue nacheinander durchlaufen werden. Wichtig ist dabei, daß `tmp` auf den Originaldaten der Liste arbeitet; es ist nicht nötig, Elemente oder Zeiger zu kopieren (dieses Prinzip ist auch der Schlüssel zur Implementierung der Methode `remove`, die wir hier nicht realisiert haben). `hasNext` muß also lediglich prüfen, ob `tmp` der Leerzeiger ist, was sowohl bei leerer Queue als auch nach Ende des Durchlaufs der Fall ist. `next` führt diese Prüfung ebenfalls aus, liefert gegebenenfalls das im Wrapperobjekt enthaltene Element zurück und stellt `tmp` auf das nächste Element.

|  | Die hier gezeigte Anwendung von anonymen lokalen Klassen ist durchaus üblich und wird meist auch von den JDK-Klassen zur Implementierung der Methode `iterator` verwendet. Prägen Sie sich diese Vorgehensweise ein, denn sie zeigt ein wichtiges und häufig angewendetes Designprinzip in Java. Weitere Hinweise zu anonymen und lokalen Klassen sind in Abschnitt 10.1 zu finden. |  |
Hinweis

Abschließend wollen wir uns noch ein Beispiel für die Anwendung unserer Queue ansehen:

    001 /* Listing1505.java */
    002
    003 import java.util.*;
    004
    005 public class Listing1505
    006 {
    007   public static void main(String[] args)
    008   {
    009     //Erzeugen der Queue
    010     LinkedQueue q = new LinkedQueue();
    011     for (int i = 1; i <= 20; ++i) {
    012       if (i % 4 == 0) {
    013         System.out.println(
    014         "Lösche: " + (String)q.retrieve()
    015         );
    016       } else {
    017         q.add("" + i);
    018       }
    019     }
    020     //Ausgeben aller Elemente
    021     Iterator it = q.iterator();
    022     while (it.hasNext()) {
    023       System.out.println((String)it.next());
    024     }
    025   }
    026 }
| Listing1505.java

Listing 15.5: Anwendung der Queue-Klasse

Das Programm füllt die Queue, indem eine Schleife von 1 bis 20 durchlaufen wird. Ist der Schleifenzähler durch vier teilbar, wird das vorderste Element der Queue entfernt, andernfalls wird der Zähler in einen `String` konvertiert und an das Ende der Queue angehängt. Nach Ende der Schleife enthält die Queue also die Strings "1", "2", ..., "20", sofern sie nicht durch vier teilbar sind, und abzüglich der ersten fünf Elemente, die durch den Aufruf von `retrieve` entfernt wurden. Die Ausgabe des Programms ist demnach:

    Lösche: 1
    Lösche: 2
    Lösche: 3
    Lösche: 5
    Lösche: 6
    7
    9
    10
    11
    13
    14
    15
    17
    18
    19

Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage, Addison Wesley, Version 3.0
<< | < | > | >> | API | © 1998-2002 Guido Krüger, http://www.javabuch.de