6 - Representación de una pila con listas enlazadas

Motivación del enfoque dinámico

Cuando el tamaño de la pila es impredecible o se desea evitar límites rigidos, una representación con listas enlazadas ofrece crecimiento bajo demanda. Cada push crea un nuevo nodo y cada pop lo libera, manteniendo la memoria ajustada al uso real.

6.1 Nodo struct Node

El nodo se define como un struct con dos campos: el valor almacenado y el puntero al siguiente nodo (el anterior en la pila). En C se acostumbra usar un alias para facilitar su reutilización.

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

Podemos reemplazar int por otro tipo o incluso por un void * si se busca generalizar la estructura.

6.2 Puntero al tope

La pila se modela con un puntero a Node que representa el tope. No se requiere un struct adicional, aunque es usual encapsularlo para agrupar funciones relacionadas.

typedef struct {
  Node *top;
} Stack;

Con esta definición, stack.top es el punto de entrada hacia todos los nodos. Si es NULL, la pila está vacía.

6.3 Inicialización de la pila

Inicializar una pila dinámica se reduce a asignar NULL al tope. A partir de allí las funciones push y pop se encargan de modificarlo.

void stack_init(Stack *stack) {
  stack->top = NULL;
}

Aunque parezca trivial, establecer el estado inicial evita comportamientos indefinidos y simplifica las comprobaciones de vacío.

6.4 Ventajas en memoria y tamaño dinámico

Las pilas basadas en nodos ofrecen beneficios claros:

• Memoria bajo demanda: solo se reserva lo necesario para cada elemento, sin bloques contiguos ni espacios ociosos.
• Tamaño ilimitado: el límite lo impone la memoria disponible del sistema, no una constante fija.
• Flexibilidad: se pueden enlazar estructuras complejas o transformar la pila en otras estructuras (colas, deques) con cambios menores.

Estas ventajas son valiosas en aplicaciones que procesan flujos desconocidos, como parsers, motores de expresiones o utilidades interactivos.

6.5 Precauciones con punteros

Trabajar con nodos requiere disciplina en el manejo de punteros:

• Validar siempre el resultado de malloc antes de usar el nodo.
• Actualizar el puntero top antes de liberar memoria para evitar perder referencias.
• Implementar una función de limpieza (stack_clear) que libere todos los nodos al final del programa.
• Evitar duplicar referencias a nodos sin una copia explícita; podría producir dobles liberaciones.

Código ejemplo para CLion

El siguiente snippet implementa una pila dinámica con operaciones básicas y una función de depuración:

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

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

typedef struct {
  Node *top;
} Stack;

void stack_init(Stack *stack) {
  stack->top = NULL;
}

int stack_is_empty(const Stack *stack) {
  return stack->top == NULL;
}

int stack_push(Stack *stack, int valor) {
  Node *nuevo = malloc(sizeof(Node));
  if (!nuevo) return 0;
  nuevo->valor = valor;
  nuevo->sig = stack->top;
  stack->top = nuevo;
  return 1;
}

int stack_pop(Stack *stack, int *out) {
  if (stack_is_empty(stack)) return 0;
  Node *tmp = stack->top;
  *out = tmp->valor;
  stack->top = tmp->sig;
  free(tmp);
  return 1;
}

int stack_peek(const Stack *stack, int *out) {
  if (stack_is_empty(stack)) return 0;
  *out = stack->top->valor;
  return 1;
}

void stack_print(const Stack *stack) {
  printf("Pila dinamica:\n");
  for (Node *n = stack->top; n; n = n->sig) {
    printf("  %d%s\n", n->valor, n == stack->top ? " <- top" : "");
  }
}

void stack_clear(Stack *stack) {
  Node *curr = stack->top;
  while (curr) {
    Node *tmp = curr;
    curr = curr->sig;
    free(tmp);
  }
  stack->top = NULL;
}

int main(void) {
  Stack stack;
  stack_init(&stack);

  stack_push(&stack, 5);
  stack_push(&stack, 15);
  stack_push(&stack, 25);
  stack_print(&stack);

  int peek;
  if (stack_peek(&stack, &peek)) {
    printf("Peek: %d\n", peek);
  }

  int valor;
  while (stack_pop(&stack, &valor)) {
    printf("Pop: %d\n", valor);
  }

  stack_clear(&stack);
  return 0;
}

Compilar este archivo en CLion produce una salida similar a la versión con arrays, pero con memoria dinámica. Siempre cierra con stack_clear para evitar fugas.