8 - Comparativa entre pilas con arrays y pilas con listas

Contexto

Elegir entre un array o una lista enlazada para implementar una pila depende de requerimientos concretos. A continuación se contrastan ambos enfoques para facilitar la decisión en proyectos reales.

8.1 Velocidad

Las pilas basadas en arrays aprovechan memoria contigua, lo que mejora el rendimiento en caches. Las operaciones push y pop son O(1) y no requieren asignaciones dinámicas salvo cuando se utiliza realloc.

Las pilas con listas dependen de malloc/free en cada operación, lo que introduce una sobrecarga mayor. Sin embargo, cuando el sistema usa un buen administrador de memoria o se inserta a través de pools, la diferencia se reduce.

8.2 Uso de memoria

• Arrays: reservan un bloque completo de memoria, lo que puede implicar espacio ocioso si la pila no se llena. Son ideales cuando el tamaño máximo es conocido y limitado.
• Listas: reservan nodo a nodo. No desperdician memoria pero agregan overhead por punteros en cada elemento y fragmentan el heap.

8.3 Complejidad temporal

En ambos casos, las operaciones básicas presentan complejidad O(1). La diferencia aparece en operaciones secundarias:

Operación	Pila con arrays	Pila con listas
push/pop	O(1)	O(1)
Redimensionar	O(n) al duplicar capacidad	No aplica
Limpieza completa	O(n) si se necesita poner a cero	O(n) liberando nodo por nodo

8.4 Situaciones recomendadas para cada tipo

• Arrays: entornos embebidos, funciones con límites claros, validación de expresiones de tamaño acotado y estructuras internas donde la velocidad constante es prioritaria.
• Listas: sistemas que procesan entradas imprevisibles, evaluadores interactivos, motores de backtracking y herramientas que requieren alterar el límite de la pila sin recompilar.
• En aplicaciones híbridas se puede iniciar con arrays y migrar a listas cuando el crecimiento supera el tamaño esperado.

8.5 Errores comunes en cada implementación

• Arrays: olvidar verificar isFull y provocar overflow; confundir el orden de incremento/decremento de top; utilizar realloc sin respaldar el puntero previo.
• Listas: no liberar los nodos desapilados; perder la referencia al tope antes de actualizarla; reutilizar nodos sin reinicializar sus punteros.
• En ambos casos: no documentar el contrato de la pila, mezclar responsabilidades de memoria y lógica, o no cubrir los edge cases en pruebas.

Conocer estas diferencias ayuda a seleccionar la representación correcta desde el inicio o a migrar a la alternativa adecuada cuando cambian los requisitos.