Lineare Datenstrukturen: Schlange, Stapel und Liste

Diese Seite bietet einen umfassenden Überblick über drei grundlegende lineare Datenstrukturen: Schlange (Queue), Stapel (Stack) und Liste (List). Jede dieser Strukturen wird detailliert mit ihren Funktionen, verfügbaren Methoden und Anwendungsbeispielen erläutert.

Schlange (Queue)

Die Schlange, auch als Queue bekannt, ist eine lineare Datenstruktur, die nach dem First-In-First-Out (FIFO) Prinzip arbeitet. Wie funktioniert die Queue? Sie ermöglicht das Hinzufügen von Objekten am Ende der Schlange und das Entfernen vom Anfang.

Definition: Eine Queue ist eine Datenstruktur, bei der das zuerst eingefügte Element auch als erstes wieder entfernt wird (FIFO-Prinzip).

Verfügbare Methoden der Queue-Klasse umfassen:

• enqueue(): Fügt ein Objekt am Ende der Schlange ein.
• dequeue(): Entfernt das vorderste Objekt aus der Schlange.
• isEmpty(): Prüft, ob die Schlange leer ist.

Beispiel: In einer Warteschlange wird das erste Element (front) entfernt, während neue Elemente am Ende (tail) hinzugefügt werden.

Highlight: Queues sind besonders nützlich in Szenarien, wo die Reihenfolge der Verarbeitung wichtig ist, wie bei Druckaufträgen oder in der Prozessverwaltung von Betriebssystemen.

Stapel (Stack)

Der Stapel, oder Stack, folgt dem Last-In-First-Out (LIFO) Prinzip. Wie funktioniert der Stack? Hier wird das zuletzt hinzugefügte Element als erstes wieder entfernt.

Definition: Ein Stack ist eine Datenstruktur, bei der das zuletzt eingefügte Element als erstes wieder entfernt wird (LIFO-Prinzip).

Die Stack-Klasse bietet folgende Methoden:

• push(): Legt ein Element oben auf den Stapel.
• pop(): Entfernt das oberste Element vom Stapel.
• top(): Ermöglicht den Zugriff auf das oberste Element, ohne es zu entfernen.
• isEmpty(): Prüft, ob der Stapel leer ist.

Beispiel: Stellen Sie sich einen Stapel Teller vor. Sie legen neue Teller oben drauf und nehmen sie auch von oben wieder herunter.

Highlight: Stacks sind besonders nützlich für die Implementierung von Undo-Funktionen oder bei der Auswertung von mathematischen Ausdrücken.

Liste (List)

Die Liste ist die flexibelste der drei vorgestellten linearen Datenstrukturen. Was ist der Unterschied zwischen Array und Liste? Im Gegensatz zu Arrays erlauben Listen das Einfügen und Löschen von Elementen an beliebigen Positionen.

Definition: Eine Liste ist eine Datenstruktur, die eine beliebige Anzahl von Objekten verwalten kann und Operationen an jeder Position ermöglicht.

Die List-Klasse bietet eine Vielzahl von Methoden, darunter:

• isEmpty(): Prüft, ob die Liste leer ist.
• toFirst() und toLast(): Setzt den Zeiger auf das erste bzw. letzte Element.
• next(): Bewegt den Zeiger zum nächsten Element.
• remove(): Löscht das aktuelle Element.
• insert() und append(): Fügt ein neues Element ein bzw. an.

Beispiel: Eine Vokabelliste, in der jedes Element (ListNode) ein Vokabel-Objekt enthält und auf das nächste Element verweist.

Highlight: Listen sind besonders vorteilhaft, wenn häufige Einfüge- und Löschoperationen an beliebigen Positionen erforderlich sind.

Vocabulary:

• ListNode: Ein Knoten in einer verketteten Liste, der Daten und einen Verweis auf den nächsten Knoten enthält.
• Current: Der aktuelle Zeiger in einer Liste, der auf das gerade betrachtete Element verweist.

Diese linearen Datenstrukturen bilden die Grundlage für viele komplexere Algorithmen und Datenverarbeitungsprozesse in der Informatik. Welche drei grundlegenden Datenstrukturen gibt es? Queue, Stack und List sind die Antwort auf diese Frage und bieten jeweils einzigartige Vorteile für verschiedene Anwendungsfälle.