Uso de std::stack, std::queue y std::priority_queue en C++

La biblioteca estándar de C++ proporciona stack, queue y priority_queue para trabajar fácilmente con distintas estructuras de datos lineales. Estas estructuras se basan en tres modelos clásicos: LIFO (Last-In First-Out), FIFO (First-In First-Out) y un modelo basado en prioridades. Este artículo explica cómo funciona cada estructura, sus casos de uso y ejemplos prácticos.

1) ¿Qué es stack? (Estructura LIFO)

std::stack funciona con el principio LIFO (Last-In First-Out). Solo se puede acceder, añadir o retirar elementos desde la parte superior (top).

• push() → añade un elemento arriba
• pop() → elimina el elemento superior
• top() → devuelve el elemento superior
• empty() → indica si la pila está vacía
• size() → cantidad de elementos

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

int main() {
    stack<int> st;

    st.push(10);
    st.push(20);
    st.push(30);

    cout << "Top: " << st.top() << endl; // 30

    st.pop(); // elimina 30

    cout << "Top: " << st.top() << endl; // 20
}

Casos de uso: funciones de deshacer, validación de paréntesis, simulación del call stack.

2) ¿Qué es queue? (Estructura FIFO)

std::queue funciona según el principio FIFO: el primer elemento en entrar es el primero en salir.

• push() → añade un elemento al final
• front() → devuelve el primer elemento
• back() → devuelve el último elemento
• pop() → elimina el primer elemento
• empty(), size()

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

int main() {
    queue<string> q;

    q.push("Juan");
    q.push("Emilia");
    q.push("Miguel");

    cout << "Front: " << q.front() << endl; // Juan
    cout << "Back: " << q.back() << endl;   // Miguel

    q.pop(); // elimina Juan

    cout << "Front: " << q.front() << endl; // Emilia
}

Casos de uso: colas de trabajo, sistemas de mensajería, procesamiento secuencial.

3) ¿Qué es priority_queue?

std::priority_queue es una cola con prioridad que ordena automáticamente los elementos. Por defecto, funciona como un max-heap: el elemento más grande tiene la mayor prioridad.

• push() → inserta un elemento
• top() → devuelve el elemento con mayor prioridad
• pop() → elimina ese elemento prioritario
• size(), empty()

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

int main() {
    priority_queue<int> pq;

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

    cout << "Top: " << pq.top() << endl; // 80

    pq.pop(); // elimina 80

    cout << "Top: " << pq.top() << endl; // 50
}

Casos de uso: algoritmos como Dijkstra, planificación de tareas, procesamiento basado en prioridad.

4) priority_queue como Min-Heap

Por defecto, priority_queue es un max-heap. Para usarlo como min-heap, se emplea greater<>.

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

int main() {
    priority_queue<int, vector<int>, greater<int>> minpq;

    minpq.push(40);
    minpq.push(10);
    minpq.push(30);

    cout << "Top: " << minpq.top() << endl; // 10
}

5) Ejemplos prácticos

a) Validación de paréntesis usando stack

#include <stack>
#include <string>
#include <iostream>
using namespace std;

bool check(string s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(') st.push(c);
        else if (c == ')') {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    cout << check("((a+b)*(c-d))"); // 1
}

b) Simulación de una cola de banco usando queue

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

int main() {
    queue<string> customers;

    customers.push("Juan");
    customers.push("Emilia");
    customers.push("David");

    while (!customers.empty()) {
        cout << "Atendiendo a: " << customers.front() << endl;
        customers.pop();
    }
}

c) Priorización de tareas usando priority_queue

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

int main() {
    priority_queue<pair<int,string>> tasks;

    tasks.push({3, "Baja prioridad"});
    tasks.push({10, "Alta prioridad"});
    tasks.push({5, "Prioridad media"});

    while (!tasks.empty()) {
        cout << "Tarea: " << tasks.top().second << endl;
        tasks.pop();
    }
}

6) ¿Cuándo utilizar cada estructura?

• stack: funciones de deshacer, análisis de expresiones, pilas de llamadas
• queue: colas de procesos, secuencias de tareas, sistemas de mensajes
• priority_queue: tareas priorizadas, algoritmos, procesamiento según prioridad

Elegir la estructura correcta mejora tanto el rendimiento como la claridad del código.

7) TL;DR

Artículos relacionados