Stack und Queue

Als Spezialfall der Liste sind sich Stack und Queue sehr ähnlich, weshalb sie oft gemeinsam besprochen werden. Die Queue (Schlange) ist eine FIFO-Datenstruktur (first in, first out) - die Objekte werden in der Reihenfolge verwaltet, in der sie in die Datenstruktur eingefügt worden sind. Direkter Zugriff besteht nur auf das vorderste Element der Schlange (den Kopf), eingefügt wird immer hinten (am Schlangenende). Der Stack (Stapel) hingegen wird als LIFO-Datenstruktur (last in, first out) bezeichnet. Hier werden neue Objekte immer oben auf den Stapel gelegt, direkter Zugriff besteht ebenfalls nur auf das oberste Objekt des Stapels.

Einen Stack aufbauen

Wie bei einer Liste ist beim Erzeugen eines Stacks zunächst die Klasse der Objekte anzugeben, die im Stack verwaltet werden sollen. Im nachfolgenden Beispiel werden drei Zeichenketten auf den Stack gelegt. Durch die LIFO-Struktur ergibt sich auf dem Stapel von oben nach unten gesehen die Abfolge Hans - Maria - Manfred.

String s1 = "Manfred";
String s2 = "Maria";
String s3 = "Hans";

Stack<String> s = new Stack<String>();

s.push(s1);
s.push(s2);
s.push(s3);

Einen Stack durchlaufen

Der Stapel kann mit einer Schleife leicht von oben nach unten durchlaufen werden.

Wichtig: Dabei wird der Stapel abgebaut, d.h. der Zugriff auf die Objekte geht verloren. Ist dies unerwünscht, müssen die einzelnen Objekte während des Durchlaufs in einer anderen Datenstruktur zwischengespeichert werden.

while (!s.isEmpty()) {

    String aktuell = s.top();

    System.out.println(aktuell);

    s.pop();
}

Eine Queue aufbauen

Wie bei einer Liste ist beim Erzeugen einer Queue zunächst die Klasse der Objekte anzugeben, die in der Queue verwaltet werden sollen. Im nachfolgenden Beispiel werden drei Zeichenketten in die Schlange eingefügt. Durch die FIFO-Struktur ergibt sich in der Schlange die Abfolge Manfred - Maria - Hans.

String s1 = "Manfred";
String s2 = "Maria";
String s3 = "Hans";

Queue<String> s = new Queue<String>();

s.enqueue(s1);
s.enqueue(s2);
s.enqueue(s3);

Eine Queue durchlaufen

Eine Schlange kann mit einer Schleife leicht von vorn nach hinten durchlaufen werden.

Wichtig: Dabei wird die Schlange abgebaut, d.h. der Zugriff auf die Objekte geht verloren. Ist dies unerwünscht, müssen die einzelnen Objekte während des Durchlaufs in einer anderen Datenstruktur zwischengespeichert werden.

while (!s.isEmpty()) {

     String aktuell = s.front();

    System.out.println(aktuell);

    s.dequeue();
}

results matching ""

    No results matching ""