Queue with constant-time min and max

Implement a FIFO queue of integers that can also report its smallest and largest element at any time.

Implement the MinMaxQueue class:

• MinMaxQueue() creates an empty queue.
• enqueue(val: int) -> None adds val at the back.
• dequeue() -> int removes and returns the front element.
• get_min() -> int returns the smallest element currently in the queue, without removing it.
• get_max() -> int returns the largest element currently in the queue, without removing it.

Calling dequeue, get_min or get_max on an empty queue should raise an error.

Constraints

• Every operation must run in O(1) time (amortized O(1) is acceptable for enqueue).
• Values may repeat and may be negative.
• Up to 10^5 operations in total.

Example

q = MinMaxQueue()
q.enqueue(6); q.enqueue(2); q.enqueue(9); q.enqueue(2)
q.get_min()  -> 2
q.get_max()  -> 9
q.dequeue()  -> 6
q.dequeue()  -> 2
q.get_min()  -> 2    # the second 2 is still queued
q.dequeue()  -> 9
q.get_max()  -> 2

Start by describing the simple approach, then make all queries constant time.

Reconstructed from the reported question; details may differ from what interviewers ask.