How to test a stack of n elements?

Question

Hi guys,

This seems like a silly question but I would really like your comments and would like to validate my tester thinking..

I can think of following test cases:
1) Pop element from empty stack should return error
2) Push n+1 elements in stack should return error during insertion of n+1th element
3) validate empty,full and top functions of stack.
4) if stack is used in multithreaded environment , make sure it is synchronized.
5) validate stack functionality: 
    push element (x)
    pop element: it should return x

Comments?

If this question is asked in an interview, what could be the possible answers? Is my answer valid enough?

Answer 1

Looks fine to me. Just make sure when you're validating the functionality, that you make sure multiple items come back in the right order, top works correctly after each pop and push, and it properly reports empty after you pop the last element.

Answer 2

I would also push the numbers 101 through 100+n then pop them all off to ensure they come off in reverse order (will catch sequencing problems such as "sometimes pop will get the second element rather than the first").

The following sequence should test all but your multithreaded requirement thoroughly:

• empty gives true.
• full gives false.
• pop gives error.
• top gives error (I assume this is a peek operation).
• for n = 101 to 100+sz-1:
  • push n works.
  • top gives n.
  • empty gives false.
  • full gives false.
• push 100+sz works.
• top gives 100+sz.
• empty gives false.
• full gives true.
• push 99 gives error.
• top gives 100+sz.
• empty gives false.
• full gives true.
• for n = 100+sz down to 102:
  • pop gives n.
  • top gives n - 1.
  • empty gives false.
  • full gives false.
• pop gives 101.
• top gives error.
• empty gives true.
• full gives false.
• pop gives error.

Answer 3

I would enhance (5) to read: push N distinct elements, pop N times and ensure the same elements are retrieved in reverse order

It might also be prudent to check that this words for elements from a sorted list, a reverse-sorted list, and an unsorted list.

Answer 4

I think you got everything covered, except maybe checking in 3) that the n elements pushed before are how you'd expect them. This will catch erroneous boundary condition checking, i.e. checking whether the stack is full only after writing the new element.

Additionally, I'd group your test cases differently and test top,pop,push,empty,full for each:

1. Empty Stack
2. Stack with one element*
3. Stack with some elements, probably call pop/push twice or more often
4. Stack nearly full (n-1 elements)*
5. Full stack

*Not necessary, but could be a corner case.

Answer 5

Do you want to get really neurotic about this? It's always interesting to confirm the performance of data structures. A stack should have constant performance. So for each k in [0,n-1), you could push k elements, then push and pop a (k+1)st element 1e8 times, and make sure the times are comparable. I can imagine several brain dead implementations where element n-1 would take n times longer to push and pop than element 0.

Answer 6

If there are any other methods apart from push and pop (eg length and top), test those too.

For top, test:

• empty stack (error)
• full stack (nth element)
• repeated calls (should return the same value as the element isn't being removed)

For length, test on:

• empty stack
• full stack
• behaviour post push (increment by one)
• post pop (decrement by one)
• behavior post top (no change)
• post pop on empty stack (zero)
• post push on full stack (n).

Answer 7

Multithreading: it would be good to write a test in which at least 3 threads hammer on the data structure simultaneously. And make sure you run it on a multiprocessor box, so you get true concurrency, not just time slicing.

And don't forget the case where:

if( !stack.Empty )
{
    // oops, another thread emptied the stack and now this call will throw an error:
    stack.Pop();
}

Answer 8

Okay from the comments

Testing of stack may be divided in

Functionality testing
Performance testing
Security testing: if data pushed onto stack are strings , then we may need to check for buffer overflows