Hub Taller STL
Taller de Estructuras Dinámicas (STL) • Módulo 5

Colas: queue y deque
FIFO, Prioridad y Colas Doblemente Enlazadas

Docente: Tomás Assenza

Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe

¿Qué es una Cola (std::queue)?

Estructura FIFO (First In, First Out)

Los elementos se agregan al final de la cola y se remueven del frente. El primero en llegar es el primero en ser atendido (como la fila del supermercado o de la parada de colectivo).

Puntos de Acceso

En std::queue solo se puede acceder al primer elemento (front()) y al último elemento (back()). No tiene operador [] ni iteradores.

Sale por el frente: pop()
7 (front)
3
10
9 (back)
Entra por atrás: push(x)

Definición y Operaciones de queue

Cabecera: #include <queue> (incluye tanto queue como priority_queue).


// 1. DEFINICION DE COLA NORMAL Y COLAS DE PRIORIDAD
queue<int> cola; // Cola FIFO estandar
priority_queue<int> maxCola; // Cola de prioridad: top() da siempre el MAYOR
priority_queue<int, vector<int>, greater<int>> minCola; // top() da el MENOR

// 2. ACCEDER AL ELEMENTO (en std::queue)
cola.front(); // Devuelve el primer elemento de la fila
cola.back();  // Aunque no es estricto de colas, tambien permite ver el ultimo

// 3. INSERTAR Y ELIMINAR
cola.push(elemento); // Encola al final
cola.pop();          // Desencola el elemento del frente

// 4. REVISAR SI LA COLA ESTA VACIA
if (cola.empty()) {
    // Esta vacia
} else {
    // No esta vacia
}
                    

Ejemplo 1: El Colectivero Misterioso

Práctica Queue

Imaginá que tenés una fila de personas en una parada de bondi. Cada uno tiene un número de entrada al bondi (porque el colectivero se puso estricto y ahora cada uno saca su numerito).

La cosa es que cuando llega el bondi, cada persona sube en el orden en que sacó el número, pero solo si su número es múltiplo de tres (porque el colectivero también está medio loco y le pinta hacer eso). Los que no, se tienen que quedar esperando al próximo bondi. ¡Clásico quilombo en la parada!

Simplificamos el problema:

"Ante una serie de ingresos en una cola, indicar en orden de llegada cuáles suben (múltiplos de 3) y cuáles esperan."

Resolución: El Colectivero Misterioso


void coleMisterioso(queue<int> &numeros) {
    cout << "Suben: ";
    while (!numeros.empty()) {
        int num = numeros.front();
        numeros.pop();

        if (num % 3 == 0) {
            cout << num << " ";
        } else {
            cout << "(espera " << num << ") ";
        }
    }
    cout << endl;
}

int main() {
    queue<int> filaBondi;
    for (int n : {7, 3, 10, 9, 2, 15}) {
        filaBondi.push(n);
    }

    coleMisterioso(filaBondi);
    return 0;
}
                        

Laboratorio en Vivo: Parada de Bondi con std::queue

OneCompiler - C++ Sandbox (Ejecutá la simulación FIFO)

Colas Dobles: std::deque

Doble Extremo en O(1)

A diferencia de queue y vector, una deque (Double-Ended Queue) permite agregar y sacar elementos tanto del principio como del final en tiempo constante.

Acceso Aleatorio Completo

Además de operar por ambas puntas, permite acceder a cualquier elemento usando corchetes d[indice] e iteradores, igual que un vector.

push_front / pop_front
d[0] (front)
d[1]
d[2]
d[3] (back)
push_back / pop_back

Operaciones de std::deque

Cabecera: #include <deque>


// 1. DEFINICION
deque<string> d;

// 2. INSERTAR AL PRINCIPIO O AL FINAL
d.push_back("final");     // Agrega al final de la deque
d.push_front("primero");  // Agrega adelante de todo

// 3. ACCEDER A CUALQUIER ELEMENTO
cout << d[0] << endl;      // Acceso por indice
cout << d.front() << endl; // Primer elemento
cout << d.back() << endl;  // Ultimo elemento

// 4. ELIMINAR DEL PRINCIPIO O DEL FINAL
d.pop_front(); // Elimina el primer elemento
d.pop_back();  // Elimina el ultimo elemento

// 5. CONSULTAR ESTADO
if (!d.empty()) {
    cout << "Cantidad: " << d.size() << endl;
}
                    

Ejemplo 2: Centro de Monitoreo (CME)

Práctica Deque

En el Centro de Monitoreo de Eventos (CME), Franco es el operador encargado de gestionar las alertas de seguridad en tiempo real para la ciudad. En el turno nocturno los eventos se multiplican y necesita manejar solo los más recientes, descartando los viejos:

• Cada vez que llegue un evento nuevo, debe agregarse adelante para visualizarlo de inmediato.

• Si el sistema excede la capacidad máxima de eventos recientes, los eventos más antiguos deben eliminarse automáticamente del final.

• La lista debe mostrarse del más reciente al menos reciente.

Simplificamos el problema:

"Crear una cola doblemente enlazada que agregue eventos al frente (push_front), elimine los antiguos por detrás (pop_back) y los muestre en orden."

Resolución: Centro de Monitoreo (CME)


void agregarEvento(deque<string> &eventos, const string &evento) {
    eventos.push_front(evento);
}

void limpiarEventosViejos(deque<string> &eventos, unsigned maxEventos) {
    while (eventos.size() > maxEventos) {
        eventos.pop_back();
    }
}

void mostrarEventos(const deque<string> &eventos) {
    cout << "Eventos recientes:" << endl;
    for (const auto &evento : eventos) {
        cout << "- " << evento << endl;
    }
}

int main() {
    deque<string> eventos;
    agregarEvento(eventos, "Usuario inicio sesion");
    agregarEvento(eventos, "Usuario cambio configuracion");
    agregarEvento(eventos, "Nuevo mensaje recibido");
    agregarEvento(eventos, "Archivo descargado");

    limpiarEventosViejos(eventos, 3);
    mostrarEventos(eventos);
    return 0;
}
                        

Laboratorio en Vivo: Historial CME con std::deque

OneCompiler - C++ Sandbox (Probá cambiar la capacidad máxima)

¡Felicitaciones por completar el Taller STL!

¿Cómo seguir practicando programación competitiva y estructuras de datos?

Bibliografía y Jueces Online

• Libro gratuito: Competitive Programmer's Handbook (cses.fi/book/book.pdf).

• Resolviendo problemas en jueces en línea: Codeforces, CSES, Beecrowd y LeetCode.

Contacto y Consultas

• Docente: Tomás Assenza (tassenza@frsf.utn.edu.ar o por mensaje privado de Teams).

Módulo 4: std::stack Volver al Hub Abrir Visualizador / Debugger STL