Implement a Queue that Supports O(1) Time Retrieval of Maximum Value

Problem Description
Design a queue that, in addition to supporting basic queue operations (enqueue, dequeue, peek at the front element), can also retrieve the maximum value within the queue in O(1) time. Assume the elements in the queue are integers.

Problem-Solving Approach
If we were to implement a regular queue, we could use a linked list or an array. However, retrieving the maximum value would require traversing the entire queue, resulting in O(n) time complexity. To achieve O(1) time for retrieving the maximum value, we need to maintain an additional data structure to track the current maximum value in the queue. The key insight is: when a new element is enqueued, it may become the future maximum; when an element is dequeued, if that element happens to be the current maximum, we need to know what the next maximum value is.

Solution: Using a Double-Ended Queue for Assistance
We can use a main queue (a regular queue) to store all elements, while simultaneously using a double-ended queue (deque) to maintain a "candidate sequence for the maximum value." The elements in this deque are stored in monotonically decreasing order, with the front element being the current maximum value in the queue.

Detailed Steps

1. Data Structure Definition

   • queue: A regular queue (implemented using a linked list or array) used to store all elements.
   • maxDeque: A double-ended queue (deque) used to maintain the candidate sequence for the current maximum value in the queue, keeping it monotonically decreasing.

2. Enqueue Operation (push)

   • Add the new element to the tail of the main queue.
   • Process the deque:
     • Starting from the tail of the deque, remove all elements smaller than the new element (because these elements can no longer be the maximum after the new element is added).
     • Add the new element to the tail of the deque.
   • Time Complexity: Although there appears to be a loop, each element is added to and removed from the deque at most once, resulting in an amortized time complexity of O(1).

3. Dequeue Operation (pop)

   • If the main queue is empty, throw an exception.
   • Remove the element from the front of the main queue.
   • If the removed element equals the element at the front of the deque (i.e., the current maximum), also remove that element from the front of the deque.
   • Time Complexity: O(1).

4. Retrieve Maximum Value (getMax)

   • If the deque is not empty, return its front element.
   • If the queue is empty, throw an exception.
   • Time Complexity: O(1).

5. Peek at Front Element (peek)

   • Return the front element of the main queue.
   • Time Complexity: O(1).

Example Walkthrough
Assume the following operations are performed sequentially:
push(1), push(3), push(2), getMax(), pop(), getMax()

• push(1):
  Main queue: [1]
  maxDeque: [1] (initially added)

• push(3):
  Main queue: [1, 3]
  maxDeque: Remove 1 from the tail (since 1 < 3), add 3 → [3]

• push(2):
  Main queue: [1, 3, 2]
  maxDeque: 2 < 3, directly add 2 → [3, 2] (monotonically decreasing)

• getMax(): Return the front of maxDeque, which is 3.

• pop(): The front element of the main queue, 1, is dequeued, but 1 ≠ 3, so maxDeque remains unchanged.
  Main queue: [3, 2]
  maxDeque: [3, 2]

• getMax(): Return the front of maxDeque, which is 3.

Edge Case Handling

• When the queue is empty, dequeue or getMax operations should throw an exception.
• If multiple identical maximum values exist, maxDeque should retain all of them (or use indices to distinguish them) to ensure the maximum value is not prematurely removed during dequeue operations.

Key Points for Code Implementation (Pseudocode)

class MaxQueue:
    def __init__(self):
        self.queue = collections.deque()  # Main queue
        self.maxDeque = collections.deque()  # Auxiliary double-ended queue

    def push(self, value):
        self.queue.append(value)
        while self.maxDeque and self.maxDeque[-1] < value:
            self.maxDeque.pop()
        self.maxDeque.append(value)

    def pop(self):
        if not self.queue:
            raise Exception("Queue is empty")
        val = self.queue.popleft()
        if val == self.maxDeque[0]:
            self.maxDeque.popleft()
        return val

    def getMax(self):
        if not self.maxDeque:
            raise Exception("Queue is empty")
        return self.maxDeque[0]

    def peek(self):
        if not self.queue:
            raise Exception("Queue is empty")
        return self.queue[0]

Summary
By maintaining a monotonically decreasing double-ended queue, we ensure that the maximum value is always at the front of maxDeque. This method achieves an amortized time complexity of O(1) for each operation and a space complexity of O(n), representing a classic space-for-time trade-off solution.