Algorithmen und Datenstrukturen in Pascal Teil 2: Queues
In der heutigen Folge, von Algorithmen und Datenstrukturen, möchte ich Ihnen die Datenstruktur Queue vorstellen. Der Begriff >Queue<, stammt, wie sovieles in der Informatik, aus der Muttersprache des Computers, englisch, und bedeutet übersetzt soviel wie >Warteschlange<. Im Anschluß, an die, in der letzten Folge behandelten, Stacks, handelt es sich auch hier wieder um eine Struktur, zur Organisation von Daten in einer bestimmten Reihenfolge.
Die Bedeutung von Queues
Ausgehend von der deutschen Bezeichnung dieser Struktur, kann man sich bereits ein rudimentäres Bild, sowohl der Struktur, als auch ihrer Anwendungen machen. Es handelt sich bei Queue um den Datentyp, der, zwecks Zwischenspeicherung, Daten aufnehmen kann und diese bei Bedarf, in der Reihenfolge ihres Eintreffens, ausgibt. Die Bezeichnung dieses Prinzips ist FIFO, für First-in-first-out.
Die Anwendungensmöglichkeiten sind vielfältig, aber lassen sich prinzipiell immer wieder auf dieselbe Situation zurückführen:
Es liegt eine Überlast an, die der Rechner zur Zeit nicht bewältigen kann. Es wird also erforderlich, die Überlast zunächst zwischenzuspeichern.
Ein spezielles Beispiel in diesem Zusammenhang, ist die Jobverwaltung in Multitasking-Betriebssystemen. Hier wird sehr oft nach dem Prinzip Round Robin vorgegangen. In Worte gefaßt bedeutet dies etwa, daß man sich die vom System gleichzeitig zu bearbeitenden Routinen in einer Warteschlange organisiert denkt. Diese Routinen bekommen nun nacheinander die Kontrolle über die Zentralrecheneinheit (CPU), können für eine gewisse Zeit ihrer Arbeit nachgehen, und werden dann, sollten sie noch nicht fertig sein, wieder in der Warteschlange vor der CPU eingereiht.
Eine andere sehr oft auftretende Situation, ist die Zwischenspeicherung von Daten vor langsamer Peripherie, z.B. Druckerspooling. Ausgehend davon, daß man ein langsam arbeitendes Peripheriegerät und einen, um Größenordnungen, schnelleren Computer besitzt, werden die Daten, welche an das Peripheriegerät ausgegeben werden sollen, in einem Queue zwischengespeichert. Der Computer kann nun solange anderen Dingen nachgehen, wie das Peripheriegerät noch mit den Daten beschäftigt ist. Wird das Gerät frei, so kann ein weiterer Datensatz überspielt werden, u.s.w.
Beschreibung von Queues
Nach diesen mehr allgemeinen Betrachtungen, werde ich, im Folgenden, eine konkrete Beschreibung der zur Organisation von Queues nötigen Mechanismen vornehmen.
Ähnlich den, in der letzten Folge behandelten, Stacks, müßen auch hier wieder Operationen zum Ein- und Ausfügen von Elementen, eine Operation zum Datentransfer Queue <--> Ausgang, sowie eine Operation zur Kontrolle von underflow-Fehlern (Zugriff, obwohl sich keine Elemente mehr in Warteposition befinden.) zur Verfügung gestellt werden.
In der untenstehenden Tabelle, finden Sie nun alle diese Operationen mit einer genauen Beschreibung ihrer Wirkung. Ein X in der Tabelle steht jeweils für eine Warteschlange, ein A für die Daten einer Warteschlange.
- CREATE(X) initialisiert die Warteschlange X, so daß eine leere Warteschlange vorliegt. Hat X vorher Elemente besessen, so gehen diese durch die erneute Erzeugung verloren.
- IS_EMPTY(X) führt bei X den Check auf die leere Schlange durch. Der Rückgabewert von IS_EMPTY(X) wird somit TRUE, wenn X die leere Warteschlange ist, sowie FALSE, sonst.
- ENTER(X,A) fügt am Ende der Schlange X das Element A ein.
- FRONT(X) liefert das am Schlangenkopf stehende Element.
- REMOVE(X) entfernt das in Warteposition stehende Element aus der Schlange X.
Anmerkung : Die so definierten Parameter implizieren, daß IS_EMPTY(X) und FRONT(X) in der späteren Implementierung Funktionen sein werden, die anderen Operationen dagegen Prozeduren.
Der Zeigercharakter der Struktur
Um sich nun bei der Implementierung nicht auf eine bestimmte Anzahl von Schlangenelementen festzulegen, ist hier, wie schon bei den Stacks, der Gebrauch der dynamischen Speicherverwaltung empfehlenswert.
Dazu definiere ich zunächst einige Typen (Listing 2a). QUEUE_DATA stellt den Typ der Informationen dar und ist, bis auf eine, später erklärte, Einschränkung, vom Benutzer frei wählbar. Im Listing habe ich INTEGER gewählt. Ein Schlangenelement (QUEUE_ELEMENT) besteht nun aus diesen QUEUE_DATA und einem Zeiger auf den Schlangennachfolger, QUEUE_PTR. Zusätzlich zu diesen Typen, muß noch ein Schlangenkopf (QUEUE) definiert werden. Dieser beinhaltet Zeiger auf Anfang und Ende der Warteschlange.
Aus Sicht des Modulanwenders, ist diese Konstruktion sehr einfach zu handhaben, da allein der Schlangenkopf die Informationen enthält, die zur Bearbeitung notwendig sind.
Zur Verdeutlichung des Zeigercharakters dieser Konstruktion und der Wirkung der fünf Operationen auf sie, werde ich drei Abbildungen (2a-2c) benutzen.
Betrachten Sie hierzu bitte zunächst die Legende (Abb.2a). Als erstes treffen wir hier die Charakterisierung eines beliebigen Schlangenelementes an. Sie ist symbolisiert durch zwei Rechtecke. Das größere der beiden stellt die Daten dar, daß kleinere beinhaltet den Zeiger auf den Schlangennachfolger.
Als nächstes befindet sich hier der Schlangenkopf. Das linke Rechteck symbolisiert den Zeiger auf das Schlangenende, also die Stelle, wo neue Elemente eingefügt werden. Das Rechte symbolisiert, analog, die Stelle, wo Elemente abgespalten werden und sich jeweils das Element in Warteposition befindet (FRONT(X)).
Als letztes Symbol der Legende habe ich einen Kreis, zur Charakterisierung des Zeigerwertes NIL, gewählt.
Ausgerüstet mit diesen Symbolen, stellen sich unsere fünf Operationen schon recht sympathisch dar.
- Bei der CREATE(X)-Anweisung wird sowohl der Kopfzeiger, als auch der Endezeiger zu NIL initialisiert (Abb.2a).
- Die IS_EMPTY(X)-Operation überprüft nun auf diesen Zustand.
- Bei der ENTER(X,A)-Operation, müßen nun zwei Fälle unterschieden werden. Zunächst wäre da der Fall des Einfügens eines Elementes in eine leere Liste. Hierbei werden beide Zeiger des Schlangenkopfes auf dieses Element umgesetzt. In Abb. 2b) dagegen sehen Sie nun den allgemeinen Fall des Einfügens eines Elementes in eine schon gefüllte Warteschlange. Die Zeigeroperation erfolgen in drei, in der Abbildung beschriebenen, Schritten.
- Bei der Front(X)- Operation bekommt man nun jeweils Zugriff auf das in Abb.2c) mit A gekennzeichnete Schlangenkopfelement.
- Die nächste, komplexe Operation ist die REMOVE(X)-Operation (Abb.2c). Hier muß auch wieder zwischen Normalfall (Entfernen eines Schlangenelementes aus einer Schlange, mit mindestens einem Elementen) und Spezialfall (Entfernen des letzten Schlangenelementes) unterschieden werden. Der dargestellte Normalfall bedarf wohl keiner weiteren Erläuterung. Der Spezialfall (ein Schlangenelement) macht das Setzen beider Schlangenkopfzeiger auf NIL erforderlich.
Implementierung
Wenn Sie sich nun der Implementierung (Listing 2b) zuwenden, werden Sie feststellen, daß hier eine vollständige Umsetzung der beschriebenen Mechanismen vollzogen wurde. Ein weitergehender Kommentar erübrigt sich somit.
Funktionalitätsschreibweise
Kurz eingehen möchte ich nur noch auf die im Programmkopf aufgeführte Funktionalitätsliste der Operatoren. Wie Sie sicher schon festgestellt haben, handelt es sich dabei nicht nur um eine reine Liste der Parameterdarstellung der aufgeführten FUNCTIONen/PROCEDUREn. Hier wird vielmehr die Gesamtheit der Ein/Ausgaben der Operationen beschrieben, ungeachtet, ob es sich dabei um eine FUNCTION, oder eine PROCEDURE handelt. Diese Systematik, die Ihnen bei diesem, noch recht einfachen, Problem der Queues vielleicht etwas pedantisch erscheinen könnte, wird mir bei den in späteren Folgen auftretenden, abstrakteren, Datenstrukturen, eine wertvolle Hilfe sein.
Doch kommen wir nun zur Anwendung der Queues. Wie sich herausstellen wird, gestaltet diese sich sehr handlich.
Anwendung
Die Anwendung der beiden Module (Typen und Operationen) ist nun denkbar einfach. Nach der Deklaration von Typen und Operationen, erhält man eine Warteschlange durch Vereinbarung einer Variablen vom 'Typ Queue' und einmaligem Aufrufen der PROCEDURE CREATE(X). Dies muß allerdings vor Benutzung durch eine der anderen vier Operationen erfolgen.
. . VAR x : queue; a : queue_data; . . create(x); . .
Bei den anderen Operationen ist nun lediglich darauf zu achten, daß keine lesenden, oder löschenden, Zugriffe auf eine leere Schlange erfolgen. Hierzu sollte vor jedem FRONT(X)-, oder REMOVE(X)-Aufruf, ein Check mit IS_EMPTY(X) erfolgen.
Aussehen kann dies folgendermaßen:
IF NOT is_empty(X) THEN remove(X);
Erwähnen möchte ich nun noch kurz eine lästige Einschränkung von PASCAL. Bei den meisten PASCAL-Versionen (Vielleicht bei allen?), dürfen Funktionen nur einfache Datentypen als Ergebnis besitzen. Dies führt in der Funktion FRONT(X) zu Problemen, wenn QUEUE_DATA kein einfacher Datentyp ist. Um das Konzept nun allgemeiner, wenn auch weniger elegant, zu halten, bietet es sich an, FRONT(X) als PROCEDURE zu formulieren.
PROCEDURE front( x : queue; VAR a : queue_data);
BEGIN {front}
IF NOT(is_empty(x)) THEN
a:=x.first^.data;
END; {front}
Womit dieses Problem umgangen wäre.
Testumgebung
Zur Verdeutlichung der Anwendung von Warteschlangen, habe ich eine kleine Testumgebung für unsere beiden Module geschrieben. Es wird hier ein Queue mit Namen SCHLANGE verwaltet. Auf dieses Queue können nun einfügende (enter(schlange,daten)), oder löschende (remove(schlange)) Zugriffe erfolgen. Ferner kann man sich das in Warteposition befindliche Schlangenelement ausgeben lassen, sowie den Check auf eine leere Warteschlange durchführen.
Beachtenswert ist hierbei eigentlich nur, daß, wie schon oben erwähnt, sämtliche lesenden, oder löschenden Zugriffe auf die Warteschlange mit is_empty(schlange) gesichert sind.
Modularisierung unter PASCAL+
Im Kontext der Anwendung der beiden Module, möchte ich kurz auf modulare Programmierung unter PASCAL+ eingehen. Wie einigen von Ihnen, die mit modularer Programmierung in anderen PASCAL-Dialekten, oder anderen Sprachen, hinreichend vertraut sind, sicher bereits aufgefallen sein wird, benutze ich den Modulbegriff in einem recht weitgefasten Sinne. Statt eigenständigen Objektcode zu erzeugen, der dann vom Linker zum eigentlichen Programm hinzugefügt wird, definiere ich meine Module immer als Header-Datei.
Diese eigentlich merkwürdige Tatsache liegt darin begründet, daß das modulare Programmieren unter PASCAL+ noch merkwürdiger ist. Hier wird nämlich verlangt, daß sämtliche globalen Vereinbarungen im Hauptprogramm, auch in jedem der Module separat und in gleicher Reihenfolge getätigt werden. Eine Eigenart, die die Erzeugung einer Programmbibliothek, oder nur eines allgemein benutzbaren Moduls, unmöglich macht, wenn im Modul Variablen oder eigenständige Typdefinitionen gemacht werden.
Vorausschau
Mit dieser Anmerkung, wäre ich nun am Ende der Queues. In der nächsten Ausgabe der ST-Computer lesen Sie, wenn Sie wollen, einiges über Listen, ihre Implementierung, ihre Anwendung und überhaupt alles, was mir bis dahin dazu einfällt.
Als letzte Anmerkung sei mir gestattet, daß ich eigentlich eine etwas größeres Queueanwendung, als das kleine Testprogramm, geplant hatte. Diese war auch schon programmiert. Unglücklicherweise hat sich dieses Programm aber etwas verselbstständlicht, will sagen, ist zu groß und unkompatibel für ein Beispiel geworden.
Geplant war eine Art Druckerspooler für Graphikdateien unterschiedlicher Formate, sowie Textdateien auf den beiden gängigen Druckertypen ATARI und EPSON-kompatibel. Um Ihnen dieses (klickfertige) Programm aber nicht völlig vorzuenthalten, stelle ich es dem Public Domain Service dieser Zeitschrift incl. Source und Dokumentation zur Verfügung.
Dirk Brockhaus