This Java program demonstrates how to implement a stack that supports pushing, popping, and retrieving the minimum element in constant time. The stack uses an auxiliary stack to track the minimum values efficiently.

Program Structure

• MinStack Class: This class contains the stack logic and the methods to manipulate the stack and retrieve the minimum element.
• Main Method: Demonstrates the functionality of the MinStack class.

Java Code

import java.util.Stack;

public class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (!stack.isEmpty()) {
            int x = stack.pop();
            if (x == minStack.peek()) {
                minStack.pop();
            }
        }
    }

    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek();
        }
        throw new IllegalStateException("Stack is empty");
    }

    public int getMin() {
        if (!minStack.isEmpty()) {
            return minStack.peek();
        }
        throw new IllegalStateException("Stack is empty");
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("Minimum: " + minStack.getMin()); // Returns -3
        minStack.pop();
        System.out.println("Top: " + minStack.top());         // Returns 0
        System.out.println("Minimum: " + minStack.getMin()); // Returns -2
    }
}

Explanation of How the Program Works

1. Push Operation: Adds an element to the main stack and updates the minimum stack if necessary.
2. Pop Operation: Removes the top element from the main stack and also updates the minimum stack if the minimum element is being removed.
3. Top Operation: Returns the top element of the main stack without removing it.
4. GetMin Operation: Retrieves the current minimum element from the minStack without modifying it.

Key Components:

• MinStack Class: Manages two stacks; one for the elements and one for keeping track of the minimum elements.
• Auxiliary Stack (minStack): Every time an element is added to the main stack, the minimum between the new element and the current minimum (top of the minStack) is pushed onto the minStack.
• Efficiency: Each method (push, pop, getMin, top) operates in constant time O(1), which is critical for performance in real-time systems or high-frequency operations.

This approach effectively combines simplicity and efficiency, making it a suitable design for various practical applications needing minimum retrieval functionality alongside standard stack operations.

Conclusion

This MinStack class implementation provides an efficient way to track the minimum element in a stack at any given time, ensuring that all operations are performed in constant time. It is particularly useful in applications where quick access to the minimum element is frequently required.