Code Katas: The Stack

I explored in my previous post the idea of a coding kata. I expressed that I did not think just any exercise was worthy of being called a kata, because not all exercises are worth of practicing more than a few times. But there are concepts in computer science that are worth repeating again and again, to become a better programmer.

What brought this first to my attention was Uncle Bob’s screencast on the Stack kata where he demonstrated Test Driven Development implementing the Stack data structure.

As a kata, it’s beautiful. It’s a fundamental concept that could be implemented in many different ways. Also, interestingly, it would be implemented differently in different languages. So there is a lot to explore here.

Before putting forward the tests Martin used, I’ll recap what a Stack is.

A stack works like a stack of plates.

  • The first items into the stack are the last items to be taken off.
  • If you have a limit to how many plates will fit on your shelf, you can’t fill it too high.
  • You can’t remove from a stack if it’s empty.

That’s basically it.

Here are the tests that Uncle Bob lays out in his screencast.

  1. Can create Stack object.
  2. Newly created stacks should be empty.
  3. After one push, stack size should be one.
  4. After one push and one pop, should be empty.
  5. When pushed passed limit, stack overflows.
  6. When popped passed limit, stack underflows.
  7. When two values are pushed then one is popped, size is one.
  8. When one is pushed one is popped.
  9. When one and two are pushed two and one are popped.
  10. When creating stack with negative size, should through IllegalCapacity.
  11. When creating stack with zero capacity, any push should overflow.
  12. When one is pushed, one is on top.
  13. When stack is empty, top throws empty.
  14. With zero capacity stack, top throws empty.
  15. Given stack with one two pushed, find one and two.
  16. Given a stack with no two, find two returns null.

In my implementation and the tests I used, I ignored everything relating to capacity (5,10,11,14) because I implemented my stack in JavaScript. I could implement overflows, but JavaScript does not require a capacity when instantiating an array.

Want to give it a shot yourself? Post your implementation in the comments.