Arrays, Listen, Stacks und Queues
Autor: Pascal LenznerFür viele Algorithmen benötigen wir grundlegende Datenstrukturen, welche in dieser Unit eingeführt werden sollen.
Wir konzentrieren uns hierbei auf Arrays, Listen, Stacks und Queues.
Arrays
Arrays, bzw. Felder, gehören zu den einfachsten Datenstrukturen und sind in so gut wie jeder Programmiersprache vorhanden. Arrays haben standardmäßig eine bei Erzeugung des Arrays festgelegte Größe, die später nicht mehr geändert werden kann. (Es gibt auch dynamische Arrays, die eine dynamische Anpassung der Größe zulassen, doch an dieser Stelle genügen uns vorerst statische Arrays.) Prinzipiell ist ein Array nur ein fest reservierter Speicherbereich, auf den beliebig zugegriffen werden kann. Ein Array besteht aus endlich vielen Speicherzellen, die jeweils einen Index haben und über diesen Index direkt adressierbar sind.
Bei eindimensionalen Arrays der Länge \(n\) gibt es \(n\) Speicherzellen mit den Indices \(1\) bis \(n\) (bzw. \(0\) bis \(n-1\), falls wir bei \(0\) anfangen zu zählen). Angenommen solch ein Array hieße \(A\), dann bezeichnete \(A[i]\) den Inhalt der \(i\)-ten Speicherzelle. Gilt \(A[i] = 17\), dann wird in der \(i\)-ten Zelle von \(A\) die Zahl \(17\) gespeichert. Wir nehmen an, dass wir auf jede Zelle des Arrays in konstanter Zeit zugreifen können. D. h., jeder Arrayzugriff kostet \(\Theta(1)\). Bei mehrdimensionalen Arrays werden die Speicherzellen über mehrere Dimensionen adressiert. Zum Beispiel ist ein zweidimensionalen Array \(A\) der Größe \(n\times m\) einfach wie eine Tabelle mit \(n\) Zeilen und \(m\) Spalten zu verstehen, wobei dann \(A[i][j]\) den Inhalt der Speicherzelle in der \(i\)-ten Zeile und der \(j\)-ten Spalte beschreibt. Auch bei mehrdimensionalen Arrays nehmen wir an, dass ein Zugriff \(\Theta(1)\) kostet.
Weiterhin nehmen wir an, dass ein Array mit Kosten \(\Theta(1)\) angelegt werden kann, wobei dann aber noch die einzelnen Zellen mit je einem Zugriff initialisiert werden müssen, damit dort der richtige Startwert steht. Somit kostet das Anlegen und Initialisieren eines Arrays mit \(k\) Zellen \(\Theta(k)\). Für ein \(3\)-dimensionales Array mit je \(n\) Einträgen pro Dimension wären das dann Kosten von \(\Theta(n^3)\), da es \(n\cdot n \cdot n = n^3\) Zellen gibt.
Vorteil eines Arrays ist somit die schnelle Zugriffszeit auf beliebige Positionen. Doch es gibt auch gravierende Nachteile: Will man beispielsweise ein Element an irgendeiner Stelle einfügen, so müssen alle Elemente in den folgenden Zellen verschoben werden. Im schlimmsten Fall kann dies zu \(\Theta(n)\) Verschiebungen führen. Falls durch das Einfügen das Array überlaufen würde, dann muss sogar ein neues Array angelegt und alle Elemente in das neue Array kopiert werden, was auch wieder Kosten von \(\Theta(n)\) verursacht. Prinzipiell gilt, dass Arrays dann eine gute Wahl sind, wenn von vornherein die Anzahl der Elemente bekannt und ein schneller Direktzugriff auf jede Position wünschenswert ist.
Listen
Im Unterschied zu (statischen) Arrays muss bei Listen nicht von vornherein die Anzahl der zu speichernden Elemente bekannt sein und wir können auch leicht neue Elemente einfügen.
Eine Liste ist vom Prinzip her einfach eine Verkettung von Objekten. Jedes dieser Objekte enthält ein zu speicherndes Datum und einen Zeiger auf sein Nachfolgeobjekt (und evtl. auch auf das Vorgängerobjekt). Außerdem gibt es einen Zeiger head, welcher auf das Startobjekt verweist. Das Ende der Liste ist damit markiert, dass ein Listenobjekt keinen Nachfolger (d. h. einen Null-Zeiger) hat. Hat jedes Objekt nur einen Zeiger auf den Nachfolger, dann nennt man dies einfach verkettete Liste.
Sind jeweils Zeiger auf den Vorgänger und den Nachfolger vorhanden (wobei das erste Objekt dann einen Null-Zeiger auf den Vorgänger hat), dann haben wir eine doppelt verkettete Liste vorliegen.
Wir werden im weiteren Verlauf immer annehmen, dass wir doppelt verkettete Listen vorliegen haben. Betrachten wir nun die Kosten für das Modifizieren einer solchen Liste.
Wollen wir ein neues Objekt in die Liste einfügen, so müssen wir nur die Zeiger der Nachbarn (bzw. den head-Zeiger) anpassen. Dazu sind nur konstant viele Zeigeränderungen nötig. Allerdings müssen wir evtl. noch die entsprechende Einfügestelle in der Liste suchen. Soll am Anfang eingefügt werden, so haben wir die richtige Stelle direkt mit Hilfe des head-Zeigers und somit kostet das Einfügen an den Listenanfang \(\Theta(1)\). Wollen wir an Position \(i\) einfügen, so müssen wir zunächst bis zu dieser Position durch die Liste gehen und dann dort die Zeiger der Nachbarn anpassen. Somit haben wir dafür Kosten von \(\Theta(i)\), d. h. im schlimmsten Fall \(\Theta(n)\), für Listen mit \(n\) Elementen (Objekten). Dasselbe gilt für das Entfernen von Elementen. Hier sehen wir den entscheidenden Nachteil von Listen gegenüber Arrays: Wir können nicht mehr direkt auf die einzelnen Elemente zugreifen, sondern wir müssen uns immer sequentiell bis zu diesen durchhangeln.
Wir können doppelt verkettete Listen auch leicht abändern, so dass wir sehr schnell ein Element vorn und hinten einfügen bzw. entfernen können. Dazu führen wir einfach einen weiteren Zeiger tail ein, der auf das letzte Element der Liste zeigt (und angepasst wird, wenn sich am Listenende etwas ändert). Allerdings hilft uns dies im schlimmsten Fall nichts. Denn auch mit dem tail-Zeiger haben wir Kosten von \(\Theta(n)\), falls wir ein Element in die Mitte der Liste einfügen bzw. löschen wollen.
Das Anlegen einer leeren Liste kostet \(\Theta(1)\), da nur der head-Zeiger auf Null gesetzt werden muss. Weitere Elemente können dann eingefügt werden. D. h., das Anlegen einer Liste mit \(i\) Elementen besteht aus dem Anlegen einer leeren Liste und dem \(i\)-maligen Einfügen der Elemente, jeweils an das Listenende. Somit kostet dies \(\Theta(i)\).
Mithilfe von doppelt verketteten Listen können wir nun leicht andere sogenannte abstrakte Datentypen realisieren, nämlich Stacks (Stapelspeicher) und Queues (Warteschlangen).
Stacks
Ein Stack ist ein LIFO-Speicher, d. h. ein Last-in-first-out-Speicher, manchmal auch Kellerspeicher genannt. Es kann nur auf ein Element zugegriffen werden und dieses ist immer das zuletzt eingefügte Element. Man kann sich einen Stack wie einen Stapel vorstellen, nur das oberste Element kann betrachtet bzw. entfernt werden und neue Elemente können nur auf das jeweils oberste Element gelegt werden. Die zulässigen Operationen eines Stacks sind somit top(), welches den Inhalt des obersten Elements zurückliefert, pop(), welches den Inhalt des obersten Elements zurückliefert und dieses Element vom Stack entfernt, und push(x), welches das Objekt \(x\) als neues oberstes Element auf den Stack legt.
Mithilfe einer doppelt verketteten Liste können wir dies wie folgt umsetzen: Wir einigen uns darauf, dass der Kopf der Liste oben ist. Somit gibt uns head.data den Inhalt des obersten Elements zurück, d. h., es realisiert die Operation top(). Die Operation pop() wird einfach durch top() und Entfernen des ersten Listenelements realisiert und die Operation push(x) wird durch Einfügen des Objekts \(x\) an den Listenanfang umgesetzt. Somit können wir mithilfe von Listen alle Operationen des Stacks mit Kosten von jeweils \(\Theta(1)\) umsetzen.
Queues
Eine Queue ist ein FIFO-Speicher, d. h. ein First-in-first-out-Speicher. Auch hier kann nur auf ein Element zugegriffen werden, nämlich das Element, welches in der Warteschlange ganz vorn steht (d. h. schon am längsten wartet). Neue Elemente können nur am Ende der Warteschlange eingefügt werden. Bei Queues gibt es auch die Operationen top(),pop() und push(x), wobei diese nun folgende Bedeutung haben: top() liefert den Inhalt des Elements am Warteschlangenanfang, pop() liefert auch diesen Inhalt und entfernt das Element am Warteschlangenanfang und push(x) fügt das neue Element \(x\) ans Ende der Warteschlange ein.
Mithilfe des oben erwähnten tail-Zeigers können wir alle drei Operationen leicht mit doppelt verketteten Listen umsetzen. top() entspricht head.data,pop() entspricht head.data gefolgt vom Löschen des Anfangselements der Liste und push(x) wird durch Einfügen des Elements \(x\) ans Listenende umgesetzt.
Somit können wir auch für Queues alle Operationen mit Kosten von jeweils \(\Theta(1)\) umsetzen.
Aufgabe
Gegeben sind zwei Stacks \(S_1\) und \(S_2\). Wie kann nur mit Hilfe der beiden Stacks eine Queue implementiert werden?
Lösung
