Datenstrukturen: Stack, Queue, Heap, Array, Baum, Graph & Algorithmen

Dieser Beitrag ist eine umfassende Übersicht der wichtigsten Datenstrukturen – inklusive Komplexitätsanalyse, praktischer Beispiele und Algorithmen.

In a Nutshell

Datenstrukturen sind Methoden, Daten so zu organisieren und zu speichern, dass sie effizient accessed und modifiziert werden können. Die Wahl der richtigen Struktur ist entscheidend für die Effizienz.

Kompakte Fachbeschreibung

Datenstrukturen sind fundamentale Bausteine der Softwareentwicklung, die die Organisation und Verwaltung von Daten definieren. Jede Struktur hat spezifische Eigenschaften und Einsatzgebiete.

Wichtige Datenstrukturen:

1. Array

• Beschreibung: Festgelegte, zusammenhängende Folge von Elementen gleichen Typs
• Zugriff: Direkt per Index (O(1))
• Nachteile: Feste Größe, Einfügen/Löschen aufwändig (O(n))

2. Stack (LIFO)

• Prinzip: Last-In, First-Out
• Operationen: push() (oben drauflegen), pop() (oben entfernen)
• Verwendung: Methodenaufrufe, Backtracking, Parser

3. Queue (FIFO)

• Prinzip: First-In, First-Out
• Operationen: enqueue() (hinten anfügen), dequeue() (vorne entfernen)
• Verwendung: Druckerwarteschlange, Breadth-First Search

4. Heap

• Beschreibung: Binärbaum mit Heap-Eigenschaft
• Typen: Min-Heap, Max-Heap
• Verwendung: Priority Queues, Heap Sort

5. Baum

• Beschreibung: Hierarchische Datenstruktur
• Typen: Binärbaum, BST, AVL, B-Baum
• Verwendung: Suchalgorithmen, Datenbanken

6. Graph

• Beschreibung: Knoten und Kanten
• Typen: Gerichtet/Ungerichtet, Gewicht/Ungewichtet
• Verwendung: Netzwerke, Routenplanung

Prüfungsrelevante Stichpunkte

• Array: Direkter Zugriff O(1), feste Größe
• Stack: LIFO-Prinzip, push/pop Operationen
• Queue: FIFO-Prinzip, enqueue/dequeue Operationen
• Heap: Min/Max-Heap, Priority Queue
• Baum: Hierarchische Struktur, BST, Balancierung
• Graph: Knoten-Kanten-Struktur, Traversierungsalgorithmen
• Big-O Notation: Zeit- und Speicherkomplexität
• IHK-relevant: Wichtig für Algorithmen und Effizienz

Kernkomponenten

1. Array: Indizierte Sammlung mit fester Größe
2. Stack: LIFO-Datenstruktur mit push/pop
3. Queue: FIFO-Datenstruktur mit enqueue/dequeue
4. Heap: Prioritätenbasierte Baumstruktur
5. Baum: Hierarchische Eltern-Kind-Beziehungen
6. Graph: Netzwerk aus Knoten und Kanten
7. Komplexität: Big-O Analyse von Operationen
8. Algorithmen: Suchen, Sortieren, Traversierung

Praxisbeispiele

1. Array und ArrayList in Java

import java.util.*;

public class ArrayDemo {
    public static void main(String[] args) {
        // Einfaches Array (feste Größe)
        int[] zahlen = new int[5];
        zahlen[0] = 10;
        zahlen[1] = 20;
        zahlen[2] = 30;
        zahlen[3] = 40;
        zahlen[4] = 50;
        
        // Direkter Zugriff O(1)
        System.out.println("Element bei Index 2: " + zahlen[2]);
        
        // Lineare Suche O(n)
        int gesucht = 30;
        int index = -1;
        for (int i = 0; i < zahlen.length; i++) {
            if (zahlen[i] == gesucht) {
                index = i;
                break;
            }
        }
        System.out.println("Index von " + gesucht + ": " + index);
        
        // ArrayList (dynamische Größe)
        List<String> namen = new ArrayList<>();
        namen.add("Alice");  // O(1) amortisiert
        namen.add("Bob");    // O(1) amortisiert
        namen.add("Charlie"); // O(1) amortisiert
        
        // Einfügen in der Mitte O(n)
        namen.add(1, "David"); // Verschiebt alle Elemente nach rechts
        
        System.out.println("ArrayList: " + namen);
        
        // Array vs ArrayList Performance
        performanceVergleich();
    }
    
    private static void performanceVergleich() {
        final int GROESSE = 100000;
        
        // Array Performance
        long start = System.nanoTime();
        int[] array = new int[GROESSE];
        for (int i = 0; i < GROESSE; i++) {
            array[i] = i;
        }
        long arrayZeit = System.nanoTime() - start;
        
        // ArrayList Performance
        start = System.nanoTime();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < GROESSE; i++) {
            arrayList.add(i);
        }
        long arrayListZeit = System.nanoTime() - start;
        
        System.out.println("Array Zeit: " + arrayZeit / 1_000_000 + " ms");
        System.out.println("ArrayList Zeit: " + arrayListZeit / 1_000_000 + " ms");
    }
}

2. Stack Implementierung und Verwendung

import java.util.*;

// Stack Implementierung mit Array
class ArrayStack<T> {
    private Object[] elemente;
    private int top;
    private final int kapazitaet;
    
    public ArrayStack(int kapazitaet) {
        this.kapazitaet = kapazitaet;
        this.elemente = new Object[kapazitaet];
        this.top = -1;
    }
    
    public void push(T element) {
        if (isFull()) {
            throw new StackOverflowError("Stack ist voll");
        }
        elemente[++top] = element;
    }
    
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elemente[top--];
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elemente[top];
    }
    
    public boolean isEmpty() {
        return top == -1;
    }
    
    public boolean isFull() {
        return top == kapazitaet - 1;
    }
    
    public int size() {
        return top + 1;
    }
}

// Stack Verwendung
public class StackDemo {
    public static void main(String[] args) {
        // Java Stack Klasse
        Stack<String> stack = new Stack<>();
        
        // Push Operationen
        stack.push("Erstes");
        stack.push("Zweites");
        stack.push("Drittes");
        
        System.out.println("Stack: " + stack);
        System.out.println("Top Element: " + stack.peek());
        
        // Pop Operationen
        while (!stack.isEmpty()) {
            String element = stack.pop();
            System.out.println("Pop: " + element);
        }
        
        // Custom Stack verwenden
        ArrayStack<Integer> meinStack = new ArrayStack<>(5);
        meinStack.push(10);
        meinStack.push(20);
        meinStack.push(30);
        
        System.out.println("\nCustom Stack:");
        while (!meinStack.isEmpty()) {
            System.out.println("Pop: " + meinStack.pop());
        }
        
        // Praktische Anwendung: Klammerprüfung
        String ausdruck = "{[()]}";
        System.out.println("Ausdruck '" + ausdruck + "' ist gültig: " + 
                          pruefeKlammer(ausdruck));
    }
    
    // Klammerprüfung mit Stack
    public static boolean pruefeKlammer(String ausdruck) {
        Stack<Character> stack = new Stack<>();
        
        for (char zeichen : ausdruck.toCharArray()) {
            switch (zeichen) {
                case '(':
                case '[':
                case '{':
                    stack.push(zeichen);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') return false;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') return false;
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') return false;
                    break;
            }
        }
        
        return stack.isEmpty();
    }
}

3. Queue Implementierung und Anwendung

import java.util.*;

// Queue Implementierung mit Array (Circular Queue)
class ArrayQueue<T> {
    private Object[] elemente;
    private int front, rear, size, kapazitaet;
    
    public ArrayQueue(int kapazitaet) {
        this.kapazitaet = kapazitaet;
        this.elemente = new Object[kapazitaet];
        this.front = this.size = 0;
        this.rear = kapazitaet - 1;
    }
    
    public void enqueue(T element) {
        if (isFull()) {
            throw new IllegalStateException("Queue ist voll");
        }
        rear = (rear + 1) % kapazitaet;
        elemente[rear] = element;
        size++;
    }
    
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue ist leer");
        }
        T element = (T) elemente[front];
        front = (front + 1) % kapazitaet;
        size--;
        return element;
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue ist leer");
        }
        return (T) elemente[front];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == kapazitaet;
    }
    
    public int size() {
        return size;
    }
}

// Queue Anwendung
public class QueueDemo {
    public static void main(String[] args) {
        // Java Queue Interface mit LinkedList
        Queue<String> queue = new LinkedList<>();
        
        // Enqueue Operationen
        queue.add("Kunde 1");
        queue.add("Kunde 2");
        queue.add("Kunde 3");
        
        System.out.println("Queue: " + queue);
        
        // Dequeue Operationen
        while (!queue.isEmpty()) {
            String kunde = queue.remove();
            System.out.println("Bedient: " + kunde);
        }
        
        // Priority Queue
        PriorityQueue<Integer> pqueue = new PriorityQueue<>();
        pqueue.add(30);
        pqueue.add(10);
        pqueue.add(20);
        pqueue.add(40);
        
        System.out.println("\nPriority Queue (natürliche Ordnung):");
        while (!pqueue.isEmpty()) {
            System.out.println("Element: " + pqueue.remove());
        }
        
        // Custom Queue verwenden
        ArrayQueue<String> warteschlange = new ArrayQueue<>(3);
        warteschlange.enqueue("Aufgabe A");
        warteschlange.enqueue("Aufgabe B");
        warteschlange.enqueue("Aufgabe C");
        
        System.out.println("\nCustom Queue:");
        while (!warteschlange.isEmpty()) {
            System.out.println("Verarbeite: " + warteschlange.dequeue());
        }
    }
}

4. Heap und Priority Queue

import java.util.*;

// Min-Heap Implementierung
class MinHeap {
    private List<Integer> heap;
    
    public MinHeap() {
        this.heap = new ArrayList<>();
    }
    
    public void insert(int wert) {
        heap.add(wert);
        heapifyUp(heap.size() - 1);
    }
    
    public int extractMin() {
        if (heap.isEmpty()) {
            throw new NoSuchElementException("Heap ist leer");
        }
        
        int min = heap.get(0);
        int letzter = heap.remove(heap.size() - 1);
        
        if (!heap.isEmpty()) {
            heap.set(0, letzter);
            heapifyDown(0);
        }
        
        return min;
    }
    
    public int peek() {
        if (heap.isEmpty()) {
            throw new NoSuchElementException("Heap ist leer");
        }
        return heap.get(0);
    }
    
    private void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap.get(parent) <= heap.get(index)) break;
            
            // Vertauschen
            Collections.swap(heap, parent, index);
            index = parent;
        }
    }
    
    private void heapifyDown(int index) {
        int groesse = heap.size();
        
        while (true) {
            int linkerKind = 2 * index + 1;
            int rechterKind = 2 * index + 2;
            int kleinster = index;
            
            if (linkerKind < groesse && heap.get(linkerKind) < heap.get(kleinster)) {
                kleinster = linkerKind;
            }
            
            if (rechterKind < groesse && heap.get(rechterKind) < heap.get(kleinster)) {
                kleinster = rechterKind;
            }
            
            if (kleinster == index) break;
            
            Collections.swap(heap, index, kleinster);
            index = kleinster;
        }
    }
    
    public boolean isEmpty() {
        return heap.isEmpty();
    }
    
    public int size() {
        return heap.size();
    }
}

// Heap Anwendung
public class HeapDemo {
    public static void main(String[] args) {
        // Java Priority Queue (Min-Heap)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(40);
        
        System.out.println("Min-Heap mit Priority Queue:");
        while (!minHeap.isEmpty()) {
            System.out.println("Min: " + minHeap.remove());
        }
        
        // Max-Heap mit Comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(30);
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(40);
        
        System.out.println("\nMax-Heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println("Max: " + maxHeap.remove());
        }
        
        // Custom Min-Heap
        MinHeap meinHeap = new MinHeap();
        meinHeap.insert(30);
        meinHeap.insert(10);
        meinHeap.insert(20);
        meinHeap.insert(40);
        
        System.out.println("\nCustom Min-Heap:");
        while (!meinHeap.isEmpty()) {
            System.out.println("Min: " + meinHeap.extractMin());
        }
        
        // Heap Sort Demonstration
        heapSortDemo();
    }
    
    private static void heapSortDemo() {
        int[] zahlen = {12, 11, 13, 5, 6, 7};
        
        System.out.println("\nHeap Sort:");
        System.out.println("Original: " + Arrays.toString(zahlen));
        
        // Max-Heap für Heap Sort
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int zahl : zahlen) {
            maxHeap.add(zahl);
        }
        
        int[] sortiert = new int[zahlen.length];
        for (int i = 0; i < zahlen.length; i++) {
            sortiert[i] = maxHeap.remove();
        }
        
        System.out.println("Sortiert: " + Arrays.toString(sortiert));
    }
}

5. Binärbaum und BST

import java.util.*;

// Binärbaum Knoten
class TreeNode<T> {
    T wert;
    TreeNode<T> links;
    TreeNode<T> rechts;
    
    public TreeNode(T wert) {
        this.wert = wert;
        this.links = null;
        this.rechts = null;
    }
}

// Binary Search Tree
class BinarySearchTree<T extends Comparable<T>> {
    private TreeNode<T> wurzel;
    
    public void insert(T wert) {
        wurzel = insertRecursive(wurzel, wert);
    }
    
    private TreeNode<T> insertRecursive(TreeNode<T> knoten, T wert) {
        if (knoten == null) {
            return new TreeNode<>(wert);
        }
        
        if (wert.compareTo(knoten.wert) < 0) {
            knoten.links = insertRecursive(knoten.links, wert);
        } else if (wert.compareTo(knoten.wert) > 0) {
            knoten.rechts = insertRecursive(knoten.rechts, wert);
        }
        
        return knoten;
    }
    
    public boolean search(T wert) {
        return searchRecursive(wurzel, wert);
    }
    
    private boolean searchRecursive(TreeNode<T> knoten, T wert) {
        if (knoten == null) {
            return false;
        }
        
        if (wert.equals(knoten.wert)) {
            return true;
        }
        
        return wert.compareTo(knoten.wert) < 0 
            ? searchRecursive(knoten.links, wert)
            : searchRecursive(knoten.rechts, wert);
    }
    
    public void inorder() {
        inorderRecursive(wurzel);
        System.out.println();
    }
    
    private void inorderRecursive(TreeNode<T> knoten) {
        if (knoten != null) {
            inorderRecursive(knoten.links);
            System.out.print(knoten.wert + " ");
            inorderRecursive(knoten.rechts);
        }
    }
    
    public void preorder() {
        preorderRecursive(wurzel);
        System.out.println();
    }
    
    private void preorderRecursive(TreeNode<T> knoten) {
        if (knoten != null) {
            System.out.print(knoten.wert + " ");
            preorderRecursive(knoten.links);
            preorderRecursive(knoten.rechts);
        }
    }
    
    public void postorder() {
        postorderRecursive(wurzel);
        System.out.println();
    }
    
    private void postorderRecursive(TreeNode<T> knoten) {
        if (knoten != null) {
            postorderRecursive(knoten.links);
            postorderRecursive(knoten.rechts);
            System.out.print(knoten.wert + " ");
        }
    }
}

// BST Anwendung
public class BaumDemo {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        
        // Elemente einfügen
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);
        
        System.out.println("In-Order Traversal (sortiert):");
        bst.inorder(); // 20 30 40 50 60 70 80
        
        System.out.println("Pre-Order Traversal:");
        bst.preorder(); // 50 30 20 40 70 60 80
        
        System.out.println("Post-Order Traversal:");
        bst.postorder(); // 20 40 30 60 80 70 50
        
        // Suchen
        System.out.println("Suche 40: " + bst.search(40)); // true
        System.out.println("Suche 25: " + bst.search(25)); // false
        
        // BST vs Array Performance Vergleich
        performanceVergleich();
    }
    
    private static void performanceVergleich() {
        final int GROESSE = 10000;
        Random random = new Random();
        
        // BST erstellen
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < GROESSE; i++) {
            bst.insert(random.nextInt(GROESSE * 10));
        }
        
        // Array erstellen
        List<Integer> array = new ArrayList<>();
        for (int i = 0; i < GROESSE; i++) {
            array.add(random.nextInt(GROESSE * 10));
        }
        
        int suchZahl = random.nextInt(GROESSE * 10);
        
        // BST Suche O(log n) im Durchschnitt
        long start = System.nanoTime();
        boolean bstGefunden = bst.search(suchZahl);
        long bstZeit = System.nanoTime() - start;
        
        // Array Suche O(n)
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("\nPerformance Vergleich:");
        System.out.println("BST Suche: " + bstZeit / 1000 + " μs, gefunden: " + bstGefunden);
        System.out.println("Array Suche: " + arrayZeit / 1000 + " μs, gefunden: " + arrayGefunden);
    }
}

Big-O Notation Übersicht

Zeitkomplexität

Operation	Array	Stack	Queue	Heap	BST	Graph
Zugriff	O(1)	O(n)	O(n)	O(1)	O(log n)	O(V+E)
Suchen	O(n)	O(n)	O(n)	O(n)	O(log n)	O(V+E)
Einfügen	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(1)
Löschen	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(V+E)

Speicherkomplexität

Datenstruktur	Speicher
Array	O(n)
Stack	O(n)
Queue	O(n)
Heap	O(n)
BST	O(n)
Graph	O(V+E)

Graph-Algorithmen

Graph Implementierung

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjazenzliste;
    
    public Graph() {
        this.adjazenzliste = new HashMap<>();
    }
    
    public void kanteHinzufuegen(int u, int v) {
        adjazenzliste.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjazenzliste.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // Ungerichtet
    }
    
    // Breadth-First Search (BFS)
    public void bfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        besucht.add(start);
        
        while (!queue.isEmpty()) {
            int knoten = queue.remove();
            System.out.print(knoten + " ");
            
            for (int nachbar : adjazenzliste.getOrDefault(knoten, Collections.emptyList())) {
                if (!besucht.contains(nachbar)) {
                    besucht.add(nachbar);
                    queue.add(nachbar);
                }
            }
        }
        System.out.println();
    }
    
    // Depth-First Search (DFS)
    public void dfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        dfsRecursive(start, besucht);
        System.out.println();
    }
    
    private void dfsRecursive(int knoten, Set<Integer> besucht) {
        besucht.add(knoten);
        System.out.print(knoten + " ");
        
        for (int nachbar : adjazenzliste.getOrDefault(knoten, Collections.emptyList())) {
            if (!besucht.contains(nachbar)) {
                dfsRecursive(nachbar, besucht);
            }
        }
    }
}

// Graph Anwendung
public class GraphDemo {
    public static void main(String[] args) {
        Graph graph = new Graph();
        
        // Kanten hinzufügen
        graph.kanteHinzufuegen(0, 1);
        graph.kanteHinzufuegen(0, 2);
        graph.kanteHinzufuegen(1, 3);
        graph.kanteHinzufuegen(2, 4);
        graph.kanteHinzufuegen(3, 4);
        graph.kanteHinzufuegen(4, 5);
        
        System.out.println("BFS ab Knoten 0:");
        graph.bfs(0); // 0 1 2 3 4 5
        
        System.out.println("DFS ab Knoten 0:");
        graph.dfs(0); // 0 1 3 4 2 5
    }
}

Vorteile und Nachteile

Array

• Vorteile: Direkter Zugriff O(1), einfache Implementierung
• Nachteile: Feste Größe, Einfügen/Löschen O(n)

Stack

• Vorteile: Einfache LIFO-Logik, O(1) push/pop
• Nachteile: Nur auf oberstes Element zugreifbar

Queue

• Vorteile: FIFO-Logik, fair für Warteschlangen
• Nachteile: Einfügen am Ende kann teuer sein

Heap

• Vorteile: O(1) Zugriff auf Minimum/Maximum
• Nachteile: Komplexere Implementierung

Baum

• Vorteile: Effiziente Suche O(log n), geordnete Daten
• Nachteile: Balancierung erforderlich

Graph

• Vorteile: Flexible Beziehungen, realistische Modellierung
• Nachteile: Komplexe Algorithmen, hoher Speicherbedarf

Häufige Prüfungsfragen

1. Was ist der Unterschied zwischen Stack und Queue? Stack: LIFO (Last-In, First-Out), Queue: FIFO (First-In, First-Out).

2. Erklären Sie die Big-O Notation für Array-Suche! Lineare Suche O(n) im Worst-Case, direkter Zugriff O(1).

3. Wann verwendet man Heap statt Array? Wenn häufig auf Minimum/Maximum zugegriffen werden muss (Priority Queue).

4. Was ist der Unterschied zwischen BFS und DFS? BFS: Level-order Traversal mit Queue, DFS: Depth-first mit Stack/Rekursion.

Wichtigste Quellen

1. https://de.wikipedia.org/wiki/Datenstruktur
2. https://www.geeksforgeeks.org/data-structures/
3. https://docs.oracle.com/javase/tutorial/collections/interfaces/index.html