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

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

Problem Description
Design a queue that, in addition to supporting basic queue operations (enqueue, dequeue, peek at the front element), also supports retrieving the maximum value in the queue in constant time O(1).

Analysis of the Solution
This problem is an extension of the "Min Stack" problem for queues. Stacks have Last-In-First-Out (LIFO) properties, making it easy to maintain an auxiliary stack that records the maximum value for each element when it is pushed. However, queues are First-In-First-Out (FIFO). When the front element (which might be the maximum) is dequeued, we need to know the maximum among the remaining elements. Simply recording a global maximum is insufficient.

We need a method to dynamically track the current maximum value in the queue. The core idea is to use a double-ended queue (deque) as an auxiliary queue to maintain a "non-increasing" sequence, thereby guaranteeing O(1) time retrieval of the maximum.

Detailed Step-by-Step Explanation

Step 1: Understand the Core Data Structures
We need two data structures to work together:

  1. Main Queue (data_queue): A standard queue (can be implemented using deque or Queue) that stores all elements and handles standard enqueue and dequeue operations.
  2. Auxiliary Deque (max_deque): A double-ended queue (must be implemented using deque) used to dynamically maintain a sequence of candidate elements that "could become the maximum". This sequence is non-strictly decreasing (i.e., adjacent equal elements are allowed).

Step 2: Enqueue Operation (push / enqueue)
Suppose we want to add a value value to the queue.

  1. Main Queue Operation: Append value to the end of data_queue.
  2. Auxiliary Queue Operation: This is the crucial step. We need to maintain the decreasing property of max_deque.
    • Starting from the tail of max_deque, remove all elements that are less than value. Because these elements entered the queue before value and are smaller than value, they can never be the maximum as long as value is in the queue.
    • Append value to the tail of max_deque.

Example of Enqueue Process
Suppose we enqueue sequentially: [5, 3, 4]

  1. Enqueue 5:
    • data_queue: [5]
    • max_deque is empty, directly add -> [5]
  2. Enqueue 3:
    • data_queue: [5, 3]
    • Compare: tail of max_deque is 5, 5 > 3, so do not remove 5, simply append 3 to the tail -> max_deque: [5, 3]
  3. Enqueue 4:
    • data_queue: [5, 3, 4]
    • Start comparing from the tail of max_deque: tail is 3, 3 < 4, so remove 3.
    • Continue comparing: now tail is 5, 5 > 4, stop removing.
    • Append 4 to the tail -> max_deque: [5, 4]
      At this point, the queue maximum is 5, which is at the front of max_deque.

Step 3: Get Maximum Operation (get_max)
This operation is very straightforward:

  • Return the front element of max_deque.
  • Because we ensured during enqueue that max_deque is a decreasing sequence, the front element is the current maximum in the queue.
  • Time complexity: O(1)

Step 4: Dequeue Operation (pop / dequeue)
Suppose we want to remove an element from the front of the queue.

  1. Main Queue Operation: Remove an element from the front of data_queue, denoted as front_value.
  2. Auxiliary Queue Operation: Check if the removed front_value is equal to the front element of max_deque.
    • If equal: It means the element being removed from the main queue is exactly the current maximum. Therefore, we need to also remove the front element from max_deque because the maximum is no longer in the main queue.
    • If not equal: It means the removed element is not the maximum (it is located after the maximum in max_deque, and because it is smaller than some value, it might have been removed during enqueue, or it was never a candidate). In this case, max_deque requires no operation. The maximum remains unchanged.

Continuing the Example with Dequeue Process
Continuing from the previous example, queue state is: data_queue: [5, 3, 4], max_deque: [5, 4]

  1. First dequeue:
    • Dequeue 5 from data_queue -> data_queue: [3, 4]
    • The dequeued 5 equals the front 5 of max_deque, so also dequeue the front 5 from max_deque -> max_deque: [4]
    • Current maximum is 4.
  2. Second dequeue:
    • Dequeue 3 from data_queue -> data_queue: [4]
    • The dequeued 3 is not equal to the front 4 of max_deque, so max_deque remains unchanged -> max_deque: [4]
    • Current maximum is still 4.

Step 5: Peek at Front Element (peek)

  • Directly return the front element of data_queue.
  • This operation is independent of the maximum value and is a basic queue operation.

Complexity Analysis

  • Enqueue (push): Although sometimes multiple elements need to be removed from the tail of max_deque, each element is added to and removed from max_deque at most once. Therefore, the amortized time complexity is O(1).
  • Dequeue (pop): Only involves comparison and possible removal from the front, time complexity is O(1).
  • Get Maximum (get_max) and Peek Front (peek): Direct access, time complexity is O(1).

Code Implementation (Python Example)

from collections import deque

class MaxQueue:

    def __init__(self):
        self.data_queue = deque()  # Main queue
        self.max_deque = deque()   # Auxiliary deque for maintaining maximum

    def max_value(self) -> int:
        """
        Retrieve the maximum value in the queue.
        """
        if not self.max_deque:
            return -1  # Or return a specific value as required by the problem when the queue is empty
        return self.max_deque[0]

    def push_back(self, value: int) -> None:
        """
        Enqueue operation.
        """
        # 1. Add element to main queue
        self.data_queue.append(value)
        # 2. Maintain monotonicity of auxiliary deque (non-strictly decreasing)
        # Remove all elements from the tail that are less than the current value
        while self.max_deque and self.max_deque[-1] < value:
            self.max_deque.pop()
        # 3. Add current value to the tail of auxiliary deque
        self.max_deque.append(value)

    def pop_front(self) -> int:
        """
        Dequeue operation.
        """
        if not self.data_queue:
            return -1  # Queue is empty
        # 1. Dequeue from main queue
        front_value = self.data_queue.popleft()
        # 2. If the dequeued element is exactly the current maximum, dequeue from the front of auxiliary deque as well
        if front_value == self.max_deque[0]:
            self.max_deque.popleft()
        return front_value

    def peek_front(self) -> int:
        """
        Peek at the front element (optional, but often included as a basic operation).
        """
        if not self.data_queue:
            return -1
        return self.data_queue[0]

Summary
The core of this design pattern lies in using a monotonic double-ended queue to efficiently maintain candidates for the maximum value within the current valid window (i.e., the entire queue). It cleverly addresses the challenges posed by the FIFO nature of queues. This method also forms the basis for solving more complex problems like "Sliding Window Maximum".