10 - Comparación entre estructuras

10.1 Objetivo de la comparación

Reunimos en una sola vista las variantes de colas estudiadas (lineal, circular, listas enlazadas, deque, prioridad y heap) para facilitar la elección según las restricciones de memoria, complejidad y concurrencia. Cada estructura nace de un compromiso distinto entre simplicidad y flexibilidad.

10.2 Resumen comparativo

Estructura	Complejidad encolado/desencolado	Memoria	Ventajas clave	Limitaciones
Cola lineal (array)	O(1) / O(1)	Tamaño fijo	Implementación simple, buena localidad de caché	Falsa saturación sin manejo circular
Cola circular	O(1) / O(1)	Tamaño fijo	Reutiliza espacios liberados	Requiere contador o casillero extra
Cola con lista enlazada	O(1) / O(1)	Dinámica	Capacidad elástica	Coste adicional de referencias y nodos
Deque	O(1) en ambos extremos	Fija o dinámica	Opera como pila o cola	Mayor complejidad de interfaz
Cola de prioridad (heap)	O(log n) / O(log n)	Fija o dinámica	Extrae el máximo/mínimo en O(1)	Implementación más extensa

10.3 Criterios de selección

• Tamaño del flujo: cargas altas o impredecibles favorecen listas o heaps dinámicos.
• Determinismo: arrays permiten calcular límites estrictos; utilizados en sistemas embebidos.
• Necesidad de doble extremo: usar deque evita duplicar código de pila y cola.
• Ordenación por prioridad: la única opción eficiente es la cola de prioridad/heap.

10.4 Costos de memoria y cache

Las listas ofrecen mayor elasticidad a costa de referencias adicionales. Las estructuras basadas en arrays (incluyendo deque y heapq) brindan densidad y buena localidad, pero requieren definir o crecer la capacidad según el uso.

10.5 Concurrencia y sincronización

Colas lineales y circulares se benefician de mecanismos lock-free sencillos. Las listas enlazadas exigen protección más estricta para evitar que dos hilos toquen el mismo nodo. Las colas de prioridad necesitan regiones críticas que abarcan toda la operación de reorganización del heap para evitar estados inconsistentes.

10.6 Escenarios de aplicación

• Buffer de red: cola circular con tamaño fijo para garantizar latencia acotada.
• Procesamiento de eventos: cola enlazada para manejar picos sin desperdiciar memoria.
• Planificador Round Robin: deque o cola circular con reasignación constante.
• Ruteo o Dijkstra: cola de prioridad respaldada por heap para seleccionar el próximo camino más corto.

10.7 Checklist rápido

Responde estas preguntas antes de elegir:

1. ¿El flujo es ILIMITADO? Usa listas o heaps que puedan crecer.
2. ¿Necesitas atender al elemento más urgente? Implementa una cola de prioridad.
3. ¿Debes insertar/eliminar por ambos extremos? Escoge un deque.
4. ¿Existen restricciones duras de memoria? Un array fijo simplifica y evita fragmentación.