3 - Tipos de implementación de pilas

Panorama general

El comportamiento LIFO se puede materializar con distintas estructuras internas. La elección depende de si buscamos límites claros, eficiencia en memoria o flexibilidad absoluta. En C las dos familias principales son basadas en arrays y basadas en listas enlazadas.

3.1 Implementación con arrays (estática o dinámica)

Utiliza un bloque contiguo para almacenar los elementos y un índice que representa el tope. Puede ser:

• Estática: define la capacidad como una constante y aloja los datos en el stack o en una variable global.
• Dinámica: aloja el array en el heap y aumenta la capacidad con realloc cuando se llena.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int *datos;
  int tope;
  int capacidad;
} PilaArray;

PilaArray *crear_pila_array(int capacidad_inicial) {
  PilaArray *p = malloc(sizeof(PilaArray));
  if (!p) return NULL;
  p->datos = malloc(sizeof(int) * capacidad_inicial);
  if (!p->datos) { free(p); return NULL; }
  p->capacidad = capacidad_inicial;
  p->tope = 0;
  return p;
}

void push_array(PilaArray *p, int valor) {
  if (p->tope == p->capacidad) {
    int nueva_cap = p->capacidad * 2;
    int *tmp = realloc(p->datos, sizeof(int) * nueva_cap);
    if (!tmp) return;
    p->datos = tmp;
    p->capacidad = nueva_cap;
  }
  p->datos[p->tope++] = valor;
}

int pop_array(PilaArray *p) {
  if (p->tope == 0) return -1;
  return p->datos[--p->tope];
}

int main(void) {
  PilaArray *p = crear_pila_array(2);
  push_array(p, 4);
  push_array(p, 7);
  push_array(p, 9);
  printf("Pop: %d\n", pop_array(p));
  printf("Pop: %d\n", pop_array(p));
  free(p->datos);
  free(p);
  return 0;
}

La estrategia estática elimina la necesidad de malloc, mientras que la dinámica permite crecer bajo demanda.

3.2 Implementación con listas enlazadas

En lugar de arrays, se reservan nodos individuales que se conectan mediante punteros. Cada push crea un nodo y lo enlaza al tope.

#include <stdio.h>
#include <stdlib.h>

typedef struct Nodo {
  int valor;
  struct Nodo *sig;
} Nodo;

typedef struct {
  Nodo *tope;
} PilaNodos;

void push_nodo(PilaNodos *p, int valor) {
  Nodo *nuevo = malloc(sizeof(Nodo));
  if (!nuevo) return;
  nuevo->valor = valor;
  nuevo->sig = p->tope;
  p->tope = nuevo;
}

int pop_nodo(PilaNodos *p) {
  if (!p->tope) return -1;
  Nodo *tmp = p->tope;
  int valor = tmp->valor;
  p->tope = tmp->sig;
  free(tmp);
  return valor;
}

int main(void) {
  PilaNodos pila = { .tope = NULL };
  push_nodo(&pila, 1);
  push_nodo(&pila, 2);
  push_nodo(&pila, 3);
  printf("Pop: %d\n", pop_nodo(&pila));
  printf("Pop: %d\n", pop_nodo(&pila));
  printf("Pop: %d\n", pop_nodo(&pila));
  return 0;
}

Esta técnica no impone una capacidad fija y libera memoria a medida que se desapila.

3.3 Diferencias entre ambas

3.4 Ventajas y desventajas prácticas

• Arrays: excelente rendimiento por localidad, simples de depurar; limitados por una capacidad predefinida o por el tiempo que requiere copiar datos al crecer.
• Listas enlazadas: flexibles y sin desperdicio de memoria cuando los datos fluctúan; requieren cuidar fugas de memoria y tienden a fragmentar el heap.
• Elección: aplicaciones embebidas o con tamaño máximo conocido prefieren arrays; herramientas interactivas, parsers o estructuras auxiliares que crecen según entrada tienden a usar nodos.

Conocer ambas alternativas permite ajustar la pila a las restricciones reales del proyecto y cambiar de estrategia sin reescribir la interfaz pública.