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