Вы должны перейти с первого варианта.
Когда люди хотят иметь Очередь (интерфейс) под рукой, они ожидают, что очередь будет работать определенным образом. Поведение указывается в интерфейсе, и клиенту не нужно беспокоиться о реализации или вносить изменения при переключении.
Это не относится к вашей очереди, если вы реализуете этот интерфейс, но выдает исключение времени выполнения, вы неожиданно нарушите ожидание вашего клиента. Иностранные программы запрашивают очередь именно потому, что не хотят, чтобы их "обманули", чтобы получить что-то не взаимозаменяемое.
Лучше сделать это явным, не реализуя очередь, если только вы не можете прозрачно обработать прерванное исключение внутри вашего объекта.