Queue with Max efficient MAX operation

Given a queue perform following operations.

1. Enqueue

2. Dequeue

3. MAX

constraints:- all the above operations should be implemented in such a way that they are of O(1) complexity

Here is the thought.

1.) Doubly linked list for queue.
2.) Keep max along with each node till that node.

Let say the queue is
2 ->8 ->6 ->9

struct{
int data
int max
struct * next
struct *prev
}

when 2 inserted, queue will be
(2,2)
when 8 inserted, queue will be
(2,2) -> (8,8)
when 6 inserted, queue will be
(2,2) -> (8,8) -> (6, 8)
when 9 inserted, queue will be
(2,2) -> (8,8) -> (6, 8) -> (9,9)

But in this implementation dequeue is not O(1).

Other thought is building max-heap for the queue.