Cola Estándar

Una cola es una estructura de datos lineal que opera bajo el principio FIFO (First In, First Out), controlada mediante dos punteros: frontal y trasero.

El puntero frontal siempre apunta al primer elemento de la cola, con inicialización en el índice cero.

Para el puntero trasero, existen dos enfoques principales:

Enfoque uno: El puntero trasero apunta al último elemento. En una cola vacía, se inicializa en -1. La cola no está vacía cuando el puntero frontal es menor o igual al trasero. El tamaño se calcula como la diferencia entre los punteros más uno.

Enfoque dos: El puntero trasero apunta a la posición siguiente al último elemento. En una cola vacía, se inicializa en cero. La cola está vacía cuando ambos punteros coinciden. El tamaño es la diferencia entre los punteros.

En ambos casos, la eliminación consiste en avanzar el puntero frontal.

Ejemplo de código en C++:

// Inserción (enfoque uno)
data[rear++] = value;
// Inserción (enfoque dos)
data[rear++] = value; // 'rear' ya apunta a la siguiente posición

// Eliminación
front++;

// Verificar vacío (enfoque uno)
if (front <= rear) std::cout << "La cola no está vacía";

// Tamaño (enfoque uno)
int size = rear - front + 1;

Cola Circular

Una cola circular optimiza el espacio al reutilizar posiones cuando los punteros alcanzan el límite del array. Generalmente se basa en el enfoque dos de la cola estándar.

Concepto clave: cuando un puntero llega al final del array (índice igual al tamaño N), se reinicia a cero.

Ejemplo de código:

// Inserción
data[rear++] = value;
if (rear == capacity) rear = 0;

// Eliminación
front++;
if (front == capacity) front = 0;

Cola Monótona

Similar a una pila monótona, esta estructura mantiene una secuencia monótona para determinar el máximo o mínimo dentro de ventanas de longitud fija en tiempo O(n).

Principio: al agregar un nuevo elemento, se comparan con el final de la cola; si el elemento final es mayor, se elimina hasta que se cumpla la condición monótona, luego se inserta el nuevo. El frente de la cola siempre contiene el valor extremo para la ventana actual.

Aplicaciones comunes incluyen la optimización de problemas de mochila múltiple o el cálculo de extreoms en subsecuencias.

Código de ejemplo para una cola monótona creciente estricta:

int front_ptr = 0, rear_ptr = -1;
for (int idx = 1; idx <= total_elements; idx++) {
    // Eliminar elementos fuera de la ventana
    if (front_ptr <= rear_ptr && queue[front_ptr] < idx - window_size + 1) front_ptr++;
    // Mantener propiedad monótona
    while (front_ptr <= rear_ptr && values[queue[rear_ptr]] >= values[idx]) rear_ptr--;
    // Insertar índice actual
    queue[++rear_ptr] = idx;
    // Guardar extremo si la ventana está completa
    if (idx >= window_size) results[++count] = values[queue[front_ptr]];
}

Problemas típicos incluyen ventanas deslizantes para el cálculo de mínimos o máximos.

Las colas de prioridad se implementan comúnmente mediante estructuras de heap.