Im Gegensatz zu Datentypen und Datenstrukturen, die eher physikalisch definiert werden, gibt man bei einem Abstrakten Datentyp nur die Operationen an, die mit ihm ausgeführt werden können sollen. In der Fachliteratur bezeichnet man die Menge der Operationen, die ein ADT ausführen kann, als Semantik des ADT.
Hier ein bekanntes Beispiel, der ADT Stack:
Der ADT Stack
Der Abstrakte Datentyp Stack wird durch folgende Operationen bzw. Semantik definiert:
- Init(): Erzeugt einen leeren Stack.
- Push(x): Das Element x wird hinzugefügt.
- Pop(): Das zuletzt hinzugefügte Element wird entfernt. Ein Wert wird von Pop() nicht zurückgeliefert.
- Top(): Der Wert des zuletzt hinzugefügten Elementes wird zurückgeliefert. Dieses Element wird aber nicht entfernt!
- Empty(): Falls der Stack leer ist, wird TRUE zurückgeliefert, sonst FALSE.
Über eine mögliche Implementierung sagt diese Definition nichts aus. Der ADT "Stack" könnte zum Beispiel mit Hilfe der Datenstruktur "Array" implementiert werden, oder aber auch mit Hilfe der Datenstruktur "Einfach verkettete dynamischen Liste".
Weitere bekannte Abstrakte Datentypen sind "Queue", "Priority Queue", "Dictionary", "List" und "binärer Suchbaum".
Spezifizierung eines ADT
Man kann einen ADT wie im obigen Beispiel durch die verbale Beschreibung der Operationen definieren bzw. spezifizieren. Eine andere, eher mathematisch-logisch orientierte Möglichkeit der Spezifizierung ist die Definitin durch Axiome.
Axiomatische Definition des ADT Stack
Autor: Jörg NIEVERGELT (1986)
Eine Erläuterung dieser Axiome finden Sie auf der Seite "Die axiomatische Sichtweise" auf dieser Homepage. Weitere Möglichkeiten der Spezifizierung finden Sie auf der Wikipedia-Seite "Abstrakter Datentyp".