Titel   Inhalt   Suchen   Index   API  Go To Java 2, Zweite Auflage, Handbuch der Java-Programmierung
 <<    <     >    >>  Kapitel 15 - Collections II

15.4 Eine eigene Queue-Klasse



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:

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 next 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   API  Go To Java 2, Zweite Auflage, Addison Wesley, Version 2.0
 <<    <     >    >>  © 2000 Guido Krüger, http://www.gkrueger.com