Sugerencia solución

.java

// SUGERENCIA DE SOLUCIÓN

Queue<Vehiculo> colaVehiculos = new LinkedList<Vehiculo>();
Queue<Soat> colaPrioridadSoats = new PriorityQueue<Soat>(); // Clase Soat debe ser comparable
Queue<Soat> tempColaPrioridadSoats = new PriorityQueue<Soat>();
 
// adicionar datos a las colas (no a la temporal)

while (!colaPrioridadSoats.isEmpty()) {
    Soat s = colaPrioridadSoats.remove();
    
    int n = colaVehiculos.size();
    for (int i = 0; i < n; i++) {
        Vehiculo v = colaVehiculos.remove();
        v.setSoat(s);
        colaVehiculos.add(v);
    }

    tempColaPrioridadSoats.add(s);
}
while (!tempColaPrioridadSoats.isEmpty()) {
    Soat s = tempColaPrioridadSoats.remove();
    colaPrioridadSoats.add(s);
}
 
// mostrar la cola de vehiculos con toda la información