queue y dequeDocente: Tomás Assenza
Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe
std::queue)?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).
En std::queue solo se puede acceder al primer elemento (front()) y al último elemento (back()). No tiene operador [] ni iteradores.
pop()
push(x)
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
}
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!
"Ante una serie de ingresos en una cola, indicar en orden de llegada cuáles suben (múltiplos de 3) y cuáles esperan."
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;
}
std::queuestd::dequeO(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.
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
push_back / pop_back
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;
}
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.
"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."
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;
}
std::deque¿Cómo seguir practicando programación competitiva y estructuras de datos?
• Libro gratuito: Competitive Programmer's Handbook (cses.fi/book/book.pdf).
• Resolviendo problemas en jueces en línea: Codeforces, CSES, Beecrowd y LeetCode.
• Docente: Tomás Assenza (tassenza@frsf.utn.edu.ar o por mensaje privado de Teams).