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

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

Problem Description
Design a queue that supports basic queue operations (enqueue, dequeue, get front element) and additionally supports retrieving the minimum element in the queue in constant time O(1). Assume the elements stored in the queue are comparable (e.g., integers).

Solution Analysis
The challenge of this problem lies in the queue's First-In-First-Out (FIFO) structure. When an element is dequeued, if it happens to be the current minimum, we need to quickly identify the new minimum among the remaining elements. Simply using a variable to track the minimum is insufficient because once the minimum is dequeued, we cannot quickly determine the next smallest value.

The core idea is to use an auxiliary double-ended queue (Deque) to dynamically maintain a "potential minimum sequence" of the current main queue. The front element of this auxiliary queue always represents the minimum value in the main queue.

Detailed Step-by-Step Explanation

  1. Data Structure Design

    • Main Queue (mainQueue): Use a standard queue (e.g., LinkedList) to store all elements, implementing normal FIFO operations.
    • Auxiliary Double-ended Queue (minDeque): Use a deque (e.g., ArrayDeque) to maintain a "non-strictly increasing" sequence. The key characteristic is that the front element is always the minimum in the main queue, and the sequence is in increasing order.

  2. Enqueue Operation (enqueue)

    • First, add the new element to the tail of the main queue.
    • Process the auxiliary queue:
      • Starting from the tail of the auxiliary queue, remove all elements that are greater than the new element. Since the new element is smaller and will be dequeued later (due to FIFO), those larger elements can never become the minimum in the future.
      • Then, add the new element to the tail of the auxiliary queue.
    • Time Complexity: Although a loop seems involved, each element is added to and removed from the auxiliary queue at most once, resulting in an amortized O(1) time complexity.

    Example: Enqueue 3, 1, 2 sequentially.

    • Enqueue 3: mainQueue[3], minDeque[3] (min: 3)
    • Enqueue 1: mainQueue[3, 1]. Tail of minDeque: 3 > 1, remove 3, add 1. minDeque becomes [1] (min: 1).
    • Enqueue 2: mainQueue[3, 1, 2]. Tail of minDeque: 1 < 2, simply add 2. minDeque becomes [1, 2] (min: 1). Since 1 comes before 2 and 1 < 2, the minimum remains 1 until 1 is dequeued.

  3. Dequeue Operation (dequeue)

    • Check if the front element of the main queue equals the front element of the auxiliary queue.
      • If equal, it means the dequeued element is the current minimum. Therefore, the front of the auxiliary queue must also be dequeued, as it is no longer in the main queue.
      • If not equal, simply dequeue the front of the main queue; the current minimum is unaffected.
    • Time Complexity: O(1).

    Continuing the example: mainQueue[3, 1, 2], minDeque[1, 2], min: 1.

    • Dequeue: mainQueue front 3 ≠ minDeque front 1. mainQueue becomes [1, 2], minDeque unchanged, min still 1.
    • Dequeue again: mainQueue front 1 = minDeque front 1. mainQueue becomes [2], dequeue minDeque front 1, minDeque becomes [2], min becomes 2.

  4. Get Front Element (getFront)

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

  5. Get Minimum Element (getMin)

    • Directly return the front element of the auxiliary queue.
    • Time Complexity: O(1).

Code Implementation (Java)

import java.util.LinkedList;
import java.util.Deque;
import java.util.Queue;

public class MinQueue {
    private Queue<Integer> mainQueue;
    private Deque<Integer> minDeque;

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

    public void enqueue(int value) {
        // Add new element to main queue
        mainQueue.offer(value);
        // Maintain auxiliary deque: remove all tail elements greater than the new element
        while (!minDeque.isEmpty() && minDeque.peekLast() > value) {
            minDeque.pollLast();
        }
        // Add the new element to the tail of the auxiliary deque
        minDeque.offerLast(value);
    }

    public int dequeue() {
        if (mainQueue.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int frontValue = mainQueue.poll();
        // If the dequeued element is the current minimum, also dequeue the front of the auxiliary deque
        if (frontValue == minDeque.peekFirst()) {
            minDeque.pollFirst();
        }
        return frontValue;
    }

    public int getFront() {
        if (mainQueue.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return mainQueue.peek();
    }

    public int getMin() {
        if (minDeque.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return minDeque.peekFirst();
    }
}

Key Points Summary

  • The auxiliary deque minDeque maintains a "non-strictly increasing" sequence, with the front always being the minimum.
  • During enqueue, removing larger elements from the tail ensures the sequence's increasing property and eliminates larger values that can never become the minimum.
  • During dequeue, the front of the auxiliary deque is only dequeued when it equals the front of the main queue (i.e., the current minimum).
  • All operations (enqueue, dequeue, getFront, getMin) have an amortized time complexity of O(1), and the space complexity is O(n).