6 - Colas con listas enlazadas

6.1 Cuándo elegir una lista enlazada

Las colas basadas en listas enlazadas mantienen el modelo FIFO sin depender de un tamaño fijo de arreglo. Crecen y se encogen en función del número real de elementos, lo que evita reservar memoria ociosa.

• Capacidad elástica: ideal cuando la tasa de llegadas es impredecible o el pico supera a una cola estática.
• Inserciones O(1): solo se modifica el puntero final, sin necesidad de desplazar datos.
• Consumo proporcional: cada nodo existe mientras contenga un dato, lo que facilita liberar memoria tempranamente.

Su costo principal es la sobrecarga de punteros y la necesidad de comprobar cada malloc/free, por lo que conviene encapsular la gestión de memoria en funciones pequeñas.

6.2 Nodo y estructura base

Un nodo almacena el valor y un enlace al siguiente. La cola mantiene punteros a frente y final para operar en tiempo constante:

typedef struct Nodo {
  int dato;
  struct Nodo *siguiente;
} Nodo;

typedef struct {
  Nodo *frente;
  Nodo *final;
  int cantidad;
} ColaLista;

void inicializar(ColaLista *cola) {
  cola->frente = NULL;
  cola->final = NULL;
  cola->cantidad = 0;
}

Al iniciar, ambos punteros deben apuntar a NULL para indicar que la cola está vacía.

6.3 Operación enqueue paso a paso

El encolado crea un nodo nuevo, copia el dato y ajusta el puntero final. Siempre debe verificarse que la reserva de memoria funcione.

int enqueue(ColaLista *cola, int valor) {
  Nodo *nuevo = malloc(sizeof(Nodo));
  if (!nuevo) {
    return 0;
  }
  nuevo->dato = valor;
  nuevo->siguiente = NULL;

  if (cola->cantidad == 0) {
    cola->frente = nuevo;
  } else {
    cola->final->siguiente = nuevo;
  }
  cola->final = nuevo;
  cola->cantidad++;
  return 1;
}

Cuando la cola estaba vacía, frente y final pasan a apuntar al mismo nodo. En escenarios con interrupciones conviene envolver la operación con una sección crítica.

6.4 Desencolado seguro y liberación

El desencolado recupera el valor del primer nodo, avanza el puntero y libera la memoria ocupada. Si el último elemento sale de la cola, ambos punteros vuelven a NULL.

int dequeue(ColaLista *cola, int *valor) {
  if (cola->cantidad == 0) {
    return 0;
  }
  Nodo *nodo = cola->frente;
  *valor = nodo->dato;
  cola->frente = nodo->siguiente;
  if (!cola->frente) {
    cola->final = NULL;
  }
  free(nodo);
  cola->cantidad--;
  return 1;
}

Esta implementación devuelve 0 si no existían elementos, lo que permite a la capa de aplicación decidir si reintentar o registrar un subflujo.

6.5 Estrategias de gestión de memoria

• Chequeo de asignaciones: cualquier retorno nulo de malloc debe propagarse para evitar nodos corruptos.
• Función de vaciado: liberar la cola al finalizar el programa impide fugas silenciosas en trayectorias de error.
• Contadores diagnósticos: registrar cantidad, asignaciones pendientes y fallas facilita auditar la memoria en sistemas embebidos.

Si los nodos almacenan estructuras grandes, conviene delegar la copia en funciones auxiliares para controlar que cada miembro se inicie correctamente.

6.6 Variantes y extensiones

• Nodo centinela: mantener un nodo vacío permanentemente reduce las comprobaciones de casos borde.
• Listas doblemente enlazadas: permiten convertir la cola en un deque sin reescribir la estructura principal.
• Colas genéricas: guardar void * o funciones de copia hace posible compartir el mismo código para distintos tipos.

Documenta las convenciones (propiedad y destrucción de datos) para evitar dobles liberaciones cuando la cola transporte punteros.

6.7 Ejemplo completo en C

El siguiente programa simula solicitudes que llegan a la cola, imprime su estado y realiza limpiezas antes de salir.

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

typedef struct Nodo {
  int dato;
  struct Nodo *siguiente;
} Nodo;

typedef struct {
  Nodo *frente;
  Nodo *final;
  int cantidad;
} ColaLista;

void inicializar(ColaLista *cola) {
  cola->frente = NULL;
  cola->final = NULL;
  cola->cantidad = 0;
}

int enqueue(ColaLista *cola, int valor) {
  Nodo *nuevo = malloc(sizeof(Nodo));
  if (!nuevo) {
    return 0;
  }
  nuevo->dato = valor;
  nuevo->siguiente = NULL;
  if (!cola->frente) {
    cola->frente = nuevo;
  } else {
    cola->final->siguiente = nuevo;
  }
  cola->final = nuevo;
  cola->cantidad++;
  return 1;
}

int dequeue(ColaLista *cola, int *valor) {
  if (!cola->frente) {
    return 0;
  }
  Nodo *nodo = cola->frente;
  *valor = nodo->dato;
  cola->frente = nodo->siguiente;
  if (!cola->frente) {
    cola->final = NULL;
  }
  free(nodo);
  cola->cantidad--;
  return 1;
}

void imprimir(const ColaLista *cola) {
  printf("[cola] cantidad=%d -> ", cola->cantidad);
  for (Nodo *n = cola->frente; n; n = n->siguiente) {
    printf("%d ", n->dato);
  }
  puts("");
}

void vaciar(ColaLista *cola) {
  int descartado;
  while (dequeue(cola, &descartado)) {
  }
}

int main(void) {
  ColaLista cola;
  inicializar(&cola);

  for (int i = 1; i <= 3; ++i) {
    enqueue(&cola, i * 10);
  }
  imprimir(&cola);

  int valor;
  dequeue(&cola, &valor);
  printf("desencolado: %d\n", valor);
  imprimir(&cola);

  enqueue(&cola, 99);
  enqueue(&cola, 100);
  imprimir(&cola);

  while (dequeue(&cola, &valor)) {
    printf("procesado: %d\n", valor);
  }
  imprimir(&cola);

  vaciar(&cola);
  return 0;
}

Prueba el ejemplo con distintas secuencias para verificar que los punteros regresen a NULL cuando la cola se vacía y que no se pierdan nodos.