Implement a Queue with O(1) Time Complexity for Retrieving the Maximum Value

Problem Description
Design a queue that, in addition to supporting basic queue operations (enqueue, dequeue), can also retrieve the maximum element in the queue in constant time.

Analysis of Solution Approach
This problem is an extension of the "Min Stack" problem but is more challenging. The First-In-First-Out (FIFO) nature of a queue complicates maintaining the maximum value because when the front element is dequeued, if it happens to be the current maximum, we need to quickly know the maximum among the remaining elements.

Core Idea: Use a Double-ended Queue to Maintain the Maximum
We can use an auxiliary double-ended queue to maintain a candidate sequence for the current maximum value in the queue.

Implementation Steps

1. Data Structure Design

   • Use a regular queue dataQueue to store the actual data.
   • Use a double-ended queue maxQueue to store elements that could become the maximum (arranged in decreasing order).

2. Enqueue Operation

   • Add the new element to dataQueue.
   • Maintain maxQueue: Starting from the tail, remove all elements smaller than the current value, then add the new element to the tail.
   • This ensures that the head of maxQueue is always the current maximum.

3. Dequeue Operation

   • Remove an element from the head of dataQueue.
   • If the removed element equals the head element of maxQueue, also remove it from the head of maxQueue.
   • This ensures that the head of maxQueue always represents the current maximum in the queue.

4. Get Maximum Operation

   • Directly return the element at the head of maxQueue.

Example Implementation

from collections import deque

class MaxQueue:
    def __init__(self):
        self.dataQueue = deque()  # Queue to store actual data
        self.maxQueue = deque()   # Double-ended queue to store possible maximum values
    
    def enqueue(self, value: int) -> None:
        # Add new element to the main queue
        self.dataQueue.append(value)
        
        # Maintain the max queue: remove all elements smaller than the current value
        while self.maxQueue and self.maxQueue[-1] < value:
            self.maxQueue.pop()
        
        # Add the new element to the max queue
        self.maxQueue.append(value)
    
    def dequeue(self) -> int:
        if not self.dataQueue:
            raise Exception("Queue is empty")
        
        # Remove element from the head of the main queue
        value = self.dataQueue.popleft()
        
        # If the removed element is the current maximum, also remove it from the max queue
        if value == self.maxQueue[0]:
            self.maxQueue.popleft()
        
        return value
    
    def getMax(self) -> int:
        if not self.maxQueue:
            raise Exception("Queue is empty")
        return self.maxQueue[0]

Time Complexity Analysis

• Enqueue operation: Although there is an inner loop, each element is processed at most twice (once when enqueued and once when dequeued), resulting in an amortized time complexity of O(1).
• Dequeue operation: O(1)
• Get maximum operation: O(1)

Example Demonstration
Operation sequence: enqueue(1) → enqueue(3) → enqueue(2) → getMax() → dequeue() → getMax()

Execution process:

1. enqueue(1): dataQueue = [1], maxQueue = [1]
2. enqueue(3): dataQueue = [1,3], maxQueue removes 1 and adds 3 → [3]
3. enqueue(2): dataQueue = [1,3,2], maxQueue = [3,2]
4. getMax(): returns 3
5. dequeue(): removes 1, dataQueue = [3,2], 1≠3, maxQueue unchanged
6. getMax(): returns 3

Key Points to Understand

• maxQueue maintains a decreasing sequence, with the head always being the current maximum.
• When a new element is enqueued, it "invalidates" all smaller elements.
• We only need to update maxQueue when the maximum value is dequeued.

This design cleverly leverages the FIFO property of a queue. By maintaining a candidate maximum sequence, it achieves O(1) time complexity for retrieving the maximum value.