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

This article provides a comprehensive overview of the most important data structures—including complexity analysis, practical examples, and algorithms.

In a Nutshell

Data structures are methods of organizing and storing data so that it can be accessed and modified efficiently. Choosing the right structure is critical for performance.

Technical Definition

Data structures are fundamental building blocks of software development that define how data is organized and managed. Each structure has specific characteristics and use cases.

Key data structures:

1. Array

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

2. Stack (LIFO)

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

3. Queue (FIFO)

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

4. Heap

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

5. Tree

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

6. Graph

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

Key Takeaways

• 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
• Efficiency: Critical for algorithm performance

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

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 usage
public class QueueDemo {
    public static void main(String[] args) {
        // Java Queue interface with LinkedList
        Queue<String> queue = new LinkedList<>();
        
        // Enqueue operations
        queue.add("Customer 1");
        queue.add("Customer 2");
        queue.add("Customer 3");
        
        System.out.println("Queue: " + queue);
        
        // Dequeue operations
        while (!queue.isEmpty()) {
            String customer = queue.remove();
            System.out.println("Served: " + customer);
        }
        
        // 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());
        }
        
        // Use custom queue
        ArrayQueue<String> waitlist = new ArrayQueue<>(3);
        waitlist.enqueue("Task A");
        waitlist.enqueue("Task B");
        waitlist.enqueue("Task C");
        
        System.out.println("\nCustom Queue:");
        while (!waitlist.isEmpty()) {
            System.out.println("Processing: " + waitlist.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 value) {
        heap.add(value);
        heapifyUp(heap.size() - 1);
    }
    
    public int extractMin() {
        if (heap.isEmpty()) {
            throw new NoSuchElementException("Heap ist leer");
        }
        
        int min = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        
        if (!heap.isEmpty()) {
            heap.set(0, last);
            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 size = heap.size();
        
        while (true) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int smallest = index;
            
            if (leftChild < size && heap.get(leftChild) < heap.get(smallest)) {
                smallest = leftChild;
            }
            
            if (rightChild < size && heap.get(rightChild) < heap.get(smallest)) {
                smallest = rightChild;
            }
            
            if (smallest == index) break;
            
            Collections.swap(heap, index, smallest);
            index = smallest;
        }
    }
    
    public boolean isEmpty() {
        return heap.isEmpty();
    }
    
    public int size() {
        return heap.size();
    }
}

// Heap usage
public class HeapDemo {
    public static void main(String[] args) {
        // Java PriorityQueue (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 PriorityQueue:");
        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 myHeap = new MinHeap();
        myHeap.insert(30);
        myHeap.insert(10);
        myHeap.insert(20);
        myHeap.insert(40);
        
        System.out.println("\nCustom Min-Heap:");
        while (!myHeap.isEmpty()) {
            System.out.println("Min: " + myHeap.extractMin());
        }
        
        // Heap sort demonstration
        heapSortDemo();
    }
    
    private static void heapSortDemo() {
        int[] numbers = {12, 11, 13, 5, 6, 7};
        
        System.out.println("\nHeap Sort:");
        System.out.println("Original: " + Arrays.toString(numbers));
        
        // Max-heap for heap sort
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int number : numbers) {
            maxHeap.add(number);
        }
        
        int[] sorted = new int[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            sorted[i] = maxHeap.remove();
        }
        
        System.out.println("Sorted: " + Arrays.toString(sorted));
    }
}

5. Binary Tree and BST

import java.util.*;

// Binary tree node
class TreeNode<T> {
    T value;
    TreeNode<T> left;
    TreeNode<T> right;
    
    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// Binary search tree
class BinarySearchTree<T extends Comparable<T>> {
    private TreeNode<T> root;
    
    public void insert(T value) {
        root = insertRecursive(root, value);
    }
    
    private TreeNode<T> insertRecursive(TreeNode<T> node, T value) {
        if (node == null) {
            return new TreeNode<>(value);
        }
        
        if (value.compareTo(node.value) < 0) {
            node.left = insertRecursive(node.left, value);
        } else if (value.compareTo(node.value) > 0) {
            node.right = insertRecursive(node.right, value);
        }
        
        return node;
    }
    
    public boolean search(T value) {
        return searchRecursive(root, value);
    }
    
    private boolean searchRecursive(TreeNode<T> node, T value) {
        if (node == null) {
            return false;
        }
        
        if (value.equals(node.value)) {
            return true;
        }
        
        return value.compareTo(node.value) < 0 
            ? searchRecursive(node.left, value)
            : searchRecursive(node.right, value);
    }
    
    public void inorder() {
        inorderRecursive(root);
        System.out.println();
    }
    
    private void inorderRecursive(TreeNode<T> node) {
        if (node != null) {
            inorderRecursive(node.left);
            System.out.print(node.value + " ");
            inorderRecursive(node.right);
        }
    }
    
    public void preorder() {
        preorderRecursive(root);
        System.out.println();
    }
    
    private void preorderRecursive(TreeNode<T> node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preorderRecursive(node.left);
            preorderRecursive(node.right);
        }
    }
    
    public void postorder() {
        postorderRecursive(root);
        System.out.println();
    }
    
    private void postorderRecursive(TreeNode<T> node) {
        if (node != null) {
            postorderRecursive(node.left);
            postorderRecursive(node.right);
            System.out.print(node.value + " ");
        }
    }
}

// BST usage
public class TreeDemo {
    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("Search 40: " + bst.search(40)); // true
        System.out.println("Search 25: " + bst.search(25)); // false
        
        // BST vs array performance comparison
        performanceComparison();
    }
    
    private static void performanceComparison() {
        final int SIZE = 10000;
        Random random = new Random();
        
        // Create BST
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < SIZE; i++) {
            bst.insert(random.nextInt(SIZE * 10));
        }
        
        // Create array
        List<Integer> array = new ArrayList<>();
        for (int i = 0; i < SIZE; i++) {
            array.add(random.nextInt(SIZE * 10));
        }
        
        int searchNumber = random.nextInt(SIZE * 10);
        
        // BST search O(log n) on average
        long start = System.nanoTime();
        boolean bstFound = bst.search(searchNumber);
        long bstTime = System.nanoTime() - start;
        
        // Array search O(n)
        start = System.nanoTime();
        boolean arrayFound = array.contains(searchNumber);
        long arrayTime = System.nanoTime() - start;
        
        System.out.println("\nPerformance Comparison:");
        System.out.println("BST search: " + bstTime / 1000 + " μs, found: " + bstFound);
        System.out.println("Array search: " + arrayTime / 1000 + " μs, found: " + arrayFound);
    }
}

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

Pros and Cons

Array

• Pros: Constant-time access O(1), straightforward to implement
• Cons: Fixed size, insertion and deletion are O(n)

Stack

• Pros: Simple LIFO logic, O(1) push and pop operations
• Cons: Only the top element is accessible

Queue

• Pros: FIFO logic, fair for scheduling scenarios
• Cons: Rear insertion can become expensive

Heap

• Pros: O(1) access to min or max elements
• Cons: More complex to implement

Tree

• Pros: Efficient search O(log n), maintains ordered data
• Cons: Requires balancing

Graph

• Pros: Flexible relationships, realistic modeling of complex systems
• Cons: Complex algorithms, high memory overhead

Common Exam Questions

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

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

3. When would you use a Heap instead of an Array? When you frequently need to access the minimum or maximum element (Priority Queue).

4. What’s the difference between BFS and DFS? BFS: level-order traversal using a Queue, DFS: depth-first traversal using a Stack or recursion.

Key Resources

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