5
\$\begingroup\$

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

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

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

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

        if(maxStack.isEmpty()){
            maxStack.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<Integer> stack;
    static Stack<Integer> minStack;
    static Stack<Integer> maxStack;

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

    // 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() && !minStack.isEmpty() && !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());
    }
}
\$\endgroup\$
  • \$\begingroup\$ Why did you include two versions? Are you seeking a comparative-review of the two snippets? \$\endgroup\$ – 200_success Aug 22 '15 at 4:32
  • \$\begingroup\$ @200_success, Not really. I wanted to show that I have already tried one optimization. If it is unnecessary, I can remove it. \$\endgroup\$ – Mehrdad Aug 22 '15 at 6:14
  • \$\begingroup\$ Aside: if pop is 'pop anything' rather than 'pop the last thing pushed', then you don't need a container at all: you just need three member variables: the number of objects 'stored', the minimum, and the maximum. If your stack 'stores' more than 2 elements, you just have pop remove something that isn't one of the extrema. \$\endgroup\$ – user14393 Aug 22 '15 at 10:50
  • \$\begingroup\$ are you looking for a minmax heap? \$\endgroup\$ – SingleNegationElimination Aug 22 '15 at 15:10
  • \$\begingroup\$ @SingleNegationElimination, From link you provided, it seems it supports 'insertion', and 'deletion' in O(logn). I think 'pop' and 'push' has different concept (and it is asked to perform in constant time). But this is a very interesting DS which I never seen it before. Thanks for the useful info :) \$\endgroup\$ – Mehrdad Aug 22 '15 at 15:41
6
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ It's not unheard of for pop to return void (e.g. this is the norm with C++ containers). Also, being allowed to pop an arbitrary element and not having to return anything allows for a simple implementation. \$\endgroup\$ – user14393 Aug 22 '15 at 10:59
  • \$\begingroup\$ @Hurkyl, but it does make more sense to let the pop return a value, and then rather choose to ignore it, instead of needing to create a new function in those cases where you actually want to have something returned. \$\endgroup\$ – holroy Aug 22 '15 at 11:12
  • 1
    \$\begingroup\$ @Hurkyl But if pop() returns void, then I would expect there to be a peek() method available. \$\endgroup\$ – 200_success Aug 22 '15 at 16:11
  • \$\begingroup\$ @200: Often true, but not required. I'm not speaking entirely hypothetically here; I've actually had occasion to use a "container" whose means of access was limited enough that you could use O(1) memory to store essentially arbitrarily many elements (and be able to remove them!). Naturally, such a structure cannot have a general "give me back an element" method. \$\endgroup\$ – user14393 Aug 22 '15 at 19:24
  • \$\begingroup\$ @Hurkyl When the changes needed to make it a more useful data structure are so easy, it makes little sense not to return something from pop(). \$\endgroup\$ – 200_success Aug 22 '15 at 20:35
3
\$\begingroup\$

The biggest thing missing is comments.

  • Someone who hasn't seen your code before (or even you six months in the future after you've had time to forget about it) who has reason to look at your code (e.g. to fix a bug or to add new features) would have to spend a fair amount of time trying to figure out how you're using the internal data structures. You should add some comments explaining what you're doing and why it works.

  • The comment // Pop method bad for two reasons. Not only is it redundant (the method name already tells you that it's the pop method), but it's ambiguous; there are a variety of things pop might do, such as pop any, FIFO, LIFO, pop max, or pop min. The comment here should state what kind of pop this method is doing.

\$\endgroup\$
3
\$\begingroup\$

Excellent comments so far, so this is more about the basic design. I think the source of complexity in this class, even though it's not terribly complex, is the concurrent maintenance of three stacks. It would in my opinion increase clarity to use a single stack instead of three. This requires introducing a class to represent the cumulative state.

I also recommend that you make member fields final unless you need to modify them.

import java.util.ArrayDeque;
public class MinMaxStack {

    private final ArrayDeque<MinMaxState> stack = new ArrayDeque<>();

    private final static class MinMaxState {

        final int min, max, value;

        MinMaxState(int newValue, MinMaxState previous) {
            value = newValue;
            if (previous == null) {
                min = max = newValue;
            } else {
                min = Math.min(newValue, previous.min);
                max = Math.max(newValue, previous.max);
            }
        }
    }

    public int min() {
        requireNonEmpty();
        return stack.peek().min;
    }

    public int max() {
        requireNonEmpty();
        return stack.peek().max;
    }

    public void push(int value) {
        stack.push(new MinMaxState(value, stack.peek()));
    }

    public int pop() {
        requireNonEmpty();
        return stack.pop().value;
    }

    private void requireNonEmpty() {
        if (stack.isEmpty())
            throw new NoSuchElementException("The stack is empty.");
    }
}
\$\endgroup\$
2
\$\begingroup\$

In addition to the valuable answer made by 200_Success, I would like to add a few comments:

  • Even though I like your consistency with the braces, the code feels jammed up in places. EspeciallyWithinIfStatementsLike if(!maxStack.isEmpty()){ and }else{. Try opening it up with if (!maxStack.isEmpty()) { and } else {
  • Try to avoid single letter variables, unless in tight loops, i.e. rename the variables: s and k
  • Rename the entire class MyDS isn't intuitive and readable
  • Decide which type you want to use, int or Integer. Or Possibly make the whole class into a general template allowing for other types as well
  • A little on the side: If you add another function to remove items other than pop(), allowing for removal within the stack, your current logic wouldn't handle that. Consider a push of the following values: 100, 80, 90 and then a removal of 80 which would make min() return 100 (if not the logic is corrected when inserting the new function)
\$\endgroup\$
  • \$\begingroup\$ It is consistently using int. It's just that Stack only works with boxed types. \$\endgroup\$ – 200_success Aug 22 '15 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.