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

This guide provides a comprehensive overview of the essential data structures—covering complexity analysis, practical examples, and algorithms.

In a Nutshell

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

Technical Overview

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 is expensive (O(n))

2. Stack (LIFO)

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

3. Queue (FIFO)

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

4. Heap

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

5. Tree

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

6. Graph

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

Key Points to Remember

• 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
• Relevance: Critical for algorithm design and efficiency

Core Components

1. Array: Indexed collection with fixed size
2. Stack: LIFO structure with push/pop
3. Queue: FIFO 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[] numbers = new int[5];
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;
        
        // Direct access O(1)
        System.out.println("Element at index 2: " + numbers[2]);
        
        // Linear search O(n)
        int target = 30;
        int index = -1;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == target) {
                index = i;
                break;
            }
        }
        System.out.println("Index of " + target + ": " + index);
        
        // ArrayList (dynamic size)
        List<String> names = new ArrayList<>();
        names.add("Alice");  // O(1) amortized
        names.add("Bob");    // O(1) amortized
        names.add("Charlie"); // O(1) amortized
        
        // Insert in the middle O(n)
        names.add(1, "David"); // Shifts all elements to the right
        
        System.out.println("ArrayList: " + names);
        
        // Array vs ArrayList performance
        performanceComparison();
    }
    
    private static void performanceComparison() {
        final int SIZE = 100000;
        
        // Array performance
        long start = System.nanoTime();
        int[] array = new int[SIZE];
        for (int i = 0; i < SIZE; i++) {
            array[i] = i;
        }
        long arrayTime = System.nanoTime() - start;
        
        // ArrayList performance
        start = System.nanoTime();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < SIZE; i++) {
            arrayList.add(i);
        }
        long arrayListTime = System.nanoTime() - start;
        
        System.out.println("Array time: " + arrayTime / 1_000_000 + " ms");
        System.out.println("ArrayList time: " + arrayListTime / 1_000_000 + " ms");
    }
}

2. Stack Implementation and Usage

import java.util.*;

// Stack implementation with array
class ArrayStack<T> {
    private Object[] elements;
    private int top;
    private final int capacity;
    
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
        this.top = -1;
    }
    
    public void push(T element) {
        if (isFull()) {
            throw new StackOverflowError("Stack is full");
        }
        elements[++top] = element;
    }
    
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elements[top--];
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elements[top];
    }
    
    public boolean isEmpty() {
        return top == -1;
    }
    
    public boolean isFull() {
        return top == capacity - 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> myStack = new ArrayStack<>(5);
        myStack.push(10);
        myStack.push(20);
        myStack.push(30);
        
        System.out.println("\nCustom Stack:");
        while (!myStack.isEmpty()) {
            System.out.println("Pop: " + myStack.pop());
        }
        
        // Practical application: bracket validation
        String expression = "{[()]}";
        System.out.println("Expression '" + expression + "' is valid: " + 
                          validateBrackets(expression));
    }
    
    // Bracket validation with stack
    public static boolean validateBrackets(String expression) {
        Stack<Character> stack = new Stack<>();
        
        for (char character : expression.toCharArray()) {
            switch (character) {
                case '(':
                case '[':
                case '{':
                    stack.push(character);
                    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 Usage

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 kunde = queue.remove();
            System.out.println("Served: " + 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());
        }
        
        // Use custom queue
        ArrayQueue<String> warteschlange = new ArrayQueue<>(3);
        warteschlange.enqueue("Task A");
        warteschlange.enqueue("Task B");
        warteschlange.enqueue("Task C");
        
        System.out.println("\nCustom Queue:");
        while (!warteschlange.isEmpty()) {
            System.out.println("Process: " + 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 usage
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("Sorted: " + 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 usage
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("Search 40: " + bst.search(40)); // true
        System.out.println("Search 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
    }
}

Strengths and Weaknesses

Array

• Strengths: O(1) random access, straightforward to implement
• Weaknesses: Fixed size, insertion and deletion both O(n)

Stack

• Strengths: Simple LIFO semantics, O(1) push and pop operations
• Weaknesses: Can only access the top element

Queue

• Strengths: FIFO semantics, fair for scheduling scenarios
• Weaknesses: Insertion at the rear can be expensive

Heap

• Strengths: O(1) access to min or max element
• Weaknesses: More complex to implement

Tree

• Strengths: Efficient O(log n) search, maintains ordered data
• Weaknesses: Requires balancing for optimal performance

Graph

• Strengths: Flexible relationship modeling, realistic for many problems
• Weaknesses: Complex algorithms, high memory overhead

Common Exam Questions

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

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

3. When should 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 traverses level by level using a queue, while DFS goes depth-first 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