Estructuras de datos: Queue, Stack, Heap, Array, Árbol, Grafo – BFS, DFS, Complejidad

Este artículo es una aclaración de conceptos sobre estructuras de datos fundamentales, incluyendo preguntas de examen y referencias.

In a Nutshell

Array, Stack, Queue, Heap, Árbol y Grafo forman la base de algoritmos eficientes. Se diferencian en el comportamiento de acceso, memoria y tiempo de ejecución, y se emplean estratégicamente según el problema, el orden, las prioridades, las jerarquías y las redes.

Descripción técnica compacta

Arrays almacenan elementos en memoria contigua, ofrecen acceso O(1) por índice y sirven como base para muchas estructuras de nivel superior. Stack funciona bajo LIFO; push y pop son O(1) y resultan ideales para rastreo inverso, pilas de llamadas y parsers. Queue sigue FIFO; enqueue y dequeue son O(1), útiles para BFS o búferes. Heap aquí se refiere a Priority Queue con propiedad de heap, donde insert, extract min y extract max son O(log n), y peek es O(1). Los árboles estructuran datos jerárquicos; en variantes balanceadas, búsqueda, inserción y eliminación son O(log n). Los grafos modelan nodos y aristas; se representan mediante listas de adyacencia o matrices de adyacencia según la densidad.

Puntos clave relevantes para examen

• Conocer las complejidades: acceso a índice en Array O(1), push y pop en Stack O(1), enqueue y dequeue en Queue O(1), insert y extract en Heap O(log n), operaciones en árboles de búsqueda balanceados O(log n)
• Órdenes de recorrido: LIFO en Stack, FIFO en Queue, prioridad en Heap
• Recorridos: BFS con Queue, DFS con Stack, recursivo o iterativo
• Relevancia técnica: representación de grafos, listas de adyacencia vs matrices de adyacencia, grafos densos vs dispersos
• Aplicación práctica: scheduling con Priority Queue, pilas de deshacer, colas de mensajes, búsqueda de rutas en routers
• Aspecto de seguridad: validación de límites en Arrays, prevenir pop o dequeue en estructuras vacías, validación de prioridades
• Eficiencia económica: elegir la estructura correcta reduce tiempo de ejecución y consumo de memoria
• Obligación de documentación: justificar la elección de estructura de datos, invariantes, contratos de complejidad

Componentes principales

1. Array, capacidad, acceso por índice, contigüidad
2. Stack, push, pop, top, invariante LIFO
3. Queue, enqueue, dequeue, front, rear, invariante FIFO
4. Priority Queue, propiedad de heap, min heap, max heap
5. Nodos de árbol, padre, hijos, altura, profundidad
6. Balanceo, AVL, Rojo-Negro, B-Árbol para páginas de memoria
7. Nodos de grafo, aristas, grado, peso, dirección
8. Representación, lista de adyacencia, matriz de adyacencia
9. Recorrido, BFS, DFS, inorder, preorder, postorder
10. Invariantes y pruebas, ordenamiento de heap, ordenamiento de árbol de búsqueda, ausencia de ciclos en árboles

Ejemplo práctico

// 1. BFS sobre un grafo con lista de adyacencia, utiliza Queue
Queue<Node> q = new LinkedList<>()
Set<Node> seen = new HashSet<>()
q.add(start), seen.add(start)
while (!q.isEmpty()) {
Node u = q.remove()
visit(u)
for (Node v : adj[u]) {
if (!seen.contains(v)) { seen.add(v), q.add(v) }
}
}

// 2. Min Heap para selección de nodos en Dijkstra
PriorityQueue<State> pq = new PriorityQueue<>(byDistance)
pq.add(source)
while (!pq.isEmpty()) {
State s = pq.remove()
if (s.dist > best[s.node]) continue
relaxEdgesAndPushBetterStates(s, pq)
}

Explicación: BFS utiliza una Queue para recorrer nivel a nivel, mientras que Dijkstra usa Priority Queue para seleccionar el nodo más económico en cada paso.

Ventajas y desventajas

Array

• Acceso muy rápido por índice, compacto

• Tamaño fijo, inserciones costosas en mitad de la estructura

Stack

• Operaciones O(1) simples, ideal para rastreo inverso

• Acceso solo a la cima

Queue

• Orden estable, desacopla productores y consumidores

• Sin acceso directo a elementos intermedios

Heap

• Selección rápida de prioridades

• Sin iteración ordenada completa, solo la cima es eficiente

Árbol

• Datos ordenados con operaciones logarítmicas

• Complejidad del balanceo

Grafo

• Muy flexible, modela redes complejas

• Mayor complejidad de implementación y algoritmos

Preguntas típicas de examen (con respuesta breve)

1. ¿Lista de adyacencia vs. matriz de adyacencia? En grafos dispersos con pocas aristas, la lista de adyacencia usa O(n + m) memoria en lugar de O(n²) y permite iteración más rápida sobre vecinos.

2. ¿Orden en Stack y Queue? Stack LIFO (último en entrar, primero en salir), Queue FIFO (primero en entrar, primero en salir).

3. ¿Propiedad de heap? En un min heap, cada nodo es menor o igual a sus hijos, y la prioridad mínima se encuentra en la raíz.

4. ¿Complejidad de inserción y eliminación en min heap? O(log n) mediante sift up y sift down; peek es O(1).

5. ¿Por qué árboles de búsqueda balanceados logran O(log n)? La altura se mantiene proporcional a log n, lo que garantiza que las longitudes de ruta para búsqueda, inserción y eliminación sean logarítmicas.

6. ¿Cómo funciona BFS y para qué sirve? Recorre nivel a nivel usando una Queue, encuentra caminos más cortos en grafos sin pesos y es útil para análisis de accesibilidad.

7. ¿Cómo representar un árbol en memoria? Mediante nodos vinculados con referencias a hijos, o implícitamente en array para heaps, con indexación 2i y 2i+1.

8. ¿Priority Queue vs. lista ordenada? Insert y extract son O(log n) en lugar de O(n); peek sigue siendo O(1).

9. ¿Riesgos en acceso a Array? Out of bounds, errores off-by-one, falta de validación de límites, potencial brecha de seguridad.

10. ¿Cuándo es DFS mejor enfoque de recorrido? En ordenamiento topológico, detección de ciclos, búsqueda de componentes y cuando se exploran deliberadamente caminos profundos.

Fuentes más importantes

1. https://de.wikipedia.org/wiki/Datenstruktur
2. https://en.cppreference.com/w/cpp/container
3. https://docs.oracle.com/javase/tutorial/collections/