3 - Representación de una cola lineal con arrays

3.1 Estructura Queue

La cola lineal se define a partir de una estructura que agrupa el buffer de datos, los punteros de control y, opcionalmente, un contador de elementos. Este bloque encierra toda la información necesaria para respetar el TDA sin exponer detalles internos al resto del programa.

#define CAPACIDAD 100

typedef struct {
  int datos[CAPACIDAD];
  int frente;
  int final;
  int cantidad;
} Cola;

Los campos frente y final contienen índices sobre el array. El contador cantidad permite discriminar estados sin realizar restas costosas ni depender de banderas externas.

3.2 Índices front y rear

La inicialización debe posicionar ambos índices al comienzo del arreglo y poner el contador en cero. A partir de allí cada inserción incrementa final y cada extracción incrementa frente. El ejemplo siguiente ilustra la rutina base:

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

int enqueue(Cola *cola, int valor) {
  if (cola->final == CAPACIDAD) {
    return 0;
  }
  cola->datos[cola->final++] = valor;
  cola->cantidad++;
  return 1;
}

int dequeue(Cola *cola, int *valor) {
  if (cola->frente == cola->final) {
    return 0;
  }
  *valor = cola->datos[cola->frente++];
  cola->cantidad--;
  return 1;
}

El reposicionamiento lineal tiene la limitación de que frente nunca vuelve a cero sin realizar desplazamientos o reinicios, tema que se retomará en el punto 3.5.

3.3 Capacidad máxima

Definir una constante como CAPACIDAD hace explícito el límite de la cola. Es importante calcularla considerando el peor caso de solicitudes pendientes y, si es necesario, agregar una función para ajustar la capacidad o recrear la estructura.

Un patrón conveniente es exponer auxiliares esVacia y esLlena para facilitar las validaciones desde el código de alto nivel:

int esVacia(const Cola *cola) {
  return cola->cantidad == 0;
}

int esLlena(const Cola *cola) {
  return cola->final == CAPACIDAD;
}

Estas funciones evitan repetir comparaciones y reducen el riesgo de estados inconsistentes.

3.4 Cola llena y cola vacía

La detección de estados extremos debe ejecutarse antes de modificar los índices. Si la cola está vacía, un intento de dequeue debe devolver un código de error y dejar los punteros intactos. En sentido inverso, si se detecta cola llena, el enqueue tiene que rechazar el valor antes de escribir sobre el arreglo.

  • Cola vacía: frente == final y cantidad == 0. El consumidor no tiene elementos para procesar.
  • Cola llena: final == CAPACIDAD. El productor debe esperar o disparar una ampliación del buffer.
  • Estado intermedio: frente < final y cantidad > 0. Hay datos disponibles y también espacio libre.

Documentar claramente estos estados simplifica la integración con módulos de negocio o hilos concurrentes.

3.5 Problema del modelo lineal

La implementación lineal pura desperdicia posiciones al comienzo del arreglo a medida que se desencolan elementos, porque frente avanza y nunca regresa. Cuando final alcanza CAPACIDAD, la cola se considera llena aunque existan casilleros libres al inicio.

Existen tres estrategias para mitigar esta desventaja:

  1. Compactación periódica: mover los elementos pendientes hacia el inicio y ajustar los índices. Es costoso para colas grandes.
  2. Reinicialización controlada: cuando la cola queda vacía, reiniciar frente y final a cero.
  3. Transición a modelo circular: utilizar aritmética modular para reciclar espacios, solución presentada en el tema 5.

Comprender este problema es crucial para dimensionar correctamente los buffers y evitar que la cola lineal se convierta en un cuello de botella.

3.6 Código completo listo para CLion

El siguiente archivo main.c integra la estructura, las funciones auxiliares y un flujo de pruebas que imprime el estado de la cola tras cada operación. Puedes copiarlo y ejecutarlo en CLion o en cualquier entorno con gcc.

#include <stdio.h>

#define CAPACIDAD 8

typedef struct {
  int datos[CAPACIDAD];
  int frente;
  int final;
  int cantidad;
} Cola;

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

int esVacia(const Cola *cola) {
  return cola->cantidad == 0;
}

int esLlena(const Cola *cola) {
  return cola->final == CAPACIDAD;
}

int enqueue(Cola *cola, int valor) {
  if (esLlena(cola)) {
    return 0;
  }
  cola->datos[cola->final++] = valor;
  cola->cantidad++;
  return 1;
}

int dequeue(Cola *cola, int *valor) {
  if (esVacia(cola)) {
    return 0;
  }
  *valor = cola->datos[cola->frente++];
  cola->cantidad--;
  if (cola->frente == cola->final) { /* se puede reiniciar para reutilizar espacio */
    cola->frente = 0;
    cola->final = cola->cantidad;
  }
  return 1;
}

void imprimir(const Cola *cola) {
  printf("[cola] frente=%d final=%d cantidad=%d -> ", cola->frente, cola->final, cola->cantidad);
  for (int i = cola->frente; i < cola->final; ++i) {
    printf("%d ", cola->datos[i]);
  }
  puts("");
}

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

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

  int valor;
  while (dequeue(&cola, &valor)) {
    printf("Desencolado: %d\n", valor);
    if (valor == 20) {
      enqueue(&cola, 99);
    }
  }
  imprimir(&cola);

  return 0;
}

El bloque imprimir ayuda a visualizar en la consola la evolución de los índices y evidencia el problema del modelo lineal cuando el frente avanza más rápido que el final.

Secuencia de la cola lineal mostrando avance del frente
Retornar