Queue that Support Push_rear, Pop_front, and GetMin in Constant Time

Source

Problem

Design a queue that supports push_rear, pop_front, and get_min in O(1). Would that be elegantly possible too?

Solution

Maintain an extra queue lets call it secondary queue.

push_rear

-> push the element in the primary queue

-> start from the front of the queue. Remove all elements which are smaller then the element. If element is greater then all it will take the last position.

pop_front

--> remove the element from primary queue

--> if the element is present at head of secondary queue remove it.

get_minimum

-->return head of the secondary queue