But how could a judge deport me if I was not physically in the USA at that time when he ordered such deportation?

If you were deported without being physically in the court room, it is called in absentia order of removal. An in absentia order of removal is as legal as if you were in court so long as DHS can show that they informed you of the date and time of the deportation hearing and that you failed to appear without a valid reason. A letter sent by 1st class mail to your address is enough even if you never got it. Another issue you must address is that once DHS lodged your deportation papers, you were not free to just leave the US without first going to court. And if this is what happened, then, iy is considered that you self deported yourself, which again is as valid as if the judge deported you in court .If that is indeed the case, a motion to reopen alleging lack of notice may not be easy. But you must still reopen your case under some other grounds and show the judge that you did not in fact receive notice. Apart from this, there is yet another issue which is that under s.241(a) INA, if ICE finds that you are back in the country, they may arrest and send you out of the US, this time without ever seeing a judge. Under that same law, CIS may not be able to approve any application you file with them include an I-485 green card application.. The facts of your case suggests to me that you should not try this at home and must instead speak seek the help of an experienced attorney.

The answer to your question depends on too many factors to list here and there is not enough information to properly advise you in such a forum. I think your case is sufficiently complicated and fact specific that you should consult with an attorney who can review in detail your immigration history and then provide you with an informed opinion on your chances for adjusting your status.

You will have to reopen your deportation case and then have the judge cancel deportation before you can apply for adjustment.

Since the judge ordered you deported, USCIS does not have jurisdiction to decide your case. The jurisdiction is with the immigration court. You will need to get the judge's decision set aside before you will be able to move forward toward adjustment. This is done by working with the ICE attorneys or by filing a motion to reopen before the judge. Be careful about the fact that you have a deportation order that can be executed upon at any time.