Kapitel 5: Stacks und Queues

abstrakte Datentypen (engl: abstract data type) abgekürzt ADT, ist eine Datenstruktur, die auf eine bestimmte Art und Weise organisiert ist, aber die Implementierungsdetails vor dem Benutzer verbirgt. Stattdessen definiert der ADT nur die Operationen, die auf dieser Datenstruktur ausgeführt werden können und gibt möglicherweise auch Einschränkungen für den Datentyp an

In einem Stack kann man Objekte speichern. Dabei kann es sich um Zahlen, Zeichenketten, Speicheradressen, ganze Funktionen, oder andere Datenstrukturen handeln. Sie werden in einer Vielzahl von Anwendugnen verwendet.

Queues sind in Szenarien nützlich, in denen es einige begrenzte Ressourcen gibt, aber mehrere Objekte die diese Ressource verwenden oder darauf zugreifen möchten. Diese Ressource kann ein Prozessor sein oder ein Dienst, der eine Funktion ausführt, oder es könnte ein Empfänger für eine Nachricht sein.

Die Einführung dieses Konzepts einer Warteliste für eine Ressource hilft uns, asynchrone Systeme zu erstellen, die Verarbeitungsgeschwindigkeit zu erhöhen und außerdem sicherzustellen, dass die Ressource effizient genutzt wird

push kann im HInblick auf abstrakte Datentypen (ADT’s) als Ablegen eines Elements auf dem Stack verstanden werden

pop steht für das Entfernen des obersten Elements vom Stack

DT = Datenstruktur+ Operationen

Datenstrukturen kann man in primitive Datenstrukturen und davon abgeleitete nichtprimitive Datenstrukturen unterteilen.

Eine primitive Datenstruktur ist eine Grundstruktur, die normalerweise in die Programmiersprache eingebaut ist, z.B. eine Ganzzahl (int) oder eine Fließkommazahl (float)

Nichtprimitive Datenstrukturen werden aus primitiven Datenstrukturen aufgebaut, die auf sinvolle Weise miteinander verknüpft sind, z.B. eine verlinkte Liste, ein binärer Suchbaum, ein AVL-Tree, ein Graph usw.

Diese nichtprimitiven Datenstrukturen legen den Schwerpunkt auf die Organisation einer Gruppe von Datenelementen.

Man spricht von einem homogenen Datentyp, wenn alle Datenelemente denselben Typ haben, andernfalls spricht man von einem heterogenen Datentyp

Man spriht von einem heterogenem Datentyp, wenn alle Datenelemente, nicht denselben Typ haben

Listen von Datenelementen können in lineare und nichtlineare Listen eingeteilt werden

• Lineare Listen sind eine Art von Datenstruktur, die homogene Elemente hat

• Die Elemente linearer Listen haben eine Reihenfolge und bilden eine Linienreihe

• Lineare Listen sind sehr einfach zu implementieren, da auch der Speicher des Computers linear organisiert ist

• Einige häufige verwendete Listen sind Stacks, Queues und verlinkte Listen

Stacks, Queues und verlinkte Listen sind Beispiele für häufig verwendete linare Listen

Eine nichtlineare Liste ist eine Datenstruktur, in der ein Datenelement mit mehreren anderen Datenelementen verbunden ist

• Eine nichtlineare Liste ist eine datenstruktur, in der ein Datenelement mit mehreren anderen Datenelementen verbunden ist

• Eine nichtlineare Liste kann (muss aber nicht) eine hierachische Beziehung oder eine Eltern-Kind-Beziehung aufweisen

• Die Datenelemente sind nicht in einer sequenziellen Struktur angeordnet

• Die verschiedenen nichtliniearen Listen sind Trees (Bäume und Graphen)

Die am häufigsten verwendeten Operationen im Hinblick auf Datenstrukturen lassen sich grob in folgende Typen unterteilen:

• Einfügen

• Traversieren (Durchlaufen)

• Auswahl

• Durchlaufen

• Sortieren

• Zusammenführen

• Zerstören oder Löschen

Ein Stack (deutsch Stapel) ist eine lineare Datenstruktur, bei der das Hinzufügen neuer Elemente und das Entfernen vorhandener Elemente immer am gleichen Ende erfolgt

Auf einen Stapel (engl. stack) werden neue Elemente immer oben abgelegt und es kann immer nur das oberste, zuletzt abgelegte Element vom Stapel weggenommen werden. Ähnlich, wie bei einem Münzstapel, oder einen Papierstapel

Das Hinzufügen eines neuen Elements erfolgt mit dem Operator push, das Entfernen mit dem Operator pop

Stacks folgen dem Prinzip LIFO (Last in, First Out) waas bedeutet, dass das zuletzt hinzugefügte Element das erste ist, das entfernt wird. Man kann sich einen Stack, wie ein Stapel Teller vortellen: Man legt die Teller oben auf den Stapel (push) und wenn man einen Teller braucht, nimmt man den obersten vom Stapel (pop)

Queues folgen dem Prinzip FIFO (First in, First Out), was bedeutet, dass das zuerst hinzugefüge Element das Erste ist, das entfernt wird. Eine queue ist wie eine Warteschlange im Supermarkt. Die erste Person, die sich anstellt (enqueue) ist die erste, die bediengt wird (dequeue)

Queues werden z.B. verwendet , um Aufgaben zu verwalten, die in einer bestimmten Reihenffolge ausgeführt werden müssen. Ein gutes Beispiel dafür ist ein Druckerspoler, der Druckaufträge in der Reihenfolge verwaltet, in der sie eingehen. Ein weiterer Anwendungsfall von queues ist etwa ein Zwischenspeicher (Buffer) zur DAtenübertragung zwischen zwei Geräten