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

Problem Description
Design a queue that, in addition to supporting standard enqueue and dequeue operations, also 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).

Analysis of the Solution Approach
The difficulty of this problem lies in the fact that a queue is a First-In-First-Out (FIFO) data structure. After an element is enqueued, it remains in the queue for some time until all elements enqueued before it have been dequeued. If we simply maintain a variable to record the current minimum value, when this minimum element is dequeued, we need to know what the new minimum is, which must be the minimum among the remaining elements in the queue. Since elements are dynamically entering and leaving the queue, we cannot find the new minimum through a single traversal (which would be O(n) time complexity).

The core idea is to simulate a queue using two stacks and leverage the existing solution for "a stack that supports O(1) retrieval of minimum value."

1. Fundamental Component: MinStack
   First, let's recall a solved problem: implementing a stack that supports O(1) retrieval of the minimum value. We typically use an auxiliary stack (min_stack) to solve this. The main stack handles push and pop operations, while the top of the auxiliary stack always holds the minimum value among all elements in the main stack.

   • push(x): Push x onto the main stack. Simultaneously, if the auxiliary stack is empty, or x is less than or equal to the top of the auxiliary stack, also push x onto the auxiliary stack.
   • pop(): Pop the top element from the main stack. If the popped element equals the top of the auxiliary stack, also pop the top of the auxiliary stack.
   • getMin(): Directly return the top element of the auxiliary stack.

2. Implementing a Queue Using Stacks
   We know that a queue can be simulated using two stacks. Let's call these two stacks stack_in and stack_out.

   • enqueue(x): Push all enqueued elements into stack_in.
   • dequeue(): If stack_out is empty, pop all elements from stack_in one by one and push them onto stack_out. Then pop an element from stack_out. If stack_out is not empty, pop directly from stack_out.

3. Combined Solution: MinQueue
   Now, we combine these two ideas. Instead of using two ordinary stacks, we use two "MinStacks" as stack_in and stack_out. Each MinStack itself maintains the minimum value among its elements.

   • Structure of MinQueue:

     • stack_in: A MinStack responsible for handling enqueue operations.
     • stack_out: Another MinStack responsible for handling dequeue operations.

   • Key Point: The global minimum of the queue is either in stack_in or in stack_out. Specifically, it is the smaller of the minimum value of stack_in and the minimum value of stack_out. This is because all elements in the queue are either in stack_in or in stack_out.

Step-by-Step Explanation

Step 1: Define the "MinStack" Class
First, we need to implement the MinStack we learned about earlier, which will serve as the building block for our MinQueue.

class MinStack:
    def __init__(self):
        self.data_stack = []   # Main data stack
        self.min_stack = []     # Auxiliary min stack, top holds the current minimum

    def push(self, x: int) -> None:
        # Push element onto the main stack
        self.data_stack.append(x)
        # If the auxiliary stack is empty, or the new element is <= the top of the auxiliary stack (current min), also push onto auxiliary stack
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        # Cannot pop if the main stack is empty
        if not self.data_stack:
            return
        # Pop the top element from the main stack
        popped_value = self.data_stack.pop()
        # If the popped value equals the top of the auxiliary stack (current min), also pop from the auxiliary stack
        if popped_value == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        # Get the top element of the main stack
        if not self.data_stack:
            return -1 # Or raise an exception
        return self.data_stack[-1]

    def get_min(self) -> int:
        # Get the current minimum value in the stack, i.e., the top of the auxiliary stack
        if not self.min_stack:
            return -1 # Or raise an exception
        return self.min_stack[-1]

Step 2: Constructing the "MinQueue" Using Two "MinStacks"
Now, we use two MinStack objects to build our MinQueue.

class MinQueue:
    def __init__(self):
        self.stack_in = MinStack()  # Stack for enqueuing
        self.stack_out = MinStack() # Stack for dequeuing

    def enqueue(self, x: int) -> None:
        """Enqueue operation"""
        # All new elements are pushed into stack_in
        self.stack_in.push(x)

    def dequeue(self) -> None:
        """Dequeue operation"""
        # If stack_out is empty, we need to "pour" all elements from stack_in into stack_out
        if self.stack_out.get_min() == -1: # Or check if len(self.stack_out.data_stack) == 0 to determine if empty
            while self.stack_in.get_min() != -1: # While stack_in is not empty
                # Pop an element from stack_in
                val = self.stack_in.top()
                self.stack_in.pop()
                # Push that element onto stack_out
                self.stack_out.push(val)
        # Pop the top element from stack_out, completing the dequeue operation
        self.stack_out.pop()

    def get_min(self) -> int:
        """Retrieve the minimum value in the queue"""
        min_in = self.stack_in.get_min() # Minimum in stack_in, returns -1 if stack is empty
        min_out = self.stack_out.get_min() # Minimum in stack_out, returns -1 if stack is empty

        # Case 1: Both stacks are empty, queue is empty
        if min_in == -1 and min_out == -1:
            return -1
        # Case 2: Only stack_in has elements
        elif min_out == -1:
            return min_in
        # Case 3: Only stack_out has elements
        elif min_in == -1:
            return min_out
        # Case 4: Both stacks have elements, return the smaller of the two
        else:
            return min(min_in, min_out)

    # A queue typically also needs a front() method to get the front element (the next element to be dequeued)
    def front(self) -> int:
        """Get the front element without dequeuing it"""
        # Principle same as dequeue: if stack_out is empty, need to pour elements
        if self.stack_out.get_min() == -1:
            while self.stack_in.get_min() != -1:
                val = self.stack_in.top()
                self.stack_in.pop()
                self.stack_out.push(val)
        # Now the front element is the top of stack_out
        return self.stack_out.top()

Step 3: Complexity Analysis

• Time Complexity:

  • enqueue(x): O(1). Simply calls stack_in.push(x).
  • dequeue(): Amortized time complexity is O(1). Although in the worst case, when stack_out is empty, we need to move all elements from stack_in to stack_out, which is an O(n) operation. However, each element is only moved from stack_in to stack_out once and popped from stack_out once. Therefore, averaging the total cost of a series of operations over each operation, the amortized cost of dequeue is constant time.
  • get_min(): O(1). Just compares the minimums of the two stacks, a constant time operation.
  • front(): Amortized time complexity is O(1), for the same reason as dequeue.

• Space Complexity: O(n). Two stacks are needed to store all elements. The space consumption of each stack (including its auxiliary stack) is linear to the number of elements n.

Conclusion
Implementing a queue that supports O(1) retrieval of the minimum value combines the ideas of "implementing a queue using stacks" and the "MinStack." By maintaining two MinStacks (stack_in and stack_out) and ensuring that the global minimum of the queue is the smaller of the two stacks' respective minimums, we successfully meet the requirement that all operations complete in constant or amortized constant time. This is a very classic and clever interview question that deeply examines the understanding and flexible application of the fundamental characteristics of stacks and queues.