Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


3. Elementare Datenstrukturen



Schlangen

Eine weitere grundlegende Datenstruktur mit beschränktem Zugriff wird Schlange genannt. Auch diesmal werden nur zwei elementare Operationen benutzt: Man kann ein Element am Anfang in die Schlange einfügen und ein Element vom Ende entfernen. Vielleicht sollte das Schubfach »Eingänge« unseres vielbeschäftigten Beamten wie eine Schlange funktionieren, da in diesem Falle die Arbeit, die zuerst eingeht, auch zuerst erledigt würde. In einem Stapel kann etwas am Boden vergraben bleiben, in einer Schlange dagegen wird alles in der Reihenfolge des Eintreffens bearbeitet.

Obwohl man Stapel häufiger als Schlangen vorfindet, was in ihrem grundlegenden Zusammenhang mit der Rekursion begründet ist (siehe Kapitel 5), werden wir auch auf Algorithmen stoßen, für die die Schlange die natürliche Datenstruktur ist. Von Stapeln wird gesagt, daß sie nach dem Prinzip »last in, first out« (LIFO) arbeiten, während für Schlangen das Prinzip »first in, first out« (FIFO) gilt.

Die Realisierung der Schlangenoperationen mittels einer verketteten Liste ist sehr einfach und wird dem Leser als Übung überlassen. Wie bei Stapeln kann auch ein Feld verwendet werden, wenn sich, wie in der folgenden Implementation, die maximale Größe abschätzen läßt:

    const max=100;
    var queue: array[0..max] of integer; 
        head,tail: integer;
    procedure put(v: integer);
      begin 
      queue[tail]:=v; tail:=tail+1;
      if tail>max then tail:=0
      end;
    function get: integer;
      begin 
      get:=queue[head]; head:=head+1;
      if head>max then head:=0
      end;
    procedure queueinitialize;
      begin head:=0; tail:=0 end;
    function queueempty: boolean;
      begin queueempty:=(head=tail) end;

Es ist notwendig, zwei Indizes festzuhalten; einen für den Anfang der Schlange (head) und einen für das Ende (tail). Den Inhalt der Schlange bilden alle Elemente im Feld zwischen head und tail, wobei das »Umlenken« zurück auf 0 zu berücksichtigen ist, wenn das Ende des Feldes erreicht wird. Falls head = tail gilt, wird die Schlange als leer definiert; falls head = tail+1 oder tail = max und head = 0 gilt, so wird sie als voll definiert.

Abbildung 3.8 zeigt, wie sich eine Beispiel-Schlange in Folge der Reihe von get- und put-Operationen verändert, die sich aus der Eingabefolge

A * S A * M * P * L E * Q * * * U * E U * * E *

ergeben.

Das Auftreten eines Buchstaben bedeutet »Setzen« (put) (des Buchstaben); das Sternchen bedeutet »Holen« (get).

Abbildung 3.8
Abbildung 3.8 Dynamische Merkmale einer Schlange.

In Kapitel 20 treffen wir auf eine deque (»double-ended queue«, Warteschlange mit beidseitigem Zugriff), wobei es sich um eine Kombination eines Stapels und einer Schlange handelt. In den Kapiteln 4 und 30 erörtern wir grundlegende Beispiele, die die Anwendung einer Schlange als einen Mechanismus, der die Untersuchung von Bäumen und Graphen ermöglicht, erfordern.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]