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 s;
    Stack minStack;
    Stack maxStack;

    public MyDS(){
        s = new Stack();
        minStack = new Stack();
        maxStack = new Stack();
    }

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

        if(minStack.isEmpty()){
            minStack.push(k);
        }else if(k = 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 stack;
static Stack minStack;
static Stack maxStack;

public DS(){
stack = new Stack();
minStack = new Stack();
maxStack = new Stack();
}

// 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{

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;
}

StackExchange Code Review Q#101630, answer score: 6