3.2 Beschränkter Zugriff: Stapel (Stack) und Warteschlangen (Queue)

Im ersten Kapitel lernen wir einige Datenstrukturen kennen, die sich hervorragend eignen, wenn die Daten in einer festen, einfachen Reihenfolge erzeugt, gelesen und entfernt wereden.

Stapel (Stacks)

Ein Stapel ist eine Datenstruktur, der zwei Operationen unterstützt :

  1. push x: das Element \(x\) wird auf einen Stapel bereits existierender Elemente "obenauf" gelegt.
  2. pop: das oberste Element des Stapels wird entfernt.

Stack mit Hilfe von Arrays

Übungsaufgabe Führen Sie die Implementierung von Stack.java mit Arrays zu Ende und testen Sie sie. Ihre Klasse Stack sollte die folgenden zwei Funktionen implementieren: 
public String pop();
public void push (String x);

Mit new Stack() sollte ein leerer Stack erstellt werden.

Hinweis. Speichern Sie Ihre Daten in einem Array der Länge \(n\). Führen Sie als Objektvariable eine Zahl \(s\), mit der Sie sich die Anzahl der Elemente in Ihrem Stack merken. Wenn \(s = n\) erreicht ist, ziehen Sie um in ein doppelt so großes Array. Wenn \(s = n/4\) erreicht ist, ziehen Sie um in ein halb so großes Array.

Stack mit Hilfe von verketteten Listen

Übungsaufgabe Wiederholen Sie die vorherige Übungsaufgabe, allerdings nun mit einer verketteten Liste. Sie brauchen also eine Klasse Node mit zwei Variablen: 
public class Node {
Node next;
String content;
}

Warteschlangen (Queues)

Eine Warteschlange unterstützt die selben Funktionen push x und pop wie ein Stack, allerdings verhalten die sich anders. Ein push x fügt x am Ende der Schlange ein, und pop entfernt das erste/vorderste Element und gibt es zurück.

Queues mit einem Array und zwei Pointern

Eine Queue können wir ganz simpel als zyklisches Array implementieren. Unsere Datenstruktur besteht aus einem Array der Größe \(n\) und zwei Zeigern start und end, die die Werte \(0,\dots,n-1\) annehmen können. Der Wert start zeigt auf den Anfang der Warteschlange (also ganz vorne), und end-1 ist das letzte Element. Am Anfang gilt start = end. Das Array ist als Wrap-Around-Array gedacht, Ihre Warteschlange kann also folgende Form haben:

Die Operation pop würde nun start auf 7 erhöhen und den Buchstaben m zurückgeben; push e würde in Zelle 1 den Buchstaben e schreiben und end auf 2 erhöhen. Die Größe der Queue, also die Anzahl der belegten Zellen, errechnen wir mittels \(s = {\rm end} - {\rm start}\), falls diese nicht negativ ist, und \(s = {\rm end} - {\rm strat} + n\), falls \(s < 0\) gilt. Im obigen Beispiel also \(1 - 6 + 11 = 6\). Wenn \(s = n-1\) erreicht worden ist, ziehen wir in ein Array der Größe \(2n\) um; falls \(s\) auf \(n/4\) gefallen ist, ziehen wir in ein Array der Größe \(n/2\) um, wie beim Stack.

Übungsaufgabe Implementieren Sie eine Queue als Wrap-Around-Array in Java.

Queues als doppelt verkettete Listen

Alternativ zur Array-Lösung können wir Queues auch mit doppelt verketteten Listen realisieren. Da bei der pop-Operation das älteste Element entfernt wird, muss dieses "wissen", welches Element nach ihm eingefügt wurde. Wir brauchen also auch Pointer von "alt" nach "neu".
Übungsaufgabe Implementieren Sie eine doppelt verkettete Liste in Java. Sie brauchen ein Objekt DoublyLinkedNode mit drei inneren Variablen: 
public class DoubleLinkedNode {
String content; 
DoublyLinkedNode before;
DoublyLinkedNode behind;
}

Nehmen Sie meine Datei QueueDLL.java als Vorlage. Zur Erinnerung können Sie sich meine Implementierung einer (einfach) verketteten Liste anschauen: LinkedList.java

Erinnern Sie sich an Elm. Dort hatten wir ja einen Datentyp 

type LinkedList = 
EmptyNode 
LinkNode String LinkedList
so dass wir mit Hilfe des Datenkonstruktors LinkNode Werte verknüpfen konnten, also zum Beispiel 
LinkNode "M" (LinkNode "o" (LinkNode "n" (LinkNode "t" (LinkNode "a" (LinkNode "g" EmptyNode)))))
Nur, dass es in Elm diesen Datentyp bereits gibt: List a mit dem Syntaxzucker, dass wir statt Datenkonstruktor LinkNode den Konstruktor :: mit Infixschreibweise verwenden dürfen, also 
"M" :: ("o" :: ("n" :: ("t" :: ("a" :: ("g" :: [])))))
beziehungsweise in noch kompakterer Schreibweise 
["M", "o", "n", "t", "a", "g"]
Aber lassen Sie sich nicht täuschen: trotz der Schreibweise mit [...] handelt es sich hier um eine verkettete Liste, deren Zellen verstreut im Speicher liegen, und nicht um ein Array mit random access; eine Funktion getLastElement: List a -< Maybe a hätte somit unvermeidlich Laufzeit \(O(n)\), weil es die ganze Liste durchlaufen müsste, und eben nicht \(O(1)\) wie bei einem Array.

Übungsaufgabe Überlegen Sie sich, wie Sie in Elm einen Datentyp Queue implementieren können, der push x und pop in konstanter amortisierter Zeit unterstützt; dass heißt, die Laufzeit einer einzelnen pop-Operation hängt unter Umständen von der Länge der Queue ab, eine Folge von \(k\) vielen Operationen braucht aber in jedem Fall höchstens \(O(k)\) Zeit.

Weitere Beispiele: Listen mit Reinschieben

Stellen Sie sich vor, wir wollen unsere aufgereihten Daten durchgehen können und ohne großen Aufwand der derzeitigen Stelle \(i\) ein neues Element "reinschieben" können, also

Wenn Sie das Prinzip der doppelt verketteten Liste verstanden haben, sollte es für Sie kein großes Problem sein, das in Java zu implementieren. Wie schaut es mit rein funktionalen Sprachen wie Elm aus?

Übungsaufgabe Implementieren Sie in Elm einen Datentyp, der die Operationen moveLeft, moveRight, currentElement, writeHere und insertRight unterstützt. Die Laufzeit sollte \(O(1)\) amortisiert sein, d.h., einzelne Operationen dürfen große Laufzeit haben, eine Folge von \(n\) Operationen muss aber in \(O(n)\) über die Bühne gehen.
Übungsaufgabe Wiederholen Sie die vorherige Übung, allerdings sollte es sich nun um eine zyklische Liste handeln, d.h., wenn Sie immer nach rechts laufen, kommen Sie am Ende wieder ganz links am Anfang an.
Ihr Datentyp sollte die gleichen Operationen unterstützen wie der vorige (also moveLeft, moveRight, insertRight etc.)