A data structure with push(int x), pop(), min() and max() in O(1) I have written this Java code for a data structure which includes 3 stacks to supports four operations in \$O(1)\$: push(int x), pop(), min() and max().

Instead of pushing new max and min in every push, I tried to optimize code in this way to have less space.

import java.util.Stack;

public class MyDS {

    Stack&lt;Integer&gt; s;
    Stack&lt;Integer&gt; minStack;
    Stack&lt;Integer&gt; maxStack;

    public MyDS(){
        s = new Stack&lt;Integer&gt;();
        minStack = new Stack&lt;Integer&gt;();
        maxStack = new Stack&lt;Integer&gt;();
    }

    // Push Method
    public void push(int k){

        if(minStack.isEmpty()){
            minStack.push(k);
        }else if(k &lt;= minStack.peek()){
            minStack.push(k);
        }

        if(maxStack.isEmpty()){
            maxStack.push(k);
        }else if(k &gt;= maxStack.peek()){
            maxStack.push(k);
        }   
        s.push(k);  
    }

    // Pop Method
    public void pop(){

        int popped;
        if(!s.isEmpty()){
            popped = s.pop();   
        }else{
            popped = -1;
        }

        if(popped == min()){
            minStack.pop();
        }

        if(popped == max()){
            maxStack.pop();
        }
    }

    // Min Method
    public int min(){
        if(!minStack.isEmpty()){
            return minStack.peek();
        }else{
            return Integer.MIN_VALUE;
        }
    }

    // Max Method
    public int max(){
        if(!maxStack.isEmpty()){
            return maxStack.peek();
        }else{
            return Integer.MAX_VALUE;
        }
    }
}


This is my earlier version of DS:

import java.util.Stack;

public class DS {
    static Stack&lt;Integer&gt; stack;
    static Stack&lt;Integer&gt; minStack;
    static Stack&lt;Integer&gt; maxStack;

    public DS(){
        stack = new Stack&lt;Integer&gt;();
        minStack = new Stack&lt;Integer&gt;();
        maxStack = new Stack&lt;Integer&gt;();
    }

    // Push Method
    public void push(int k){        
        stack.push(k);
        if(!minStack.isEmpty()){
            minStack.push(Math.min(k, minStack.peek()));
        }else{
            minStack.push(k);
        }
        if(!maxStack.isEmpty()){
            maxStack.push(Math.max(k, maxStack.peek()));
        }else{
            maxStack.push(k);
        }
    }

    // Pop Method
    public void pop(){
        if(!stack.isEmpty() &amp;&amp; !minStack.isEmpty() &amp;&amp; !maxStack.isEmpty()){
            stack.pop();
            minStack.pop();
            maxStack.pop();
        }
    }

    // Find Min 
    public int findMin(){
        if(!minStack.isEmpty()){
            return minStack.peek();
        }
        return Integer.MIN_VALUE;
    }

    // Find Max
    public int findMax(){
        if(!maxStack.isEmpty()){
            return maxStack.peek();
        }
        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {

        DS ds = new DS();

        System.out.println("Push 7, 6, 5: ");
        ds.push(7);
        ds.push(6);
        ds.push(5);

        System.out.println("S1: " + stack);
        System.out.println("S2: " + minStack);
        System.out.println("S3: " + maxStack);

        System.out.println("Min till now: " + ds.findMin());
        System.out.println("Max till now: " + ds.findMax());

        System.out.println("Push 4, 3: ");
        ds.push(4);
        ds.push(3);

        System.out.println(stack);
        System.out.println(minStack);
        System.out.println(maxStack);

        System.out.println("Min till now: " + ds.findMin());
        System.out.println("Max till now: " + ds.findMax());

        System.out.println("1 pop(): ");
        ds.pop();
        System.out.println("Min till now: " + ds.findMin());
        System.out.println("Max till now: " + ds.findMax());


        System.out.println("1 pop(): ");
        ds.pop();
        System.out.println("Min till now: " + ds.findMin());
        System.out.println("Max till now: " + ds.findMax());
    }
}
Your MyDS class has the right idea, in general.

Special values like -1, Integer.MIN_VALUE, and Integer.MAX_VALUE make me suspicious.  All of those special values denote what I consider to be error cases.  Using special cases that might also be valid data is a dangerous habit that can lead to bugs.  Instead of those special numbers, it would be better to throw exceptions — probably NoSuchElementException.  You should also offer a size() and/or an isEmpty() method so that users of your data structure can proactively avoid encountering the exception.

The three instance variables should be private.  The default access is rarely appropriate.  java.util.Stack is to be avoided, due to unfortunate historical design decisions (inappropriately extending java.util.Vector, and being thread-safe by default).  The documentation recommends ArrayDeque instead.

Of the four operations in MyDS, I think pop() could use the most work.    It's weird that pop() doesn't return a value.  The -1 is entirely avoidable: if the main stack is empty, the min and max stacks should surely be empty too.

public int pop() {
    if (s.isEmpty()) {
        throw new NoSuchElementException();
    }
    int popped = s.pop();
    if (popped == min()) {
        minStack.pop();
    }
    if (popped == max()) {
        maxStack.pop();
    }
    return popped;
}