Stack with 'getMinimum' operation

Question

Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.

Looking for code review, optimizations, best practices.

    public class StackMinimum<T>{
       /*
        * Composition triumphs over inheritance :)
        */
       private final Stack<T> stack1 = new Stack<T>();
       private final Stack<T> stack2 = new Stack<T>();

       public void push(T item) {
           stack1.push(item);
           if (stack2.isEmpty() || ((Comparable<T>) item).compareTo(stack2.peek()) < 0) {
               stack2.push(item);
           }
        }

        public T pop() {
            T item = stack1.pop();
            if (item.equals(stack2.peek())) {
                stack2.pop();
            }
            return item;
        }

        public T peek() {
            return stack1.peek();
        }

        public int size() {
            return stack1.size();
        }

        public T getMinimum () {
            return stack2.peek();
        }

        public boolean isEmpty() {
            return stack1.isEmpty();
        }
    }


public class StackMinimumTest {

    @Test
    public void test() {
        StackMinimum<Integer> stack1 = new StackMinimum<Integer>();
        stack1.push(1);
        stack1.push(2);
        stack1.push(3);

        assertEquals(1, (int)stack1.getMinimum());

        stack1.push(-1);
        assertEquals(-1, (int)stack1.getMinimum());

        stack1.pop();
        assertEquals(1, (int)stack1.getMinimum());

        while(!stack1.isEmpty()) {
            assertEquals(1, (int)stack1.getMinimum());
            stack1.pop();
        }
    }
}

Answer 1

You have a bug: .getMinimum() loses track if you push the same new minimum value twice.

You should use both inheritance and composition.

Use inheritance for the "main" stack, because your data structure is a stack — one with an extra feature. That gives you the read-only operations .peek(), .size(), and .isEmpty() for free.

Use composition for the "minimum" stack, as you have currently done.

Answer 2

1. I would rename stack1 to delegate and stack2 to minimumStack or something similar to express their purpose and make the code easier to understand.

2. I would use ObjectUtils.min (or max?) instead of

   ((Comparable<T>) item).compareTo(stack2.peek()) < 0)
   

   compareTo always forces me to check the javadoc to figure out what does its return value mean.

3. Having a loop in the test method is a test smell: Conditional Test Logic

4. The test does not cover the peek nor the size method.

Answer 3

It looks very good for me, you can use the extend keyword on generics to insure type safety and to avoid unnecessary casts. And this is called a Bounded type

class StackMinimum<T extends Comparable>{
      public void push(T item) {
       stack1.push(item);
       // to need for the cast here
       if (stack2.isEmpty() || item.compareTo(stack2.peek()) < 0) {
           stack2.push(item);
       }
    }
}

Only Comparable types will be welcomed in your stack

Answer 4

As others have noted, Stack extends Vector. As such Stack is a List. The easiest and most readable way to add getMinimum() would be to do this :

import java.util.Collections;
import java.util.Stack;

public class SpecialStack<T extends Comparable<? super T>> extends Stack<T> {

    public T getMinimum() {
        return Collections.min(this);
    }
}

I'm guessing this is homework. As such, you can probably not get around using Stack for this exercise, but note that Stack, as a subclass of Vector, carries synchronized overhead, which in most cases you won't need. So for real life purposes you're better off using ArrayDeque, as even Stack's javadoc suggests itself.