Informatik-Lexikon

Abstrakter Datentyp

Im Gegensatz zu Datentypen undl 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. Hier ein bekanntes Beispiel, der ADT Stack:

Der ADT Stack

Der Abstrakte Datentyp Stack wird durch folgende Operationen 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", "Liste" und "binärer Suchbaum".