Stack data structure unit testing

Question

I have this contract:

public interface Stack<T> { void push(T object); T pop(); int size(); } 

I am curious what you think about my test of the size() and pop() in order to prevent bugs (underlying data structure in not being cleaned) in implementation like below:

Implementation:

public class StackImpl implements Stack<Object> { private int size; private Object data[]; @Override public void push(Object object) { data[size] = object; size++; } @Override public Object pop() { --size; return data[size]; } @Override public int size() { return size; } } 

Test:

public class StackTest { @Test public void pushTwoObjectsToEmtyStackCheckThatSizeIsTwo() { pushObjectsInOrder(OBJECT_A, OBJECT_B); assertEquals(2, stack.size()); } @Test public void pushTwoObjectToEmptyStackAndPopTheSameObjectsInReversedOrder() { pushObjectsInOrder(OBJECT_A, OBJECT_B); assertEquals(OBJECT_B, stack.pop()); assertEquals(OBJECT_A, stack.pop()); } @Test(expected=IllegalArgumentException.class) public void stackDoesntAcceptNullAndThrowExcpetion() { stack.push(null); } @Before public void setUp() throws Exception { stack = new StackImpl(); } private void pushObjectsInOrder(Object... objects) { for (Object object : objects) { stack.push(object); } } private static final Object OBJECT_A = new Object(); private static final Object OBJECT_B = new Object(); private Stack<Object> stack; } 

I'd like to not focus too much on the implementation itself, like whether it should be List or array etc. Assume that you defined interface and going to give to implement it to other guy. Since you defined the contract you are the one who writes a unit test.

Answer 1

Here are some tests I'd perform at the very least. There may be more you'd want:

1. Create an empty Stack. Test that its size is 0.
2. Push an element onto the stack. Test that its size is now 1.
3. Push another element onto the stack. Test that its size is now 2.
4. Pop an element from the stack. Test that it matches the 2nd pushed value. Check that the size of the stack is now 1.
5. Pop an element from the stack. Test that it matches the 1st pushed value. Check that the size of the stack is 0.
6. Attempt to pop an element from the stack. You should receive an ArrayIndexOutOfBounds exception.

Answer 2

@PhilWright made some good points. I would add:

• Popping element from an empty stack should throw java.util.EmptyStackException
• Test for memory leaks. Since the Stack is in charge of managing its own memory, this is a real concern. A common memory leak in stack implementations is when removed elements are not nulled out correctly.

Here's one way to verify that pop cleans up after the removed object, based on @DavidHarkness' idea in comments, using a WeakReference:

@Test public void testPopCleansUpReference() { Object value = new Object(); WeakReference<Object> reference = new WeakReference<>(value); Stack<Object> stack = new StackImpl(); stack.push(value); value = null; stack.pop(); Runtime.getRuntime().gc(); assertNull(reference.get()); } 

The current implementation fails this test, because this implementation only decreases the size variable, the popped object remains inside the data array:

@Override public Object pop() { --size; return data[size]; } 

For the record, the fix is simple enough:

@Override public Object pop() { Object result = data[--size]; data[size] = null; return result; }