Abstrakter Datentyp: ADT einfach erklärt

Ein abstrakter Datentyp, kurz ADT, fasst Daten mit der Menge aller zulässigen Operationen zusammen, über die man auf diese Daten zugreift. Der Zugriff läuft also nur über diese Operationen. Deshalb sind die Daten nach außen gekapselt.

Ein ADT beschreibt, was die Operationen tun. Wie sie es tun, lässt er offen. Die Umsetzung im Speicher heißt Implementierung. Wer den ADT benutzt, muss die innere Umsetzung nicht kennen, denn der ADT verwaltet seine Daten im Speicher selbst.

Dazu gehören angestrebte Eigenschaften. Bei der Kapselung kann der Anwender in die interne Struktur der Daten nicht eingreifen. Dadurch ist die Gefahr, Daten ungewollt zu löschen oder zu verändern, deutlich herabgesetzt. Bei der Modularität können viele Verbesserungen nachträglich über den ADT übernommen werden, ohne dass sich die Programme ändern, die ihn benutzen.

Die Signatur ist die formale Schnittstelle einer Operation. Sie besteht aus dem Namen und den Parametern (Anzahl, Art und Reihenfolge). Bei stark typisierten Programmiersprachen, in denen jeder Wert einen festen Typ hat, gehört auch der Typ des Ergebnisses dazu. Auch die Menge aller Operationen eines ADT nennt man Signatur.

Die Semantik legt die Bedeutung und das Zusammenspiel der Operationen fest. Eine Spezifikation eines ADT besteht aus beidem: aus einer Signatur und einer Semantik.

Eine Signatur allein ist rein syntaktisch. Das heißt: Sie beschreibt nur die äußere Form, nicht die Bedeutung. Sie nennt Namen, die Stelligkeit (wie viele Eingaben eine Operation hat) und das Ergebnis. Ob ein Zeichen wie + wirklich addiert, steht erst in der Semantik.

Das zeigt der Vergleich von Stapelspeicher (Stack) und Warteschlange (Queue). Ihre Signaturen sind gleich aufgebaut: push und enqueue nehmen beide ein Element und die Struktur und liefern die Struktur zurück. Unterschiede ergeben sich erst mit der Semantik: Der Stack arbeitet nach dem Prinzip Last in, first out, die Queue nach First in, first out.

Ein Stack (Stapelspeicher) arbeitet nach dem Prinzip Last in, first out, kurz LIFO. Stell dir einen Stapel Umzugskisten vor: Du legst eine neue Kiste oben drauf und nimmst auch nur oben eine weg. Der Zugriff ist im Regelfall nur auf das oberste Element möglich.

Die Signatur des Stacks hat fünf Operationen. emptyStack erzeugt einen leeren Stack. isStackEmpty fragt, ob der Stack leer ist. push packt ein Element oben auf den Stack. pop entfernt das oberste Element und gibt den neuen Stack zurück. top gibt das oberste Element zurück, ohne es zu entfernen. Eine andere Beschreibung des Stapelspeichers lässt pop das oberste Objekt liefern und entfernen; die Operation zum bloßen Ansehen heißt dort peek (zuweilen auch top).

Die Semantik besteht aus Regeln. Dabei steht x für ein Element und s für einen Stack. Der Sonderfall ist der leere Stack: Auf ihm ergeben pop und top den Wert ERROR, also einen Fehler. Auch eine Java-Beschreibung des Stacks (ein Interface, das nur Signaturen festlegt und die Semantik in Kommentaren nennt) verlangt für pop und top als Voraussetzung: Der Stack ist nicht leer.

Ein Stack kann auf verschiedene Weisen implementiert werden. Zwei Möglichkeiten bieten dieselbe Schnittstelle an, zum Beispiel stack_empty, stack_push und stack_pop. Von außen sehen sie gleich aus. Innen sind sie verschieden gebaut.

Liste: Jedes Element liegt in einem eigenen Knoten. Der Knoten speichert einen Zeiger (einen Verweis) auf die Daten und einen Zeiger next auf den nächsten Knoten. Der Stack merkt sich nur den obersten Knoten (top). Bei push entsteht ein neuer Knoten, sein next zeigt auf das bisherige top, und er wird das neue top. Bei pop wird top auf das next des obersten Knotens gesetzt. Die Größe stimmt stets mit der Anzahl der Elemente überein. Dafür ist der Speicherverbrauch hoch, weil für jedes Element zusätzlich ein Zeiger auf das nächste gespeichert wird. Auch ist das Einfügen und Auslesen nicht in konstanter Zeit möglich, da dabei stets Speicheroperationen ausgeführt werden.

Feld: Der Stack besitzt ein Feld (bottom) und die Zahlen len und size. Aus dem Code folgt: len ist die Anzahl der abgelegten Elemente, denn stack_empty prüft, ob len gleich 0 ist. size ist die Größe des Feldes. Bei push kommt das Element an die Stelle len, danach wird len um 1 größer. Ist len gleich size, ist das Feld voll und wird vor dem Ablegen vergrößert. Gibt es dafür keinen Speicher mehr, meldet push einen Fehler (ERR_NOMEM). Der Speicherverbrauch pro Element ist geringer, weil kein Zeiger auf das nachfolgende Element nötig ist. Der Zugriff auf die Elemente ist in konstanter Zeit möglich, solange keine Speicheroperationen durchgeführt werden müssen.