Data Structures Overview: Arrays, Stacks, Queues, Heaps, Trees & Graphs

This article provides a concise overview of 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 usage, and practical applications.

Core Concepts

Data structures organize information for fast access and processing. Every structure has distinct properties and optimal use cases.

Performance summary:

Array

Access: O(1) — direct lookup by index
Insert/Delete: O(n) — elements must be shifted
Memory: O(n) — contiguous block
Use case: Fixed size, frequent random access

Stack (LIFO)

Push/Pop: O(1) — only affects top element
Memory: O(n) — dynamic or static
Use case: Function calls, backtracking, parsing

Queue (FIFO)

Enqueue/Dequeue: O(1) — front and rear operations
Memory: O(n) — circular implementation possible
Use case: Buffering, BFS, task queues

Heap (Priority Queue)

Insert: O(log n) — maintains heap property
Extract Min/Max: O(log n) — remove root
Peek: O(1) — view minimum or maximum
Use case: Priority scheduling, sorting, event handling

Tree (BST)

Search: O(log n) — when balanced
Insert/Delete: O(log n) — when balanced
Memory: O(n) — node-based
Use case: Ordered data, database indexing

Graph

Traversal: O(V+E) — V=vertices, E=edges
Memory: O(V+E) — adjacency list representation
Use case: Networks, pathfinding, routing

Key Takeaways

Array: O(1) access, fixed size, contiguous memory
Stack: LIFO principle, O(1) push/pop, call stack
Queue: FIFO principle, O(1) enqueue/dequeue, buffering
Heap: Priority-based, O(log n) insert/extract, O(1) peek
Tree: Hierarchical structure, O(log n) when balanced, BST
Graph: Nodes and edges, BFS/DFS O(V+E)
Big-O Notation: Time and space complexity analysis
Practical skill: Choosing the right structure for the problem

Core Components

Array: Indexed collection with direct access
Stack: LIFO structure for backtracking scenarios
Queue: FIFO structure for sequential processing
Heap: Priority-based tree structure
Tree: Hierarchical parent-child relationships
Graph: Network of connected nodes
Performance: Big-O analysis of operations
Application: Selecting the right 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 SuchbaumVsArray {
    public static void main(String[] args) {
        final int GROESSE = 100_000;
        Random random = new Random();
        
        // Build BST
        BinarySearchTree 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) average case
        long start = System.nanoTime();
        boolean bstGefunden = bst.search(suchZahl);
        long bstZeit = System.nanoTime() - start;
        
        // Array search O(n) worst case
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("Searching for " + suchZahl + ":");
        System.out.println("BST time: " + bstZeit / 1000 + " μs, found: " + bstGefunden);
        System.out.println("Array time: " + arrayZeit / 1000 + " μs, found: " + arrayGefunden);
        
        // Sorted 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 time: " + binaryZeit / 1000 + " μs, index: " + index);
    }
}

5. Graph Traversal Comparison

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/Recursion)
    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();
        
        // Build graph
        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 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	Space	Remark
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

Choosing the right data structure

Use arrays when:

Size is known and constant
Random access is needed frequently
Memory space is critical (contiguous allocation)

Use stacks when:

LIFO behavior is required
Backtracking through states
Managing recursive function calls

Use queues when:

FIFO behavior is required
Implementing waiting lines
Breadth-First Search traversal

Use heaps when:

Priority ordering matters
Frequent access to minimum or maximum values
Implementing scheduling algorithms

Use trees when:

Storing ordered data
Efficient searching is needed
Modeling hierarchical relationships

Use graphs when:

Modeling network relationships
Path planning is involved
Many-to-many relationships exist

Performance Tips

Array optimization

// Prepare loop
int[] array = new int[1000];
int laenge = array.length; // Don't fetch on each iteration

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

Stack optimization

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

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

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 wert) {
    queue[rear = (rear + 1) % queue.length] = wert;
}

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

Common Interview Questions

Which data structure for a printer queue? Queue (FIFO) – the first request is processed first.
Why is BST search faster than array search? BST: O(log n) through halving; array: O(n) through linear search.
What’s the difference between a stack and a queue? Stack: LIFO (Last-In, First-Out); queue: FIFO (First-In, First-Out).
When should you use a heap instead of an array? When frequent access to minimum or maximum values is required (Priority Queue).

Täglicher Artikel

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

Data Structures Overview: Arrays, Stacks, Queues, Heaps, Trees & Graphs

In a Nutshell

Core Concepts

Array

Stack (LIFO)

Queue (FIFO)

Heap (Priority Queue)

Tree (BST)

Graph

Key Takeaways

Core Components

Practical Examples

1. Array vs ArrayList Performance

2. Stack vs Queue Application

3. Priority Queue (Heap) Application

4. Binary Search Tree vs Array Search

5. Graph Traversal Comparison

Big-O Notation Comparison Table

Time Complexity

Space Complexity

Use Case Scenarios

Choosing the right data structure

Performance Tips

Array optimization

Stack optimization

Queue optimization

Common Interview Questions

Key Resources

Nächster Artikel in Algorithms

Related Posts

Data Structures Overview: Arrays, Stacks, Queues, Heaps & Graphs

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

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

Täglicher Artikel

Data Structures Overview: Arrays, Stacks, Queues, Heaps, Trees & Graphs

IRC-Mania Die Seite rund um Sicherheit und Programmierung

In a Nutshell

Core Concepts

Array

Stack (LIFO)

Queue (FIFO)

Heap (Priority Queue)

Tree (BST)

Graph

Key Takeaways

Core Components

Practical Examples

1. Array vs ArrayList Performance

2. Stack vs Queue Application

3. Priority Queue (Heap) Application

4. Binary Search Tree vs Array Search

5. Graph Traversal Comparison

IRC-Security.de

Big-O Notation Comparison Table

Time Complexity

Space Complexity

Use Case Scenarios

Choosing the right data structure

Performance Tips

Array optimization

Stack optimization

Queue optimization

Common Interview Questions

Key Resources

Premium VPS Hosting

Nächster Artikel in Algorithms

Related Posts

Data Structures Overview: Arrays, Stacks, Queues, Heaps & Graphs

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

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