8. Implementierung mit Reihung

Die obige Schnittstelle kann mit Hilfe einer Reihung (array) als Ringpuffer implementiert werden[1]. Die Grundidee dabei ist, dass jedes Queue-Objekt intern ein Reihungsobjekt (aus Referenzen) pflegt (über die globale Variable inhalt), in dem die einzutragenden Elemente (Objekte vom generischen Typ E) eingehängt werden. Das Queue-Objekt führt dabei Buch über die Anzahl der eingetragenen Elemente (globale Variable anzahl), sowie über ihre Position. Genauer, es muss nur der Index des ältesten Elements (das am längsten wartet) und des jüngsten Elements (das zuletzt eingetragen wurde) gemerkt werden (globale Variablen ältestes und jüngstes). Wenn ein neues Element eingetragen wird, wird der Index des jüngsten inkrementiert (um 1 erhöht) und an diese Stelle wird das neue Element eingehängt. Wenn das älteste Element gelöscht wird, wird der Index ältestes inkrementiert und das nächstälteste wird zum ältesten. Der Platz des gelöschten Elements wird dadurch für eine spätere Eintragung frei.

Wenn ein Index das Ende der Reihung erreicht, würde eine nächste Inkrementierung ArrayIndexOutOfBoundsException auslösen. Wenn jüngstes an dieser Position steht, könnte man vermuten, dass keine weiteren Elemente mehr eingetragen werden können, die Warteschlange sei voll. Es kann jedoch sein, dass in der Zwischenzeit Elemente gelöscht worden sind, d.h. die Anfangsplätze in der Reihung wieder frei sind. Ob das der Fall ist, kann über anzahl überprüft werden (die bei jeder add erhöht, bei jeder remove dekrementiert wird). Wenn also anzahl es erlaubt, kann jüngstes nach der Position length-1 anstelle von length (die eine Ausnahme auslösen würde) wieder auf 0 umgeschaltet werden. Dies kann durch eine if-Abfrage, einfacher aber mit dem Restoperator % bewerkstelligt werden:

jüngstes = (jüngstes + 1) % inhalt.length

Diese Programmzeile ist äquivalent mit

if (jüngstes == inhalt.length-1)
   jüngstes = 0
else
   jüngstes = jüngstes + 1

In remove muss ältestes ähnlich weitergeschaltet werden:

ältestes = (ältestes + 1) % inhalt.length

Diese Technik implementiert einen Ringpuffer:

Abbildung 17: Ringpuffer

Die Datenstruktur des Ringpuffers besteht aus einer Reihung und zwei Indizes, die nur inkrementiert werden, jedoch mit Überlaufprüfung:

Abbildung 18: Datenstruktur des Ringpuffers

Der gestrichelte Pfeil zeigt die Bewegungsrichtung innerhalb der Reihung an.

Somit kann die Schnittstelle Queue folgendermaßen implementiert werden:

/** Array implementation of Queue - ArrayQ.scala*/
import java.util.NoSuchElementException
class ArrayQ[E](size: Int) extends Queue[E] {
   protected var inhalt = new Array[Object](size).asInstanceOf[Array[E]] [2]
   protected var jüngstes = size-1 // irgendwelche Werte [3]
   protected var ältestes = 0 
   protected var anzahl = 0
   clear // eigentliche Initialisierung

   def clear = {
     jüngstes = size-1 // zuletzt besetztes Feld [4]
     ältestes = 0
     anzahl = 0 }

   def isEmpty =
     anzahl == 0

   def isFull =
     anzahl == size

   def add(o: E) = {
     if (isFull)
        throw new IllegalStateException
     anzahl = anzahl + 1 // [5]
     jüngstes = (jüngstes + 1) % inhalt.length // [6]
     inhalt(jüngstes) = o }

   def element: E =
     if (isEmpty)
        throw new NoSuchElementException
     else
        inhalt(ältestes)

   def remove =
     if (isEmpty)
        throw new NoSuchElementException
     else {
        ältestes = (ältestes + 1) % inhalt.length // bei Überlauf wird 0
        anzahl = anzahl - 1 } }

[1] Die folgenden Implementierungen dienen nur zu Lehrzwecken; in den Scala-Bibliotheken gibt es bessere Implementierungen

[2] Von einem Typparameter (wie E) kann kein Objekt (auch kein Array-Objekt) erzeugt werden; deswegen wird Array[Object] erzeugt zu Array[E] mit asInstanceOf konvertiert („gecastet“).

[3] Scala verlangt die Initialisierung globaler Variablen

[4] beim ersten add wird 0

[5] Scala’s Int hat (leider) keinen ++

[6] % bewirkt, dass auf inhalt.length-1 der Wert 0 folg

Version: 5. Dezember 2010