ADT Schlange = Queue


Eine Datenstruktur zur Zwischenablage von Datenwerten, bei der die Werte in der gleichen Reihenfolge entnommen werden, in der sie eingetragen wurden (First-In-First-Out, FIFO), nennen wir eine (Warte-)Schlange oder Queue. Eine Schlange hat einen Schwanz, an den wir mittels der Operation enqueue Datenelemente anhängen, und einen Kopf, wo wir das aktuell erste Element first(q)  mit der Operation dequeue abholen können; übrig bleibt rest(q). 

Die algebraische Modellierung ist etwas mühsam und benötigt die Hilfsfunktionen first  und rest  vor allem wegen einiger Unvollkommenheiten der üblichen mathematischen Notation.

ADT Queues(T) IS
SORTS:
queue, T, boolean, cardinal
OPERATIONS:
newqueue: queue
enqueue: T queue queue
isempty: queue boolean
length: queue cardinal
dequeue: queue T queue
first: queue T
rest: queue queue
RULES:
isempty(newqueue) = true
isempty(enqueue(x, q)) = false
length(newqueue) = 0
length(enqueue(x, q)) = length(q) + 1
dequeue(q) = <first(q), rest(q)>
first(enqueue(x, q)) = IF isempty(q) THEN x ELSE first(q)
rest(enqueue(x, q)) = IF isempty(q) THEN newqueue
ELSE enqueue(x, rest(q))
END Queues.
Wir besprechen einige Realisierungen im Einzelnen; man macht dabei leicht Fehler, weil es nicht nur den Sonderfall der leeren Schlange  zu berücksichtigen gilt, sondern auch den Fall einer einelementigen Schlange,  bei der Kopf und Schwanz identisch sind.


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36