Data Structures: Stack, Queue, Heap, Array, Tree, Graph & Algorithms

This article is a comprehensive overview of important data structures – including complexity analysis, practical examples, and algorithms.

In a Nutshell

Data structures are methods of organizing and storing data so that they can be efficiently accessed and modified. Choosing the right structure is crucial for efficiency.

Compact Technical Description

Data structures are fundamental building blocks of software development that define the organization and management of data. Each structure has specific properties and areas of application.

Important data structures:

1. Array

• Description: Fixed, contiguous sequence of elements of the same type
• Access: Direct via index (O(1))
• Disadvantages: Fixed size, insertion/deletion expensive (O(n))

2. Stack (LIFO)

• Principle: Last-In, First-Out
• Operations: push() (add to top), pop() (remove from top)
• Usage: Method calls, backtracking, parsers

3. Queue (FIFO)

• Principle: First-In, First-Out
• Operations: enqueue() (add to back), dequeue() (remove from front)
• Usage: Print queue, breadth-first search

4. Heap

• Description: Binary tree with heap property
• Types: Min-heap, max-heap
• Usage: Priority queues, heap sort

5. Tree

• Description: Hierarchical data structure
• Types: Binary tree, BST, AVL, B-tree
• Usage: Search algorithms, databases

6. Graph

• Description: Nodes and edges
• Types: Directed/undirected, weighted/unweighted
• Usage: Networks, route planning

Exam-Relevant Key Points

• Array: Direct access O(1), fixed size
• Stack: LIFO principle, push/pop operations
• Queue: FIFO principle, enqueue/dequeue operations
• Heap: Min/max-heap, priority queue
• Tree: Hierarchical structure, BST, balancing
• Graph: Node-edge structure, traversal algorithms
• Big-O Notation: Time and space complexity
• IHK-relevant: Important for algorithms and efficiency

Core Components

1. Array: Indexed collection with fixed size
2. Stack: LIFO data structure with push/pop
3. Queue: FIFO data structure with enqueue/dequeue
4. Heap: Priority-based tree structure
5. Tree: Hierarchical parent-child relationships
6. Graph: Network of nodes and edges
7. Complexity: Big-O analysis of operations
8. Algorithms: Searching, sorting, traversal

Practical Examples

1. Array and ArrayList in Java

import java.util.*;

public class ArrayDemo {
    public static void main(String[] args) {
        // Simple array (fixed size)
        int[] zahlen = new int[5];
        zahlen[0] = 10;
        zahlen[1] = 20;
        zahlen[2] = 30;
        zahlen[3] = 40;
        zahlen[4] = 50;
        
        // Direct access O(1)
        System.out.println("Element at index 2: " + zahlen[2]);
        
        // Linear search 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 of " + gesucht + ": " + index);
        
        // ArrayList (dynamic size)
        List<String> namen = new ArrayList<>();
        namen.add("Alice");  // O(1) amortized
        namen.add("Bob");    // O(1) amortized
        namen.add("Charlie"); // O(1) amortized
        
        // Insertion in the middle O(n)
        namen.add(1, "David"); // Shifts all elements to the right
        
        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 time: " + arrayZeit / 1_000_000 + " ms");
        System.out.println("ArrayList time: " + arrayListZeit / 1_000_000 + " ms");
    }
}

2. Stack Implementation and Usage

import java.util.*;

// Stack implementation with 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 is full");
        }
        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 usage
public class StackDemo {
    public static void main(String[] args) {
        // Java Stack class
        Stack<String> stack = new Stack<>();
        
        // Push operations
        stack.push("First");
        stack.push("Second");
        stack.push("Third");
        
        System.out.println("Stack: " + stack);
        System.out.println("Top element: " + stack.peek());
        
        // Pop operations
        while (!stack.isEmpty()) {
            String element = stack.pop();
            System.out.println("Pop: " + element);
        }
        
        // Use custom stack
        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());
        }
        
        // Practical application: bracket validation
        String ausdruck = "{[()]}";
        System.out.println("Expression '" + ausdruck + "' is valid: " + 
                          pruefeKlammer(ausdruck));
    }
    
    // Bracket validation with 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 Implementation and Application

import java.util.*;

// Queue Implementation with 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 Application
public class QueueDemo {
    public static void main(String[] args) {
        // Java Queue Interface with LinkedList
        Queue<String> queue = new LinkedList<>();
        
        // Enqueue Operations
        queue.add("Kunde 1");
        queue.add("Kunde 2");
        queue.add("Kunde 3");
        
        System.out.println("Queue: " + queue);
        
        // Dequeue Operations
        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 (natural order):");
        while (!pqueue.isEmpty()) {
            System.out.println("Element: " + pqueue.remove());
        }
        
        // Custom Queue usage
        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 and Priority Queue

import java.util.*;

// Min-Heap Implementation
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;
            
            // Swap
            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 Application
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 with Priority Queue:");
        while (!minHeap.isEmpty()) {
            System.out.println("Min: " + minHeap.remove());
        }
        
        // Max-Heap with 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 for 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. Binary Tree and BST

import java.util.*;

// Binary Tree Node
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 Application
public class BaumDemo {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        
        // Insert elements
        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 (sorted):");
        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
        
        // Search
        System.out.println("Suche 40: " + bst.search(40)); // true
        System.out.println("Suche 25: " + bst.search(25)); // false
        
        // BST vs Array Performance Comparison
        performanceVergleich();
    }
    
    private static void performanceVergleich() {
        final int GROESSE = 10000;
        Random random = new Random();
        
        // Create BST
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < GROESSE; i++) {
            bst.insert(random.nextInt(GROESSE * 10));
        }
        
        // Create array
        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 search O(log n) on average
        long start = System.nanoTime();
        boolean bstGefunden = bst.search(suchZahl);
        long bstZeit = System.nanoTime() - start;
        
        // Array search O(n)
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("\nPerformance Comparison:");
        System.out.println("BST Search: " + bstZeit / 1000 + " μs, found: " + bstGefunden);
        System.out.println("Array Search: " + arrayZeit / 1000 + " μs, found: " + arrayGefunden);
    }
}

Big-O Notation Overview

Time Complexity

Operation	Array	Stack	Queue	Heap	BST	Graph
Access	O(1)	O(n)	O(n)	O(1)	O(log n)	O(V+E)
Search	O(n)	O(n)	O(n)	O(n)	O(log n)	O(V+E)
Insert	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(1)
Delete	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(V+E)

Space Complexity

Data Structure	Memory
Array	O(n)
Stack	O(n)
Queue	O(n)
Heap	O(n)
BST	O(n)
Graph	O(V+E)

Graph Algorithms

Graph Implementation

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
    }
}

Advantages and Disadvantages

Array

• Advantages: Direct access O(1), simple implementation
• Disadvantages: Fixed size, insert/delete O(n)

Stack

• Advantages: Simple LIFO logic, O(1) push/pop
• Disadvantages: Only accessible from top element

Queue

• Advantages: FIFO logic, fair for queuing
• Disadvantages: Insertion at end can be expensive

Heap

• Advantages: O(1) access to minimum/maximum
• Disadvantages: More complex implementation

Tree

• Advantages: Efficient search O(log n), ordered data
• Disadvantages: Balancing required

Graph

• Advantages: Flexible relationships, realistic modeling
• Disadvantages: Complex algorithms, high memory usage

Common Exam Questions

1. What is the difference between Stack and Queue? Stack: LIFO (Last-In, First-Out), Queue: FIFO (First-In, First-Out).

2. Explain the Big-O notation for array search! Linear search O(n) in worst-case, direct access O(1).

3. When do you use Heap instead of Array? When frequently accessing minimum/maximum elements (Priority Queue).

4. What is the difference between BFS and DFS? BFS: Level-order traversal with Queue, DFS: Depth-first with Stack/recursion.

Most Important Sources

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