You have no right to the bin above your seat. For those exit rows where you cannot put anything beneath the seat in front of you, flight attendants will generally try to help find some space somewhere for at least your small personal item, but any passenger may be required to check their bags rather than put them in the overhead bin.
It is entirely possible that the airline didn't enforce the bag limit, but the overhead bins can easily fill up even when the limit is strictly enforced. If every passenger, or even most passengers, brings a regulation sized carry-on on a full flight, it is obvious that many of the bags will not fit in the bins and will have to be checked.
In some cases, overhead bins may be marked as reserved for first class or premium economy passengers (or safety equipment, or pillows and blankets). Even in such cases, cabin crew may fill these bins with other bags in an attempt to accommodate as many passengers as possible, and a late-boarding passenger may be caught out with no space.
It is hard to imagine that they are likely to remove and check someone's bag so you may have that space. Overhead bin space is typically first-come first served, and at some point, they will declare the bins full and start checking bags (sometimes even before the bins are actually full). Note that if your bag must be checked, you should ensure you remove any essential items (medication, passports, keys, etc...) and any valuables, along with any hazardous material that cannot be checked, namely spare (uninstalled) lithium batteries including external power packs.
Boarding as early as possible (which, on some airlines, could require frequent flyer status or paying an extra fee) will help secure you overhead bin space.