Datentypen
Abstrakter Datentyp
In der Informatik spielt die Verwendung von Datenstrukturen eine wichtige Rolle. Eine Datenstruktur ist eine spezielle Art von Datentyp, der es ermöglicht, Daten auf bestimmte Weise zu organisieren und zu verwalten. Abstrakte Datentypen (ADT) sind eine spezielle Form von Datenstrukturen, die sich durch ihre abstrakte und universelle Natur auszeichnen.
abstrakter Datentyp (ADT): Beschreibung von Datenstrukturen unabhängig von ihrer späteren Implementierung in einer konkreten Programmiersprache
- Konkrete Datentypen werden aus Basisdatentypen bzw. Java-Klassen konstruiert und sind somit direkt in einer Implementierung einsetzbar.
- Abstrakte Datentypen bilden nur eine Spezifikation der Schnittstelle nach außen, indem sie Operationen und ihre Funktionalität festlegen. Sie sind nicht direkt in ein Programm einbindbar.
Ein abstrakter Datentyp (ADT) ist eine spezielle Art von Datenstruktur, die nur über die Methoden und Operationen definiert wird, die auf ihr ausgeführt werden können, ohne ihre tatsächliche Implementierung zu offenbaren. Es ist eine abstrakte Vorstellung davon, wie Daten gespeichert und verarbeitet werden, ohne die tatsächlichen Details der Implementierung zu kennen.
Ein Beispiel für einen ADT ist eine Warteschlange (Queue). Eine Warteschlange ist eine Datenstruktur, bei der das erste Element, das hinzugefügt wurde, auch als erstes entfernt wird (First-In-First-Out, FIFO). Der ADT Warteschlange definiert die Methoden wie hinzufügen und entfernen von Elementen sowie Abfragen von Größe, aber nicht die tatsächliche Implementierung. Es kann implementiert werden, indem man ein Array oder eine Liste verwendet.
Liste
Eine Liste ist eine abstrakte Datenstruktur, die eine Folge von Elementen speichert, wobei die Reihenfolge der Elemente signifikant ist. Listen ermöglichen es, Elemente einfach hinzuzufügen, zu entfernen oder nach bestimmten Kriterien zu sortieren. Darüber hinaus können Listen in andere Datenstrukturen, wie z. B. Stacks oder Queues, umgewandelt werden.
Liste
- Lineare Folge von Datenelementen
- Reihenfolge der Elemente wird erhalten
- Elemente können
- hinzugefügt werden
- entfernt werden
- gesucht werden
- Grundlage für andere Datenstrukturen
Typische Operationen auf einer Liste
append: Fügt ein Element am Ende hinzuinsert: Fügt ein Element am einer bestimmten Stelle hinzuremove: Entfernt ein Elementindex: Gibt den Index eines Elements zurücksize: Zählt die Anzahl eines Elements in der Listeclear: Entfernt alle Elemente aus der Liste
Stack
Ein Stack (Stapel oder Kellerspeicher) ist eine spezielle Art von Datenstruktur, die nach dem Last-In-First-Out (LIFO) Prinzip arbeitet. Das bedeutet, dass das letzte hinzugefügte Element als erstes entfernt wird.
Stack auch Kellerspeicher oder Stapel
- Last-In-First-Out (LIFO)
- Grundlage für viele Algorithmen
- Methodenaufruf in Programmiersprachen basiert auf Stack
Typische Operationen auf einem Stack
push: fügt ein Element auf den Stack hinzupop: entfernt das oberste Element vom Stack und gibt es zurückpeek: gibt das oberste Element des Stacks zurück, ohne es zu entfernenisEmpty: gibt an, ob der Stack leer ist oder nicht
Ein konkretes Beispiel für die Verwendung eines Stacks ist das Auswerten von Ausdrücken in der Umgekehrten Polnischen Notation (RPN). In diesem Fall werden die Operanden (z. B. 2, 3) auf den Stack gelegt und die Operatoren (z. B. +, *) werden auf die Operanden angewendet, die sich auf dem Stack befinden.
Ein Stack kann auch verwendet werden, um Funktionsaufrufe zu implementieren (Call Stack), und es ist auch Teil einiger Algorithmen wie Tiefensuche und Backtracking.
Queue
Ein Queue (Warteschlange) ist ein abstrakter Datentyp, der nach dem First-In-First-Out (FIFO) Prinzip arbeitet. Das bedeutet, dass das erste hinzugefügte Element als erstes entfernt wird. Eine Queue besteht aus einer Liste von Elementen, die einen bestimmten Zugriff auf die Elemente ermöglicht.
Eine Queue hat typischerweise die folgenden Methoden:
enqueue: fügt ein Element an das Ende der Queue hinzu.dequeue: entfernt das erste Element in der Queue und gibt es zurück.peek: gibt das erste Element in der Queue zurück, ohne es zu entfernen.isEmpty: gibt an, ob die Queue leer ist oder nicht.
Ein konkretes Beispiel für die Verwendung einer Queue ist ein Drucksystem, in dem die Druckaufträge in der Reihenfolge ihres Eingangs verarbeitet werden. Ein weiteres Beispiel ist die Simulation von Warteschlangen in einem Computersystem, in dem Aufgaben in der Reihenfolge ihres Eingangs verarbeitet werden.
Queues können auf viele Arten implementiert werden, wie z. B. mit Arrays, Listen oder verketteten Listen. Es gibt auch spezielle Arten von Queues wie z. B. die Priority Queue, bei der die Elemente nach einem bestimmten Prioritätskriterium sortiert sind und die Dequeue-Operation das Element mit der höchsten Priorität entfernt.
Ringpuffer
Ein Ringpuffer (auch bekannt als „circular buffer“ oder „circular queue“) ist eine spezielle Art von Datenstruktur, die auf einem Array basiert und die Eigenschaft besitzt, dass sie sich selbst überschreibt, wenn sie voll ist. Ein Ringpuffer hat eine feste Größe und ermöglicht es, Elemente hinzuzufügen und zu entfernen, ohne dass die Größe dynamisch verändert werden muss.
Ein Ringpuffer hat typischerweise die folgenden Methoden:
put: fügt ein Element am Ende des Ringpuffers hinzu. Wenn der Ringpuffer voll ist, wird das älteste Element überschriebenget: entfernt das älteste Element aus dem Ringpuffer und gibt es zurückpeek: gibt das älteste Element des Ringpuffers zurück, ohne es zu entfernenisFull: gibt an, ob der Ringpuffer voll ist oder nichtisEmpty: gibt an, ob der Ringpuffer leer ist oder nicht
Ein Anwendungsbeispiel für einen Ringpuffer ist die Aufzeichnung von Ereignissen in einer begrenzten Historie. Ein anderes Beispiel ist die Verarbeitung von Datenströmen, bei denen ältere Daten überschrieben werden, wenn kein Speicherplatz mehr verfügbar ist.