Colas (Queues)

¿Qué es una cola?

Imagina una fila para comprar boletos en el cine. La primera persona que llega es la primera que es atendida. Las nuevas personas se forman al final. Esto es FIFO: First In, First Out (el primero en entrar es el primero en salir).

Cola:
Frente → [A] [B] [C] [D] ← Final
          ↑                  ↑
      Se atiende         Se forman
      (sale)             (entran)

Cola en C++ con queue

#include <queue>

queue<int> cola;

cola.push(10);    // Entra al final
cola.push(20);
cola.push(30);

cout << cola.front() << endl;  // 10 (el primero de la fila)
cout << cola.back() << endl;   // 30 (el último de la fila)

cola.pop();                     // Sale 10 (el primero)
cout << cola.front() << endl;  // 20 (ahora es el primero)

cout << cola.size() << endl;   // 2
cout << cola.empty() << endl;  // 0 (false)

Cola doble: deque

Una deque (double-ended queue) permite insertar y quitar de ambos extremos:

#include <deque>

deque<int> dq;

dq.push_back(10);     // Agregar al final
dq.push_front(5);     // Agregar al inicio
dq.push_back(20);     // dq = {5, 10, 20}

cout << dq.front() << endl;  // 5
cout << dq.back() << endl;   // 20

dq.pop_front();       // Quitar 5 del inicio
dq.pop_back();        // Quitar 20 del final
// dq = {10}

// También se puede acceder por índice
dq.push_back(30);
cout << dq[0] << endl;  // 10
cout << dq[1] << endl;  // 30

Cola de prioridad: priority_queue

Una cola de prioridad siempre te da el elemento de mayor valor primero (no el primero que entró):

#include <queue>

priority_queue<int> pq;

pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);

cout << pq.top() << endl;  // 50 (el mayor)
pq.pop();
cout << pq.top() << endl;  // 30
pq.pop();
cout << pq.top() << endl;  // 20

Cola de prioridad (menor primero)

// Min-heap: el menor tiene prioridad
priority_queue<int, vector<int>, greater<int>> pq;

pq.push(30);
pq.push(10);
pq.push(50);

cout << pq.top() << endl;  // 10 (el menor)

Con structs personalizados

struct Evento {
    int tiempo;
    string nombre;
};

struct Comparar {
    bool operator()(Evento &a, Evento &b) {
        return a.tiempo > b.tiempo;  // Menor tiempo = mayor prioridad
    }
};

priority_queue<Evento, vector<Evento>, Comparar> pq;

Aplicaciones

BFS (Búsqueda en anchura)

La cola es fundamental para BFS, que exploraremos en la sección de grafos:

queue<int> q;
q.push(nodoInicial);

while (!q.empty()) {
    int actual = q.front();
    q.pop();
    // Procesar y agregar vecinos
}

Simulación de procesos

// Simular una fila de impresión
queue<string> impresora;
impresora.push("Documento1.pdf");
impresora.push("Foto.jpg");
impresora.push("Tarea.docx");

while (!impresora.empty()) {
    cout << "Imprimiendo: " << impresora.front() << endl;
    impresora.pop();
}

Comparación: Pila vs Cola

Ejercicio de práctica

Simula una cola de atención. Lee N operaciones: "LLEGA nombre" (la persona se forma) o "ATIENDE" (se atiende a la primera persona). Imprime el nombre de cada persona atendida.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;

    queue<string> fila;

    for (int i = 0; i < n; i++) {
        string operacion;
        cin >> operacion;

        if (operacion == "LLEGA") {
            string nombre;
            cin >> nombre;
            fila.push(nombre);
        } else {  // ATIENDE
            if (!fila.empty()) {
                cout << "Atendiendo a: " << fila.front() << endl;
                fila.pop();
            } else {
                cout << "No hay nadie en la fila" << endl;
            }
        }
    }

    return 0;
}

Siguiente paso

Aprende sobre Problemas con Pilas y Colas para ver aplicaciones más avanzadas.