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

This guide provides a compact overview of the core data structures – complete with performance analysis, use cases, and Big-O notation.

In a Nutshell

Arrays, stacks, queues, heaps, trees, and graphs form the foundation of efficient algorithms. Each differs in access time, memory requirements, and optimal applications.

Quick Technical Reference

Data structures organize information for fast access and manipulation. Every structure has specific strengths and ideal use cases.

Performance at a glance:

Array

• Access: O(1) – Direct lookup by index
• Insert/Delete: O(n) – Requires shifting elements
• Memory: O(n) – Contiguous allocation
• Best for: Fixed-size collections with frequent random access

Stack (LIFO)

• Push/Pop: O(1) – Only top element affected
• Memory: O(n) – Dynamic or fixed
• Best for: Function calls, backtracking, parsing

Queue (FIFO)

• Enqueue/Dequeue: O(1) – Front and back operations
• Memory: O(n) – Circular queues available
• Best for: Buffers, breadth-first search, task scheduling

Heap (Priority Queue)

• Insert: O(log n) – Maintains heap property
• Extract Min/Max: O(log n) – Remove root
• Peek: O(1) – View min/max without removing
• Best for: Priority scheduling, heapsort, top-k problems

Tree (BST)

• Search: O(log n) – When balanced
• Insert/Delete: O(log n) – When balanced
• Memory: O(n) – Node-based
• Best for: Ordered data, database indexing

Graph

• Traversal: O(V+E) – V = vertices, E = edges
• Memory: O(V+E) – Adjacency list representation
• Best for: Networks, routing, social graphs

Key Takeaways for Interviews

• Array: O(1) access, fixed size, contiguous memory
• Stack: LIFO principle, O(1) push/pop, call stack implementation
• Queue: FIFO principle, O(1) enqueue/dequeue, buffer management
• Heap: Priority queue, O(log n) insert/extract, O(1) peek
• Tree: Hierarchical structure, O(log n) balanced operations, BST properties
• Graph: Node-edge structure, BFS/DFS traversal in O(V+E)
• Big-O Notation: Analyzes time and space complexity
• Practical selection: Choosing the right structure determines algorithm efficiency

Core Components

1. Array: Index-based collection with direct access
2. Stack: LIFO structure for reversal and backtracking
3. Queue: FIFO structure for sequential processing
4. Heap: Priority-ordered tree structure
5. Tree: Hierarchical parent-child relationships
6. Graph: Network of connected vertices and edges
7. Performance: Big-O analysis of operations
8. Application: Matching problem requirements to structure

Practical Examples

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 Application

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) Application

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. Binary Search Tree vs Array Search

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 SearchTreeVsArray {
    public static void main(String[] args) {
        final int SIZE = 100_000;
        Random random = new Random();
        
        // Build BST
        BinarySearchTree 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 searchValue = random.nextInt(SIZE * 10);
        
        // BST search O(log n) on average
        long start = System.nanoTime();
        boolean bstFound = bst.search(searchValue);
        long bstTime = System.nanoTime() - start;
        
        // Array search O(n) worst-case
        start = System.nanoTime();
        boolean arrayFound = array.contains(searchValue);
        long arrayTime = System.nanoTime() - start;
        
        System.out.println("Searching for " + searchValue + ":");
        System.out.println("BST time: " + bstTime / 1000 + " μs, found: " + bstFound);
        System.out.println("Array time: " + arrayTime / 1000 + " μs, found: " + arrayFound);
        
        // Sorted array (Binary Search)
        Collections.sort(array);
        start = System.nanoTime();
        int index = Collections.binarySearch(array, searchValue);
        long binaryTime = System.nanoTime() - start;
        
        System.out.println("Binary search time: " + binaryTime / 1000 + " μs, index: " + index);
    }
}

5. Graph Traversal Comparison

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
    
    void addEdge(int u, int v) {
        adjacencyList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjacencyList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }
    
    // Breadth-First Search (Queue)
    void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        visited.add(start);
        
        System.out.print("BFS: ");
        while (!queue.isEmpty()) {
            int node = queue.remove();
            System.out.print(node + " ");
            
            for (int neighbor : adjacencyList.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        System.out.println();
    }
    
    // Depth-First Search (Stack/Recursion)
    void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsRecursive(start, visited);
    }
    
    private void dfsRecursive(int node, Set<Integer> visited) {
        visited.add(node);
        System.out.print(node + " ");
        
        for (int neighbor : adjacencyList.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited);
            }
        }
    }
}

public class GraphTraversal {
    public static void main(String[] args) {
        Graph graph = new Graph();
        
        // Build graph
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);
        
        System.out.println("Graph traversal:");
        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 Comparison Table

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	Note
Array	O(n)	Contiguous
Stack	O(n)	Dynamic
Queue	O(n)	Circular possible
Heap	O(n)	Tree structure
BST	O(n)	Node-based
Graph	O(V+E)	V=vertices, E=edges

Use Case Scenarios

When to use which data structure?

Use arrays when:

• Size is known and constant
• Random access is frequent
• Memory is tight (contiguous allocation)

Use stacks when:

• LIFO behavior is needed
• You need to backtrack through states
• Managing recursive function calls

Use queues when:

• FIFO behavior is needed
• Implementing waiting lines
• Running breadth-first search

Use heaps when:

• Priorities matter
• You frequently access minimum or maximum values
• Implementing scheduling algorithms

Use trees when:

• Storing ordered data
• Efficient searching is required
• Representing hierarchical relationships

Use graphs when:

• Modeling network relationships
• Planning routes
• Representing many-to-many connections

Performance Tips

Array Optimization

// Prepare loop variables
int[] array = new int[1000];
int length = array.length; // Don't recalculate each iteration

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

Stack Optimization

// Array instead of Stack for fixed size
int[] stack = new int[1000];
int top = -1;

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

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

Queue Optimization

// Circular queue for fixed size
int[] queue = new int[1000];
int front = 0, rear = 0;

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

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

Common Interview Questions

1. Which data structure for a printer queue? Queue (FIFO) — the first request is processed first.

2. Why is BST search faster than array search? BST: O(log n) through halving the search space; array: O(n) through linear scan.

3. What’s the difference between stack and queue? Stack: LIFO (Last-In, First-Out); queue: FIFO (First-In, First-Out).

4. When should you use a heap instead of an array? When you frequently need to access the minimum or maximum value (priority queue).

Key Resources

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