Or try to predict availability based on recent queries. If there is only one stall open and someone checked its status 30s ago, respond that "maybe" a stall is free.

> Maybe they could add a reservation queue to the bathroom as new functionality.

The FIFO system does not take urgency into account. When making a query, it would be good to give an urgency rating on a scale of 0 to some_number.

Maybe the bathroom lock could literally be a mutex.

A queue would only work if everyone used this system. Unfortunately, you will always have visitors or people who don't want to participate.