Schlangen (4)

Für Schlangen von prinzipiell unbekannter Länge bietet sich eine Realisierung über verkettete Listen an. Wir wissen bereits, daß wir am Ende einer Liste leicht Elemente anhängen, und am Anfang Elemente löschen können. Zur Beschreibung einer Schlange brauchen wir demnach Informationen darüber, wo Kopf und Schwanz liegen, und vielleicht auch noch die Länge, falls sie oft benötigt wird. Diese Beschreibungsgrößen packen wir in einen Beschreibungsblock, den wir über einen Pointer adressieren. Für die Listenelemente selbst können wir es bei den schon früher verwendeten Datentypen belassen: 
TYPE queue = POINTER TO qrecord;
   qrecord = RECORD l: CARDINAL;
                    hd, tl: liste;
             END;
Eine leere Schlange hat einen nichtleeren Beschreibungsblock, aber die daran hängende Liste ist leer; wir setzen (redundant) hd = tl = NIL und l = 0. Wird eine Schlange nicht mehr gebraucht, so müssen wir nicht nur die Listenelemente, sondern auch den Beschreibungskopf freigeben! 
PROCEDURE newqueue(VAR q: queue);
BEGIN NEW(q);
      WITH q^ DO hd := NIL; tl := NIL; l := 0;
      END;
END newqueue;

PROCEDURE isempty(q: queue): BOOLEAN;
BEGIN RETURN q^.hd = NIL;
END isempty;

PROCEDURE killqueue(VAR q: queue);
BEGIN delete(q^.hd);
      DISPOSE(q);
END killqueue;
Bei einer einelementigen  Schlange ist der Kopf gleichzeitig das letzte Element; dies gibt beim Eintragen und Aushängen Sonderfälle. Das versuchte Aushängen aus einer leeren Schlange fangen wir nicht dynamisch ab; der Benutzer kann (und sollte) es durch Abfragen selbst vermeiden!
zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36