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

Problem Description
Design a queue that, in addition to supporting basic queue operations (enqueue, dequeue, peek front), can retrieve the minimum value in the queue with O(1) time complexity. Assume the elements stored in the queue are comparable.

Solution Approach
The characteristic of a queue is First-In-First-Out (FIFO), and the minimum value changes dynamically as elements are dequeued. For example, if the minimum value is at the front of the queue, it needs to be updated after dequeuing. To achieve O(1) retrieval of the minimum value, we combine the properties of a standard queue and a monotonic queue:

1. Main Queue: Use a standard queue (e.g., LinkedList) to store all elements, supporting normal enqueue and dequeue operations.
2. Auxiliary Deque: Use a double-ended queue (e.g., ArrayDeque) to maintain a non-strictly monotonic increasing sequence, where the front always holds the current minimum value in the queue.

Step-by-Step Details

1. Initialization

   • Create two queues: queue (main queue) and minDeque (auxiliary double-ended queue).

2. Enqueue Operation (push)

   • Add the new element x to queue.
   • Process minDeque: Starting from the tail, if the tail element is greater than x, repeatedly pop from the tail (because these older elements will be dequeued after x and cannot become the minimum) until minDeque is empty or the tail element ≤ x.
   • Add x to the tail of minDeque.
   • Time Complexity: Each element enters and leaves minDeque at most once, amortized O(1).

3. Dequeue Operation (pop)

   • If queue is empty, throw an error.
   • Pop the front element val from queue.
   • If val equals the front element of minDeque, it means the current minimum value is being dequeued, so synchronously pop the front of minDeque.
   • Time Complexity: O(1).

4. Get Minimum Operation (getMin)

   • Directly return the front element of minDeque (if the queue is not empty).
   • Time Complexity: O(1).

5. Other Operations

   • peek (get front): Return the front of queue, O(1).
   • isEmpty: Check if queue is empty, O(1).

Example Walkthrough
Operation sequence: push(3), push(1), push(2), getMin(), pop(), getMin()

• push(3):
  queue → [3]
  minDeque → [3] (added directly initially)
• push(1):
  queue → [3, 1]
  Tail of minDeque is 3 > 1, pop 3 → minDeque becomes empty, then add 1 → [1]
• push(2):
  queue → [3, 1, 2]
  Tail of minDeque is 1 ≤ 2, add 2 directly → [1, 2]
• getMin() → 1 (front of minDeque)
• pop():
  Pop front 3 from queue, but 3 ≠ front of minDeque (which is 1), so minDeque remains unchanged → [1, 2]
• getMin() → 1

Complexity Analysis

• Time Complexity: All operations are amortized O(1).
• Space Complexity: O(n), worst-case when all elements are simultaneously present in minDeque (e.g., input is a strictly decreasing sequence).

Key Points

• The auxiliary queue minDeque maintains a non-strictly increasing sequence, allowing duplicate elements (e.g., after push(1), push(1) again, both 1s need to be retained to correctly handle dequeues).
• During dequeue, the front of minDeque is popped only if it equals the front of the main queue, to avoid prematurely losing the minimum value.

Code Implementation (Java)

import java.util.*;

class MinQueue {
    private Queue<Integer> queue;
    private Deque<Integer> minDeque;

    public MinQueue() {
        queue = new LinkedList<>();
        minDeque = new ArrayDeque<>();
    }

    public void push(int x) {
        queue.offer(x);
        while (!minDeque.isEmpty() && minDeque.peekLast() > x) {
            minDeque.pollLast();
        }
        minDeque.offerLast(x);
    }

    public int pop() {
        if (queue.isEmpty()) throw new NoSuchElementException();
        int val = queue.poll();
        if (val == minDeque.peekFirst()) {
            minDeque.pollFirst();
        }
        return val;
    }

    public int getMin() {
        if (minDeque.isEmpty()) throw new NoSuchElementException();
        return minDeque.peekFirst();
    }

    public int peek() {
        if (queue.isEmpty()) throw new NoSuchElementException();
        return queue.peek();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}