Datenstrukturen Übersicht: Array, Stack, Queue, Heap, Baum & Graph

Dieser Beitrag ist eine kompakte Übersicht der wichtigsten Datenstrukturen – mit Performance-Analyse, Einsatzgebieten und Big-O Notation.

In a Nutshell

Die Kern-Datenstrukturen Array, Stack, Queue, Heap, Baum und Graph bilden die Grundlage effizienter Algorithmen. Sie unterscheiden sich in Zugriffszeit, Speicherbedarf und Anwendungsgebieten.

Kompakte Fachbeschreibung

Datenstrukturen organisieren Daten für effizienten Zugriff und Verarbeitung. Jede Struktur hat spezifische Eigenschaften und optimale Einsatzgebiete.

Performance-Übersicht:

Array

Zugriff: O(1) - Direkt per Index
Einfügen/Löschen: O(n) - Elemente müssen verschoben werden
Speicher: O(n) - Zusammenhängender Speicher
Einsatz: Feste Größe, häufiger Random Access

Stack (LIFO)

Push/Pop: O(1) - Nur oberstes Element
Speicher: O(n) - Dynamisch oder fix
Einsatz: Methodenaufrufe, Backtracking, Parser

Queue (FIFO)

Enqueue/Dequeue: O(1) - Vorne/Hinten
Speicher: O(n) - Circular Queue möglich
Einsatz: Warteschlangen, BFS, Buffer

Heap (Priority Queue)

Insert: O(log n) - Heap-Eigenschaft erhalten
Extract Min/Max: O(log n) - Wurzel entfernen
Peek: O(1) - Minimum/Maximum ansehen
Einsatz: Prioritäten, Scheduling, Heap Sort

Baum (BST)

Suchen: O(log n) - Balanciert
Einfügen/Löschen: O(log n) - Balanciert
Speicher: O(n) - Knotenbasiert
Einsatz: Geordnete Daten, Datenbanken

Graph

Traversierung: O(V+E) - V=Knoten, E=Kanten
Speicher: O(V+E) - Adjazenzliste
Einsatz: Netzwerke, Routenplanung

Prüfungsrelevante Stichpunkte

Array: O(1) Zugriff, feste Größe, zusammenhängender Speicher
Stack: LIFO-Prinzip, push/pop O(1), Call Stack
Queue: FIFO-Prinzip, enqueue/dequeue O(1), Buffer
Heap: Priority Queue, O(log n) insert/extract, O(1) peek
Baum: Hierarchisch, O(log n) bei Balancierung, BST
Graph: Knoten-Kanten-Struktur, BFS/DFS O(V+E)
Big-O Notation: Zeit- und Speicherkomplexität
IHK-relevant: Fundament für Algorithmen und Effizienz

Kernkomponenten

Array: Indizierte Sammlung mit direktem Zugriff
Stack: LIFO-Datenstruktur für Rückverfolgung
Queue: FIFO-Datenstruktur für Warteschlangen
Heap: Prioritätenbasierte Baumstruktur
Baum: Hierarchische Eltern-Kind-Beziehungen
Graph: Netzwerk aus Knoten und Kanten
Performance: Big-O Analyse von Operationen
Anwendung: Optimale Strukturauswahl

Praxisbeispiele

1. Array vs ArrayList Performance

import java.util.*;

public class ArrayPerformance {
    public static void main(String[] args) {
        final int GROESSE = 100_000;
        
        // Array (feste Größe)
        long start = System.nanoTime();
        int[] array = new int[GROESSE];
        for (int i = 0; i < GROESSE; i++) {
            array[i] = i; // O(1) Schreiben
        }
        long arrayZeit = System.nanoTime() - start;
        
        // ArrayList (dynamisch)
        start = System.nanoTime();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < GROESSE; i++) {
            arrayList.add(i); // O(1) amortisiert
        }
        long arrayListZeit = System.nanoTime() - start;
        
        // Random Access Test
        Random random = new Random();
        
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            int index = random.nextInt(GROESSE);
            int wert = array[index]; // O(1)
        }
        long arrayAccess = System.nanoTime() - start;
        
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            int index = random.nextInt(GROESSE);
            int wert = arrayList.get(index); // O(1)
        }
        long arrayListAccess = System.nanoTime() - start;
        
        System.out.println("Array Füllzeit: " + arrayZeit / 1_000_000 + " ms");
        System.out.println("ArrayList Füllzeit: " + arrayListZeit / 1_000_000 + " ms");
        System.out.println("Array Access: " + arrayAccess / 1000 + " μs");
        System.out.println("ArrayList Access: " + arrayListAccess / 1000 + " μs");
    }
}

2. Stack vs Queue Anwendung

import java.util.*;

public class StackQueueDemo {
    public static void main(String[] args) {
        // Stack für Klammerprüfung (LIFO)
        String ausdruck = "{[()()]}";
        if (pruefeKlammer(ausdruck)) {
            System.out.println("Ausdruck '" + ausdruck + "' ist gültig");
        }
        
        // Queue für Druckerwarteschlange (FIFO)
        Queue<String> druckerQueue = new LinkedList<>();
        druckerQueue.add("Dokument1.pdf");
        druckerQueue.add("Dokument2.pdf");
        druckerQueue.add("Dokument3.pdf");
        
        System.out.println("Druckerwarteschlange:");
        while (!druckerQueue.isEmpty()) {
            String dokument = druckerQueue.remove();
            System.out.println("Drucke: " + dokument);
        }
        
        // Performance Vergleich
        performanceVergleich();
    }
    
    // Klammerprüfung mit Stack
    private 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();
    }
    
    private static void performanceVergleich() {
        final int OPERATIONEN = 1_000_000;
        
        // Stack Performance
        long start = System.nanoTime();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < OPERATIONEN; i++) {
            stack.push(i);
        }
        for (int i = 0; i < OPERATIONEN; i++) {
            stack.pop();
        }
        long stackZeit = System.nanoTime() - start;
        
        // Queue Performance
        start = System.nanoTime();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < OPERATIONEN; i++) {
            queue.add(i);
        }
        for (int i = 0; i < OPERATIONEN; i++) {
            queue.remove();
        }
        long queueZeit = System.nanoTime() - start;
        
        System.out.println("\nPerformance Vergleich (" + OPERATIONEN + " Operationen):");
        System.out.println("Stack Zeit: " + stackZeit / 1_000_000 + " ms");
        System.out.println("Queue Zeit: " + queueZeit / 1_000_000 + " ms");
    }
}

3. Priority Queue (Heap) Anwendung

import java.util.*;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // Min-Heap für aufsteigende Sortierung
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(40);
        minHeap.add(5);
        
        System.out.println("Min-Heap (Priority Queue):");
        while (!minHeap.isEmpty()) {
            System.out.println("Extract 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);
        maxHeap.add(5);
        
        System.out.println("\nMax-Heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println("Extract Max: " + maxHeap.remove());
        }
        
        // Task-Scheduling mit Prioritäten
        taskSchedulingDemo();
    }
    
    private static void taskSchedulingDemo() {
        // Task mit Priorität
        class Task {
            String name;
            int priority;
            
            Task(String name, int priority) {
                this.name = name;
                this.priority = priority;
            }
            
            @Override
            public String toString() {
                return name + " (Prio: " + priority + ")";
            }
        }
        
        // Priority Queue für Tasks
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            (t1, t2) -> Integer.compare(t2.priority, t1.priority) // Max-Heap
        );
        
        taskQueue.add(new Task("Email senden", 2));
        taskQueue.add(new Task("Datenbank backup", 5));
        taskQueue.add(new Task("Log analysieren", 1));
        taskQueue.add(new Task("Security update", 10));
        
        System.out.println("\nTask-Scheduling (hohe Priorität zuerst):");
        while (!taskQueue.isEmpty()) {
            System.out.println("Ausführen: " + taskQueue.remove());
        }
    }
}

4. Suchbaum vs Array Suche

import java.util.*;

class TreeNode {
    int wert;
    TreeNode links, rechts;
    
    TreeNode(int wert) {
        this.wert = wert;
        this.links = this.rechts = null;
    }
}

class BinarySearchTree {
    TreeNode wurzel;
    
    void insert(int wert) {
        wurzel = insertRecursive(wurzel, wert);
    }
    
    private TreeNode insertRecursive(TreeNode knoten, int wert) {
        if (knoten == null) {
            return new TreeNode(wert);
        }
        
        if (wert < knoten.wert) {
            knoten.links = insertRecursive(knoten.links, wert);
        } else if (wert > knoten.wert) {
            knoten.rechts = insertRecursive(knoten.rechts, wert);
        }
        
        return knoten;
    }
    
    boolean search(int wert) {
        return searchRecursive(wurzel, wert);
    }
    
    private boolean searchRecursive(TreeNode knoten, int wert) {
        if (knoten == null) return false;
        if (knoten.wert == wert) return true;
        
        return wert < knoten.wert 
            ? searchRecursive(knoten.links, wert)
            : searchRecursive(knoten.rechts, wert);
    }
}

public class SuchbaumVsArray {
    public static void main(String[] args) {
        final int GROESSE = 100_000;
        Random random = new Random();
        
        // BST aufbauen
        BinarySearchTree 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) im Worst-Case
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("Suche nach " + suchZahl + ":");
        System.out.println("BST Zeit: " + bstZeit / 1000 + " μs, gefunden: " + bstGefunden);
        System.out.println("Array Zeit: " + arrayZeit / 1000 + " μs, gefunden: " + arrayGefunden);
        
        // Sortierter Array (Binary Search)
        Collections.sort(array);
        start = System.nanoTime();
        int index = Collections.binarySearch(array, suchZahl);
        long binaryZeit = System.nanoTime() - start;
        
        System.out.println("Binary Search Zeit: " + binaryZeit / 1000 + " μs, Index: " + index);
    }
}

5. Graph Traversierung Vergleich

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjazenzliste = new HashMap<>();
    
    void kanteHinzufuegen(int u, int v) {
        adjazenzliste.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjazenzliste.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }
    
    // Breadth-First Search (Queue)
    void bfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        besucht.add(start);
        
        System.out.print("BFS: ");
        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 (Stack/Rekursion)
    void dfs(int start) {
        Set<Integer> besucht = new HashSet<>();
        dfsRecursive(start, besucht);
    }
    
    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);
            }
        }
    }
}

public class GraphTraversal {
    public static void main(String[] args) {
        Graph graph = new Graph();
        
        // Graph aufbauen
        graph.kanteHinzufuegen(0, 1);
        graph.kanteHinzufuegen(0, 2);
        graph.kanteHinzufuegen(1, 3);
        graph.kanteHinzufuegen(2, 4);
        graph.kanteHinzufuegen(3, 4);
        graph.ketteHinzufuegen(4, 5);
        
        System.out.println("Graph Traversierung:");
        graph.bfs(0); // Level-order: 0 1 2 3 4 5
        graph.dfs(0); // Depth-first: 0 1 3 4 2 5
    }
}

Big-O Notation Vergleichstabelle

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	Bemerkung
Array	O(n)	Zusammenhängend
Stack	O(n)	Dynamisch
Queue	O(n)	Circular möglich
Heap	O(n)	Baumstruktur
BST	O(n)	Knotenbasiert
Graph	O(V+E)	V=Knoten, E=Kanten

Anwendungsszenarien

Wann welche Datenstruktur?

Array verwenden wenn:

Größe bekannt und konstant
Häufiger Random Access benötigt
Speicherplatz kritisch (zusammenhängend)

Stack verwenden wenn:

LIFO-Verhalten benötigt
Rückverfolgung von Zuständen
Methodenaufrufe rekursiver Funktionen

Queue verwenden wenn:

FIFO-Verhalten benötigt
Warteschlangen realisieren
Breadth-First Search

Heap verwenden wenn:

Prioritäten wichtig
Häufig auf Minimum/Maximum zugegriffen
Scheduling-Algorithmen

Baum verwenden wenn:

Geordnete Daten gespeichert werden
Effiziente Suche erforderlich
Hierarchische Beziehungen

Graph verwenden wenn:

Netzwerkbeziehungen modelliert
Routenplanung erforderlich
Viele-zu-viele Beziehungen

Performance-Tipps

Array-Optimierung

// Schleife vorbereiten
int[] array = new int[1000];
int laenge = array.length; // Nicht in jeder Iteration

for (int i = 0; i < laenge; i++) {
    array[i] = i;
}

Stack-Optimierung

// Array statt Stack für feste Größe
int[] stack = new int[1000];
int top = -1;

void push(int wert) {
    stack[++top] = wert;
}

int pop() {
    return stack[top--];
}

Queue-Optimierung

// Circular Queue für feste Größe
int[] queue = new int[1000];
int front = 0, rear = 0;

void enqueue(int wert) {
    queue[rear = (rear + 1) % queue.length] = wert;
}

int dequeue() {
    return queue[front = (front + 1) % queue.length];
}

Häufige Prüfungsfragen

Welche Datenstruktur für Druckerwarteschlange? Queue (FIFO) - erste Anfrage wird zuerst bearbeitet.
Warum ist BST-Suche schneller als Array-Suche? BST: O(log n) durch Halbierung, Array: O(n) durch lineare Suche.
Was ist der Unterschied zwischen Stack und Queue? Stack: LIFO (Last-In, First-Out), Queue: FIFO (First-In, First-Out).
Wann verwendet man Heap statt Array? Wenn häufig auf Minimum/Maximum zugegriffen werden muss (Priority Queue).

Datenstrukturen Übersicht: Array, Stack, Queue, Heap, Baum & Graph

Datenstrukturen Übersicht: Array, Stack, Queue, Heap, Baum & Graph

In a Nutshell

Kompakte Fachbeschreibung

Array

Stack (LIFO)

Queue (FIFO)

Heap (Priority Queue)

Baum (BST)

Graph

Prüfungsrelevante Stichpunkte

Kernkomponenten

Praxisbeispiele

1. Array vs ArrayList Performance

2. Stack vs Queue Anwendung

3. Priority Queue (Heap) Anwendung

4. Suchbaum vs Array Suche

5. Graph Traversierung Vergleich

Big-O Notation Vergleichstabelle

Zeitkomplexität

Speicherkomplexität

Anwendungsszenarien

Wann welche Datenstruktur?

Performance-Tipps

Array-Optimierung

Stack-Optimierung

Queue-Optimierung

Häufige Prüfungsfragen

Wichtigste Quellen

Ähnliche Beiträge

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

Algorithmen Grundlagen: Komplexitätsanalyse, Big-O-Notation, Such- & Sortieralgorithmen

Datenstrukturen Grundlagen: Stack, Queue, Heap, Array, Baum, Graph

Datenstrukturen Übersicht: Array, Stack, Queue, Heap, Baum & Graph

IRC-Mania Die Seite rund um Sicherheit und Programmierung

In a Nutshell

Kompakte Fachbeschreibung

Array

Stack (LIFO)

Queue (FIFO)

Heap (Priority Queue)

Baum (BST)

Graph

Prüfungsrelevante Stichpunkte

Kernkomponenten

Praxisbeispiele

1. Array vs ArrayList Performance

2. Stack vs Queue Anwendung

3. Priority Queue (Heap) Anwendung

4. Suchbaum vs Array Suche

5. Graph Traversierung Vergleich

IRC-Security.de

Big-O Notation Vergleichstabelle

Zeitkomplexität

Speicherkomplexität

Anwendungsszenarien

Wann welche Datenstruktur?

Performance-Tipps

Array-Optimierung

Stack-Optimierung

Queue-Optimierung

Häufige Prüfungsfragen

Wichtigste Quellen

Premium VPS Hosting

Ähnliche Beiträge

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

Algorithmen Grundlagen: Komplexitätsanalyse, Big-O-Notation, Such- & Sortieralgorithmen

Datenstrukturen Grundlagen: Stack, Queue, Heap, Array, Baum, Graph