Estructuras de datos: Stack, Queue, Heap, Array, Árbol, Grafo y Algoritmos

Este artículo es una descripción exhaustiva de las estructuras de datos más importantes, incluyendo análisis de complejidad, ejemplos prácticos y algoritmos.

En resumen

Las estructuras de datos son métodos para organizar y almacenar información de manera que se pueda acceder y modificar de forma eficiente. Elegir la estructura correcta es fundamental para lograr una buena eficiencia en el programa.

Descripción técnica compacta

Las estructuras de datos son componentes fundamentales del desarrollo de software que definen cómo se organiza y gestiona la información. Cada estructura tiene propiedades y casos de uso específicos.

Estructuras de datos importantes:

1. Array

• Descripción: Secuencia contigua y de tamaño fijo de elementos del mismo tipo
• Acceso: Directo por índice (O(1))
• Desventajas: Tamaño fijo, inserción y eliminación costosas (O(n))

2. Stack (LIFO)

• Principio: Last-In, First-Out (último en entrar, primero en salir)
• Operaciones: push() (agregar al tope), pop() (extraer del tope)
• Usos: Llamadas a funciones, backtracking, analizadores sintácticos

3. Queue (FIFO)

• Principio: First-In, First-Out (primero en entrar, primero en salir)
• Operaciones: enqueue() (agregar al final), dequeue() (extraer del inicio)
• Usos: Cola de impresión, búsqueda por amplitud

4. Heap

• Descripción: Árbol binario con propiedad de heap
• Tipos: Min-Heap, Max-Heap
• Usos: Colas de prioridad, Heap Sort

5. Árbol

• Descripción: Estructura de datos jerárquica
• Tipos: Árbol binario, ABB, AVL, Árbol B
• Usos: Algoritmos de búsqueda, bases de datos

6. Grafo

• Descripción: Nodos y aristas
• Tipos: Dirigido o no dirigido, ponderado o sin peso
• Usos: Redes, planificación de rutas

Puntos clave

• Array: Acceso directo O(1), tamaño fijo
• Stack: Principio LIFO, operaciones push/pop
• Queue: Principio FIFO, operaciones enqueue/dequeue
• Heap: Min/Max-Heap, colas de prioridad
• Árbol: Estructura jerárquica, ABB, balanceo
• Grafo: Estructura de nodos y aristas, algoritmos de recorrido
• Notación Big-O: Complejidad temporal y espacial
• Relevancia práctica: Fundamental para algoritmos y eficiencia

Componentes principales

1. Array: Colección indexada de tamaño fijo
2. Stack: Estructura LIFO con push/pop
3. Queue: Estructura FIFO con enqueue/dequeue
4. Heap: Estructura de árbol basada en prioridades
5. Árbol: Relaciones jerárquicas padre-hijo
6. Grafo: Red de nodos conectados por aristas
7. Complejidad: Análisis Big-O de operaciones
8. Algoritmos: Búsqueda, ordenamiento, recorrido

Ejemplos prácticos

1. Array y ArrayList en Java

import java.util.*;

public class ArrayDemo {
    public static void main(String[] args) {
        // Array simple (tamaño fijo)
        int[] zahlen = new int[5];
        zahlen[0] = 10;
        zahlen[1] = 20;
        zahlen[2] = 30;
        zahlen[3] = 40;
        zahlen[4] = 50;
        
        // Acceso directo O(1)
        System.out.println("Element bei Index 2: " + zahlen[2]);
        
        // Búsqueda lineal 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 von " + gesucht + ": " + index);
        
        // ArrayList (tamaño dinámico)
        List<String> namen = new ArrayList<>();
        namen.add("Alice");  // O(1) amortizado
        namen.add("Bob");    // O(1) amortizado
        namen.add("Charlie"); // O(1) amortizado
        
        // Inserción en el medio O(n)
        namen.add(1, "David"); // Desplaza todos los elementos hacia la derecha
        
        System.out.println("ArrayList: " + namen);
        
        // Comparación de rendimiento Array vs ArrayList
        performanceVergleich();
    }
    
    private static void performanceVergleich() {
        final int GROESSE = 100000;
        
        // Rendimiento Array
        long start = System.nanoTime();
        int[] array = new int[GROESSE];
        for (int i = 0; i < GROESSE; i++) {
            array[i] = i;
        }
        long arrayZeit = System.nanoTime() - start;
        
        // Rendimiento ArrayList
        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 Zeit: " + arrayZeit / 1_000_000 + " ms");
        System.out.println("ArrayList Zeit: " + arrayListZeit / 1_000_000 + " ms");
    }
}

2. Implementación y uso de Stack

import java.util.*;

// Implementación de Stack con 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 ist voll");
        }
        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;
    }
}

// Uso de Stack
public class StackDemo {
    public static void main(String[] args) {
        // Clase Stack de Java
        Stack<String> stack = new Stack<>();
        
        // Operaciones push
        stack.push("Erstes");
        stack.push("Zweites");
        stack.push("Drittes");
        
        System.out.println("Stack: " + stack);
        System.out.println("Top Element: " + stack.peek());
        
        // Operaciones pop
        while (!stack.isEmpty()) {
            String element = stack.pop();
            System.out.println("Pop: " + element);
        }
        
        // Usar Stack personalizado
        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());
        }
        
        // Aplicación práctica: validación de paréntesis
        String ausdruck = "{[()]}";
        System.out.println("Ausdruck '" + ausdruck + "' ist gültig: " + 
                          pruefeKlammer(ausdruck));
    }
    
    // Validación de paréntesis con 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. Implementación y aplicación de colas

import java.util.*;

// Implementación de cola con 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;
    }
}

// Aplicación de colas
public class QueueDemo {
    public static void main(String[] args) {
        // Interfaz Queue de Java con LinkedList
        Queue<String> queue = new LinkedList<>();
        
        // Operaciones de enqueue
        queue.add("Cliente 1");
        queue.add("Cliente 2");
        queue.add("Cliente 3");
        
        System.out.println("Cola: " + queue);
        
        // Operaciones de dequeue
        while (!queue.isEmpty()) {
            String cliente = queue.remove();
            System.out.println("Atendido: " + cliente);
        }
        
        // Priority Queue
        PriorityQueue<Integer> pqueue = new PriorityQueue<>();
        pqueue.add(30);
        pqueue.add(10);
        pqueue.add(20);
        pqueue.add(40);
        
        System.out.println("\nPriority Queue (ordenamiento natural):");
        while (!pqueue.isEmpty()) {
            System.out.println("Elemento: " + pqueue.remove());
        }
        
        // Usar cola personalizada
        ArrayQueue<String> warteschlange = new ArrayQueue<>(3);
        warteschlange.enqueue("Tarea A");
        warteschlange.enqueue("Tarea B");
        warteschlange.enqueue("Tarea C");
        
        System.out.println("\nCola personalizada:");
        while (!warteschlange.isEmpty()) {
            System.out.println("Procesando: " + warteschlange.dequeue());
        }
    }
}

4. Heap y Priority Queue

import java.util.*;

// Implementación de Min-Heap
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;
            
            // Intercambiar
            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();
    }
}

// Aplicación de Heap
public class HeapDemo {
    public static void main(String[] args) {
        // Priority Queue de Java (Min-Heap)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(40);
        
        System.out.println("Min-Heap con Priority Queue:");
        while (!minHeap.isEmpty()) {
            System.out.println("Mín: " + 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);
        
        System.out.println("\nMax-Heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println("Máx: " + maxHeap.remove());
        }
        
        // Min-Heap personalizado
        MinHeap meinHeap = new MinHeap();
        meinHeap.insert(30);
        meinHeap.insert(10);
        meinHeap.insert(20);
        meinHeap.insert(40);
        
        System.out.println("\nMin-Heap personalizado:");
        while (!meinHeap.isEmpty()) {
            System.out.println("Mín: " + meinHeap.extractMin());
        }
        
        // Demostración de Heap Sort
        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 para 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("Ordenado: " + Arrays.toString(sortiert));
    }
}

5. Árbol binario y BST

import java.util.*;

// Nodo de árbol binario
class TreeNode<T> {
    T wert;
    TreeNode<T> links;
    TreeNode<T> rechts;
    
    public TreeNode(T wert) {
        this.wert = wert;
        this.links = null;
        this.rechts = null;
    }
}

// Árbol de búsqueda binaria
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 + " ");
        }
    }
}

// Aplicación de BST
public class BaumDemo {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        
        // Insertar elementos
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);
        
        System.out.println("Recorrido In-Order (ordenado):");
        bst.inorder(); // 20 30 40 50 60 70 80
        
        System.out.println("Recorrido Pre-Order:");
        bst.preorder(); // 50 30 20 40 70 60 80
        
        System.out.println("Recorrido Post-Order:");
        bst.postorder(); // 20 40 30 60 80 70 50
        
        // Buscar
        System.out.println("Buscar 40: " + bst.search(40)); // true
        System.out.println("Buscar 25: " + bst.search(25)); // false
        
        // Comparación de desempeño BST vs Array
        performanceVergleich();
    }
    
    private static void performanceVergleich() {
        final int GROESSE = 10000;
        Random random = new Random();
        
        // Crear BST
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < GROESSE; i++) {
            bst.insert(random.nextInt(GROESSE * 10));
        }
        
        // Crear 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);
        
        // Búsqueda en BST O(log n) en promedio
        long start = System.nanoTime();
        boolean bstGefunden = bst.search(suchZahl);
        long bstZeit = System.nanoTime() - start;
        
        // Búsqueda en array O(n)
        start = System.nanoTime();
        boolean arrayGefunden = array.contains(suchZahl);
        long arrayZeit = System.nanoTime() - start;
        
        System.out.println("\nComparación de desempeño:");
        System.out.println("Búsqueda en BST: " + bstZeit / 1000 + " μs, encontrado: " + bstGefunden);
        System.out.println("Búsqueda en array: " + arrayZeit / 1000 + " μs, encontrado: " + arrayGefunden);
    }
}

Notación Big-O: Overview

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 Espacial

Estructura	Memoria
Array	O(n)
Stack	O(n)
Queue	O(n)
Heap	O(n)
BST	O(n)
Graph	O(V+E)

Algoritmos de Grafos

Implementación de Grafos

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adyacencia;
    
    public Graph() {
        this.adyacencia = new HashMap<>();
    }
    
    public void agregarArista(int u, int v) {
        adyacencia.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adyacencia.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // No dirigido
    }
    
    // Breadth-First Search (BFS)
    public void bfs(int inicio) {
        Set<Integer> visitados = new HashSet<>();
        Queue<Integer> cola = new LinkedList<>();
        
        cola.add(inicio);
        visitados.add(inicio);
        
        while (!cola.isEmpty()) {
            int nodo = cola.remove();
            System.out.print(nodo + " ");
            
            for (int vecino : adyacencia.getOrDefault(nodo, Collections.emptyList())) {
                if (!visitados.contains(vecino)) {
                    visitados.add(vecino);
                    cola.add(vecino);
                }
            }
        }
        System.out.println();
    }
    
    // Depth-First Search (DFS)
    public void dfs(int inicio) {
        Set<Integer> visitados = new HashSet<>();
        dfsRecursivo(inicio, visitados);
        System.out.println();
    }
    
    private void dfsRecursivo(int nodo, Set<Integer> visitados) {
        visitados.add(nodo);
        System.out.print(nodo + " ");
        
        for (int vecino : adyacencia.getOrDefault(nodo, Collections.emptyList())) {
            if (!visitados.contains(vecino)) {
                dfsRecursivo(vecino, visitados);
            }
        }
    }
}

// Aplicación de Grafo
public class GraphDemo {
    public static void main(String[] args) {
        Graph grafo = new Graph();
        
        // Agregar aristas
        grafo.agregarArista(0, 1);
        grafo.agregarArista(0, 2);
        grafo.agregarArista(1, 3);
        grafo.agregarArista(2, 4);
        grafo.agregarArista(3, 4);
        grafo.agregarArista(4, 5);
        
        System.out.println("BFS desde nodo 0:");
        grafo.bfs(0); // 0 1 2 3 4 5
        
        System.out.println("DFS desde nodo 0:");
        grafo.dfs(0); // 0 1 3 4 2 5
    }
}

Ventajas y Desventajas

Array

• Ventajas: Acceso directo O(1), implementación simple
• Desventajas: Tamaño fijo, inserción/eliminación O(n)

Stack

• Ventajas: Lógica LIFO simple, operaciones push/pop en O(1)
• Desventajas: Solo acceso al elemento superior

Queue

• Ventajas: Lógica FIFO, equitativa para colas de espera
• Desventajas: Inserción al final puede ser costosa

Heap

• Ventajas: Acceso a mínimo/máximo en O(1)
• Desventajas: Implementación más compleja

Árbol

• Ventajas: Búsqueda eficiente O(log n), datos ordenados
• Desventajas: Requiere balanceo

Grafo

• Ventajas: Relaciones flexibles, modelado realista
• Desventajas: Algoritmos complejos, mayor uso de memoria

Preguntas Típicas de Entrevista

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

2. Explica la notación Big-O para la búsqueda en arrays. Búsqueda lineal O(n) en el peor caso, acceso directo O(1).

3. ¿Cuándo usas Heap en lugar de Array? Cuando necesitas acceder frecuentemente al mínimo o máximo (Priority Queue).

4. ¿Cuál es la diferencia entre BFS y DFS? BFS: recorrido por niveles usando una cola, DFS: recorrido en profundidad usando pila o recursión.

Referencias Principales

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