Resumen de Estructuras de Datos: Array, Stack, Queue, Heap, Árbol y Grafo

Este artículo ofrece una descripción compacta de las estructuras de datos más importantes, con análisis de rendimiento, casos de uso y notación Big-O.

En pocas palabras

Las estructuras de datos fundamentales como Array, Stack, Queue, Heap, Árbol y Grafo constituyen la base de algoritmos eficientes. Cada una se diferencia en tiempo de acceso, consumo de memoria y áreas de aplicación.

Descripción técnica compacta

Las estructuras de datos organizan la información para permitir acceso y procesamiento eficientes. Cada estructura tiene propiedades específicas y campos de aplicación óptimos.

Resumen de rendimiento:

Array

• Acceso: O(1) - Directo por índice
• Inserción/Eliminación: O(n) - Requiere desplazamiento de elementos
• Memoria: O(n) - Almacenamiento contiguo
• Uso: Tamaño fijo, acceso aleatorio frecuente

Stack (LIFO)

• Push/Pop: O(1) - Solo el elemento superior
• Memoria: O(n) - Dinámico o fijo
• Uso: Llamadas a funciones, backtracking, analizadores sintácticos

Queue (FIFO)

• Enqueue/Dequeue: O(1) - Frente/Final
• Memoria: O(n) - Queue circular posible
• Uso: Colas de espera, BFS, buffers

Heap (Priority Queue)

• Insert: O(log n) - Mantiene la propiedad del heap
• Extract Min/Max: O(log n) - Elimina la raíz
• Peek: O(1) - Observa mínimo/máximo
• Uso: Prioridades, scheduling, Heap Sort

Árbol (BST)

• Búsqueda: O(log n) - Balanceado
• Inserción/Eliminación: O(log n) - Balanceado
• Memoria: O(n) - Basado en nodos
• Uso: Datos ordenados, bases de datos

Grafo

• Recorrido: O(V+E) - V=nodos, E=aristas
• Memoria: O(V+E) - Lista de adyacencia
• Uso: Redes, planificación de rutas

Puntos clave para evaluación

• Array: Acceso O(1), tamaño fijo, memoria contigua
• Stack: Principio LIFO, push/pop O(1), Call Stack
• Queue: Principio FIFO, enqueue/dequeue O(1), buffer
• Heap: Priority Queue, insert/extract O(log n), peek O(1)
• Árbol: Jerárquico, O(log n) con balanceo, BST
• Grafo: Estructura nodo-arista, BFS/DFS O(V+E)
• Notación Big-O: Complejidad temporal y espacial
• Relevancia profesional: Fundamento para algoritmos y eficiencia

Componentes clave

1. Array: Colección indexada con acceso directo
2. Stack: Estructura LIFO para retroceso
3. Queue: Estructura FIFO para colas de espera
4. Heap: Estructura de árbol basada en prioridades
5. Árbol: Relaciones jerárquicas padre-hijo
6. Grafo: Red de nodos y aristas
7. Rendimiento: Análisis Big-O de operaciones
8. Aplicación: Selección óptima de estructura

Ejemplos prácticos

1. Rendimiento de Array vs ArrayList

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. Aplicación de Stack vs Queue

import java.util.*;

public class StackQueueDemo {
    public static void main(String[] args) {
        // Stack para validación de paréntesis (LIFO)
        String ausdruck = "{[()()]}";
        if (pruefeKlammer(ausdruck)) {
            System.out.println("Ausdruck '" + ausdruck + "' ist gültig");
        }
        
        // Queue para cola de impresión (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);
        }
        
        // Comparación de rendimiento
        performanceVergleich();
    }
    
    // Validación de paréntesis con 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;
        
        // Rendimiento de Stack
        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;
        
        // Rendimiento de Queue
        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("\nComparación de rendimiento (" + OPERATIONEN + " operaciones):");
        System.out.println("Stack Zeit: " + stackZeit / 1_000_000 + " ms");
        System.out.println("Queue Zeit: " + queueZeit / 1_000_000 + " ms");
    }
}

3. Aplicación de Priority Queue (Heap)

import java.util.*;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // Min-Heap para ordenamiento ascendente
        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 con 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());
        }
        
        // Scheduling de tareas con prioridades
        taskSchedulingDemo();
    }
    
    private static void taskSchedulingDemo() {
        // Tarea con prioridad
        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 para tareas
        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. Árbol de búsqueda vs búsqueda en array

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();
        
        // BST aufbauen
        BinarySearchTree bst = new BinarySearchTree();
        for (int i = 0; i < GROESSE; i++) {
            bst.insert(random.nextInt(GROESSE * 10));
        }
        
        // Array erstellen
        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 Suche O(log n) im Durchschnitt
        long start = System.nanoTime();
        boolean bstGefunden = bst.search(suchZahl);
        long bstZeit = System.nanoTime() - start;
        
        // Array Suche O(n) im Worst-Case
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("Suche nach " + suchZahl + ":");
        System.out.println("BST Zeit: " + bstZeit / 1000 + " μs, gefunden: " + bstGefunden);
        System.out.println("Array Zeit: " + arrayZeit / 1000 + " μs, gefunden: " + arrayGefunden);
        
        // Sortierter 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 Zeit: " + binaryZeit / 1000 + " μs, Index: " + index);
    }
}

5. Comparación de recorrido de grafos

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/Rekursion)
    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();
        
        // Graph aufbauen
        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 Traversierung:");
        graph.bfs(0); // Level-order: 0 1 2 3 4 5
        graph.dfs(0); // Depth-first: 0 1 3 4 2 5
    }
}

Tabla de comparación Big-O

Complejidad temporal

Operación	Array	Stack	Queue	Heap	BST	Graph
Acceso	O(1)	O(n)	O(n)	O(1)	O(log n)	O(V+E)
Búsqueda	O(n)	O(n)	O(n)	O(n)	O(log n)	O(V+E)
Inserción	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(1)
Eliminación	O(n)	O(1)	O(1)	O(log n)	O(log n)	O(V+E)

Complejidad de espacio

Estructura de datos	Espacio	Observación
Array	O(n)	Contiguo
Stack	O(n)	Dinámico
Queue	O(n)	Circular posible
Heap	O(n)	Estructura de árbol
BST	O(n)	Basado en nodos
Graph	O(V+E)	V=nodos, E=aristas

Escenarios de aplicación

Cuándo usar cada estructura de datos

Usa Array cuando:

• El tamaño es conocido y constante
• Necesitas acceso aleatorio frecuente
• El espacio contiguo es crítico

Usa Stack cuando:

• Necesitas comportamiento LIFO
• Requieres rastrear el estado o deshacer operaciones
• Trabajas con llamadas recursivas de funciones

Usa Queue cuando:

• Necesitas comportamiento FIFO
• Implementas colas de espera
• Ejecutas búsqueda en anchura

Usa Heap cuando:

• Las prioridades son importantes
• Accedes frecuentemente a mínimo o máximo
• Implementas algoritmos de planificación

Usa Árbol cuando:

• Almacenas datos ordenados
• Requieres búsqueda eficiente
• Modelar relaciones jerárquicas

Usa Graph cuando:

• Modelar relaciones de red
• Realizar planificación de rutas
• Representar relaciones de muchos a muchos

Consejos de rendimiento

Optimización de arrays

// Preparar el bucle
int[] array = new int[1000];
int laenge = array.length; // No en cada iteración

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

Optimización de stacks

// Usar array en lugar de Stack para tamaño fijo
int[] stack = new int[1000];
int top = -1;

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

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

Optimización de queues

// Cola circular para tamaño fijo
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];
}

Preguntas frecuentes de entrevista

1. ¿Qué estructura para una cola de impresora? Queue (FIFO), la primera solicitud se procesa primero.

2. ¿Por qué la búsqueda en BST es más rápida que en array? BST: O(log n) por división iterativa, array: O(n) por búsqueda lineal.

3. ¿Cuál es la diferencia entre stack y queue? Stack: LIFO (Last-In, First-Out), Queue: FIFO (First-In, First-Out).

4. ¿Cuándo usar heap en lugar de array? Cuando necesitas acceso frecuente a mínimo o máximo (Priority Queue).

Principales fuentes

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