2 - Tipos de colas

2.1 Cola lineal

La cola lineal es la versión más intuitiva: se reserva memoria contigua, se define un frente y un final y se desplazan ambos punteros a medida que las solicitudes entran y salen. Es ideal para colas pequeñas o cuando el volumen de operaciones es moderado y previsiblemente inferior a la capacidad establecida.

Su mayor debilidad es el despericio de espacio cuando se desencolan elementos al comienzo y las posiciones liberadas no se reutilizan. Esto provoca el conocido problema de "falsa saturación" si se alcanzó el límite una vez.

#define TAM_MAX 64

typedef struct {
  int datos[TAM_MAX];
  int frente;
  int final;
} ColaLineal;

void inicializarLinea(ColaLineal *c) {
  c->frente = 0;
  c->final = 0;
}

int estaVacia(const ColaLineal *c) {
  return c->frente == c->final;
}

int estaLlena(const ColaLineal *c) {
  return c->final == TAM_MAX;
}

int enqueueLinea(ColaLineal *c, int valor) {
  if (estaLlena(c)) {
    return 0;
  }
  c->datos[c->final++] = valor;
  return 1;
}

int dequeueLinea(ColaLineal *c, int *valor) {
  if (estaVacia(c)) {
    return 0;
  }
  *valor = c->datos[c->frente++];
  return 1;
}

Este diseño obliga a reinicializar la cola cuando frente alcanza a final y ambos valen TAM_MAX. En sistemas interactivos se suele copiar los elementos remanentes al comienzo o recurrir a colas circulares.

2.2 Cola circular

En la cola circular se reutilizan las posiciones liberadas volviendo a la posición cero mediante el operador módulo. Solo se necesita un contador de elementos activos para diferenciar entre cola llena y vacía cuando frente == final.

  • Ventaja principal: aprovecha cada casillero del buffer sin mover datos.
  • Consideración: deben actualizarse los punteros en aritmética modular para evitar desbordes.
#define TAM_CIRC 64

typedef struct {
  int datos[TAM_CIRC];
  int frente;
  int final;
  int cantidad;
} ColaCircular;

void inicializarCircular(ColaCircular *c) {
  c->frente = 0;
  c->final = 0;
  c->cantidad = 0;
}

int enqueueCircular(ColaCircular *c, int valor) {
  if (c->cantidad == TAM_CIRC) {
    return 0;
  }
  c->datos[c->final] = valor;
  c->final = (c->final + 1) % TAM_CIRC;
  c->cantidad++;
  return 1;
}

int dequeueCircular(ColaCircular *c, int *valor) {
  if (c->cantidad == 0) {
    return 0;
  }
  *valor = c->datos[c->frente];
  c->frente = (c->frente + 1) % TAM_CIRC;
  c->cantidad--;
  return 1;
}

Las colas circulares aparecen en drivers, buffers de audio o protocolos de red porque encajan con la naturaleza repetitiva de los flujos.

2.3 Deque (double-ended queue)

El deque permite insertar y eliminar por ambos extremos. Se lo usa cuando la lógica requiere alternar prioridades, simular estructuras híbridas o implementar algoritmos de ventanas deslizantes.

Puede representarse con arrays o listas; en ambos casos hay que cuidar los casos frontales para evitar que el frente retroceda a valores negativos.

#define TAM_DEQUE 32

typedef struct {
  int datos[TAM_DEQUE];
  int frente;
  int final;
  int cantidad;
} Deque;

void inicializarDeque(Deque *d) {
  d->frente = 0;
  d->final = 0;
  d->cantidad = 0;
}

int pushFront(Deque *d, int valor) {
  if (d->cantidad == TAM_DEQUE) {
    return 0;
  }
  d->frente = (d->frente - 1 + TAM_DEQUE) % TAM_DEQUE;
  d->datos[d->frente] = valor;
  d->cantidad++;
  return 1;
}

int pushBack(Deque *d, int valor) {
  if (d->cantidad == TAM_DEQUE) {
    return 0;
  }
  d->datos[d->final] = valor;
  d->final = (d->final + 1) % TAM_DEQUE;
  d->cantidad++;
  return 1;
}

int popFront(Deque *d, int *valor) {
  if (d->cantidad == 0) {
    return 0;
  }
  *valor = d->datos[d->frente];
  d->frente = (d->frente + 1) % TAM_DEQUE;
  d->cantidad--;
  return 1;
}

int popBack(Deque *d, int *valor) {
  if (d->cantidad == 0) {
    return 0;
  }
  d->final = (d->final - 1 + TAM_DEQUE) % TAM_DEQUE;
  *valor = d->datos[d->final];
  d->cantidad--;
  return 1;
}

Cada operación mantiene la complejidad O(1) gracias al uso del módulo, lo que vuelve al deque una opción atractiva frente a combinaciones ad hoc de dos pilas o dos colas.

2.4 Cola de prioridad

La cola de prioridad modifica la regla FIFO permitiendo que el elemento con mayor o menor prioridad (según la definición del problema) sea atendido antes. Su implementación eficiente utiliza un heap binario almacenado en un array. El valor de prioridad puede ser igual al dato en sistemas sencillos o un campo separado.

Los insert y extract logran complejidad O(log n) al reorganizar el heap mediante operaciones sift-up y sift-down. Esta estructura es indispensable para planificadores, rutas de menor costo o simulaciones con eventos.

#define CAP_HEAP 128

typedef struct {
  int datos[CAP_HEAP];
  int cantidad;
} MinHeap;

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void siftUp(MinHeap *h, int idx) {
  while (idx > 0) {
    int padre = (idx - 1) / 2;
    if (h->datos[idx] >= h->datos[padre]) {
      break;
    }
    swap(&h->datos[idx], &h->datos[padre]);
    idx = padre;
  }
}

void siftDown(MinHeap *h, int idx) {
  while (1) {
    int hijoIzq = idx * 2 + 1;
    int hijoDer = hijoIzq + 1;
    int menor = idx;
    if (hijoIzq < h->cantidad && h->datos[hijoIzq] < h->datos[menor]) {
      menor = hijoIzq;
    }
    if (hijoDer < h->cantidad && h->datos[hijoDer] < h->datos[menor]) {
      menor = hijoDer;
    }
    if (menor == idx) {
      break;
    }
    swap(&h->datos[idx], &h->datos[menor]);
    idx = menor;
  }
}

int insertHeap(MinHeap *h, int valor) {
  if (h->cantidad == CAP_HEAP) {
    return 0;
  }
  int idx = h->cantidad++;
  h->datos[idx] = valor;
  siftUp(h, idx);
  return 1;
}

int extractMin(MinHeap *h, int *valor) {
  if (h->cantidad == 0) {
    return 0;
  }
  *valor = h->datos[0];
  h->datos[0] = h->datos[--h->cantidad];
  siftDown(h, 0);
  return 1;
}

Una cola de prioridad debe exponer también una operación peek para consultar el próximo elemento a salir sin modificar la estructura, y una función de comparación cuando se necesitan prioridades compuestas.

Retornar