Datenstrukturen Queue, Stack, Heap, Array, Baum, Graph – BFS, DFS, Komplexität

Dieser Beitrag ist eine Begriffserklärung zu wichtigen Datenstrukturen – inklusive Prüfungsfragen und Tags.

In a Nutshell

Die Kern Datenstrukturen Array, Stack, Queue, Heap, Baum und Graph bilden die Grundlage effizienter Algorithmen. Sie unterscheiden sich in Zugriffs, Speicher und Laufzeitverhalten und werden je nach Problem, Reihenfolge, Prioritäten, Hierarchien, Netze, gezielt eingesetzt.

Kompakte Fachbeschreibung

Arrays speichern Elemente im zusammenhängenden Speicher, bieten O(1) Zugriff per Index und sind Basis vieler höherer Strukturen. Stack arbeitet nach LIFO, push und pop sind O(1) und eignen sich für Rückverfolgung, Aufrufstapel, Parser. Queue folgt FIFO, enqueue und dequeue sind O(1), nützlich für BFS oder Puffer. Heap bezeichnet hier die prioritätsbasierte Priority Queue mit Heap Eigenschaft, insert, extract min, max sind O(log n), peek O(1). Bäume strukturieren hierarchische Daten, in balancierten Varianten sind Suche, Einfügen und Löschen O(log n). Graphen modellieren Knoten und Kanten, Repräsentation über Adjazenzliste oder Adjazenzmatrix je nach Dichte.

Prüfungsrelevante Stichpunkte

• Komplexitäten kennen, Array Index Zugriff O(1), Stack push pop O(1), Queue enqueue dequeue O(1), Heap insert extract O(log n), balancierter Suchbaum Operationen O(log n)
• Reihenfolgen, LIFO beim Stack, FIFO bei Queue, Priorität beim Heap
• Traversierungen, BFS mit Queue, DFS mit Stack, rekursiv oder iterativ
• IHK relevant, Repräsentation von Graphen, Adjazenzliste vs Adjazenzmatrix, dichte vs dünne Graphen
• Praxisbezug, Scheduling mit Priority Queue, Undo Stack, Messaging Queue, Router Pfadsuche
• Sicherheitsaspekt, Bounds Checks bei Arrays, leere Pop Dequeue verhindern, Prioritätenvalidierung
• Wirtschaftlichkeit, richtige Struktur reduziert Laufzeit und Speicher
• Dokumentationspflicht, Datenstrukturwahl, Invarianten, Komplexitätsverträge

Kernkomponenten

1. Array, Kapazität, Indexzugriff, Kontiguität
2. Stack, push, pop, top, LIFO Invariante
3. Queue, enqueue, dequeue, front, rear, FIFO Invariante
4. Priority Queue, Heap Eigenschaft, min, max Heap
5. Baumknoten, Eltern, Kinder, Höhe, Tiefe
6. Balancierung, AVL, Rot Schwarz, B Baum für Speicher Seiten
7. Graphknoten, Kanten, Grad, Gewicht, Richtung
8. Repräsentation, Adjazenzliste, Adjazenzmatrix
9. Traversierung, BFS, DFS, Inorder, Preorder, Postorder
10. Invarianten und Tests, Heap Ordnung, Suchbaum Ordnung, Zyklusfreiheit bei Bäumen

Praxisbeispiel

// 1. BFS über einen Graphen mit Adjazenzliste, nutzt Queue
Queue<Node> q = new LinkedList<>()
Set<Node> seen = new HashSet<>()
q.add(start), seen.add(start)
while (!q.isEmpty()) {
Node u = q.remove()
visit(u)
for (Node v : adj[u]) {
if (!seen.contains(v)) { seen.add(v), q.add(v) }
}
}

// 2. Min Heap Nutzung für Dijkstra Knoten Auswahl
PriorityQueue<State> pq = new PriorityQueue<>(byDistance)
pq.add(source)
while (!pq.isEmpty()) {
State s = pq.remove()
if (s.dist > best[s.node]) continue
relaxEdgesAndPushBetterStates(s, pq)
}

Erklärung: BFS nutzt eine Queue für Schicht-weises Traversieren, Dijkstra wählt mit Priority Queue den günstigsten Knoten.

Vorteile und Nachteile

Array

• Sehr schneller Indexzugriff, kompakt

• Fixe Größe, teure Einfügungen in der Mitte

Stack

• Einfache O(1) Operationen, ideal für Rückverfolgung

• Nur Zugriff auf die Spitze

Queue

• Stabile Reihenfolge, entkoppelt Produzenten Konsumenten

• Kein Direktzugriff

Heap

• Schnelle Prioritätswahl

• Keine geordnete Gesamtiteration, nur Spitze effizient

Baum

• Geordnete Daten mit logarithmischen Operationen

• Balancierungskomplexität

Graph

• Sehr flexibel, modelliert Netze

• Höhere Implementierungs- und Algorithmuskomplexität

Typische Prüfungsfragen (mit Kurzantwort)

1. Adjazenzliste vs. Adjazenzmatrix? Bei dünnen Graphen mit wenigen Kanten, Speicher O(n + m) statt O(n²) und schnellere Iteration über Nachbarn.

2. Reihenfolge Stack und Queue? Stack LIFO (zuletzt hinein, zuerst heraus), Queue FIFO (zuerst hinein, zuerst heraus).

3. Heap Eigenschaft? Bei einem Min Heap ist jeder Knoten kleiner gleich seinen Kindern, die kleinste Priorität liegt an der Wurzel.

4. Komplexität Einfügen/Löschen Min Heap? O(log n) durch sift up und sift down, peek ist O(1).

5. Balancierte Suchbäume O(log n)? Die Höhe bleibt proportional zu log n, dadurch sind Pfadlängen für Suche, Insert, Delete logarithmisch.

6. BFS funktioniert und wofür? Ebene für Ebene über Queue, liefert kürzeste Wege in ungewichteten Graphen und eignet sich für Erreichbarkeitsanalysen.

7. Baum im Speicher repräsentieren? Verlinkte Knoten mit Referenzen auf Kinder, oder implizit im Array bei Heaps, Indexierung über 2i, 2i+1.

8. Priority Queue vs. sortierte Liste? insert und extract sind O(log n) statt O(n), peek bleibt O(1).

9. Risiken bei Array Zugriff? Out of Bounds, Off by One Fehler, fehlende Bounds Checks, potenzielle Sicherheitslücke.

10. DFS besserer Traversierungsansatz? Bei Topologischer Sortierung, Zyklenerkennung, Komponentenfindung, und wenn tiefe Pfade gezielt erkundet werden sollen.

Wichtigste Quellen

1. https://de.wikipedia.org/wiki/Datenstruktur
2. https://en.cppreference.com/w/cpp/container
3. https://docs.oracle.com/javase/tutorial/collections/