Реализовать очередь, в которой push_rear (),pop_front () и get_min () - все операции с постоянным временем

Я столкнулся с этим вопросом: Реализуйте очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем.

Сначала я думал об использовании структуры данных min-heap, которая имеет сложность O (1) для get_min ( ). Но push_rear () и pop_front () были бы O (log (n)).

Кто-нибудь знает, как лучше всего реализовать такую ​​очередь, которая имеет O (1) push (), pop () и min. ()?

Я погуглил об этом и хотел указать на эту ветку фанатов алгоритмов . Но похоже, что ни одно из решений не следует правилу постоянного времени для всех трех методов: push (), pop () и min ().

Спасибо за все предложения.