Schlangen (2)

Ist die Maximallänge einer Schlange von vorne herein beschränkt, so kann man sie in einem Array fester Länge unterbringen, den man zu einem logischen Ringpuffer schließt. Da im Allgemeinen nur ein Teil des Array belegt sein wird, müssen wir uns die Position von Kopf und Schwanz merken, und wir rechnen auch die aktuelle Länge mit.

Schlange im Array
Zur Einübung formulieren wir unsre Lösung mittels eines opaken Typs queue , den wir als Pointer auf einen Verbund unserer Beschreibungsgrößen und Datenwerte realisieren. Die einzelnen Felder des Verbundes sprechen wir über eine WITH-Anweisung an; das ist bequem. 
TYPE queue = POINTER TO qrecord;
     index = 1 .. max; (* maximaler Umfang *)
     storeTyp = ARRAY [index] OF atom;
     qrecord = RECORD store: StoreTyp;
                      hd, tl: index;
                      l: CARDINAL;
               END;

PROCEDURE newqueue(VAR q: queue);
BEGIN NEW(q);
      WITH q^ DO l := 0; hd := 1; tl := max;
      END;
END newqueue;
Die hier gesetzten Anfangswerte für hd und tl ergeben sich beim Austragen des einzigen Elements einer einelementigen Schlange, die ganz am Ende des Array liegt; andere Besetzungen wären ebenso möglich. Eine Schlange ist leer genau dann, wenn sie die Länge Null hat.

Achtung!  Eine Schlange der maximalen  Länge l=max sieht bei dieser Implementierung bis auf die Längenangabe genauso  wie eine leere  Schlange aus! Daher müssen wir hier unbedingt die Länge mitrechnen, selbst wenn sie der Anwender nicht brauchen sollte.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36