Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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();
        }
    }
}
share|improve this question
3  
+1 for : Composition triumphs over inheritance –  Sleiman Jneidi Jun 26 at 22:27
    
Use Generics. StackMinimum<T extends Comparable<T>>. Don't cast. –  Boris the Spider Jun 27 at 8:19
    
Currently the code is bugged. push 5, 3, 3, then pop, and it will report the minimum as 5. Or push 5, 5 then pop twice : EmptyStackException. –  bowmore Jun 27 at 15:17

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
3  
Unfortunately Stack extends Vector, so I guess you have to implement a lot of other methods (like remove) to keep its behavior consistent. –  palacsint Jun 26 at 23:46
2  
Good job spotting the .getMinimum() bug. Changing the < to <= will fix the bug (I think). –  The Dark Jun 27 at 1:29
    
That is the first thing that I noticed. Solution by TheDark works, but a simpler solution would be to always push with the minimum value. So pop will also always pop from minimum stack. –  justhalf Jun 27 at 8:07
  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.

share|improve this answer
    
I don't agree with introducing a (fairly weighty) dependency like commons lang for no gain. The return of compareTo is very well defined and has been since the dark ages. –  Boris the Spider Jun 27 at 8:18
    
@BoristheSpider: Yes, I can accept the first part. Anyway, it's just a single <dependency> with Maven. If it's an interview question it shows that the interviewee have some knowledge of the existing libraries (and probably don't reinvent the wheel). Finally, you can still create a similar method in your code to make it readable. I know that compareTo is quite old but this does not mean that anyone should memorize that (instead of focusing on business problems). Extracting out the comparison to a helper method (similar to min) would express the dev's intent and make maintenance easier. –  palacsint Jun 27 at 9:03
1  
Sure, completely agree with extracting if conditions into boolean methods. Just think there need to be more compelling reasons for including dependencies - although cheap to include with Maven, they have their own maintenance costs. –  Boris the Spider Jun 27 at 9:07

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

share|improve this answer
1  
Shouldn't this be Comparable<T>? –  codesparkle Jun 27 at 0:11
    
@codesparkle No, it shouldn't, the type is bounded to T where T is Comparable –  Sleiman Jneidi Jun 27 at 0:17
1  
Comparable is the raw usage of the generic interface Comparable<T>. The language specification says: The use of raw types is allowed only as a concession to compatibility of legacy code. The use of raw types in code written after the introduction of generics into the Java programming language is strongly discouraged. (emphasis mine) –  codesparkle Jun 27 at 0:28
    
Sorry, forgot the link to the JLS –  codesparkle Jun 27 at 0:36
    
This answer is close, but wrong. Raw types should never be used. –  Boris the Spider Jun 27 at 8:20

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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