Building a simple Stack in Java. (Part 1)- 6 mins
Starting yesterday and continuing today me and Mike worked on some fun exercises with Java and one of them included building a Stack. The exercises can be found here.
The definition of a Stack is as follows:
A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.
A basic implementation of a stack is also called a LIFO. This means that the (L)ast item that goes (I)n, is the (F)irst one that comes (O)ut. A good example of this is explained in the link above. When you are using a browser and you click a link, the link gets added (push) to the stack. When you want to revisit the previous link and you click the back button, it pops the link from the stack. Last In, First Out. Therefore the main two operations of a Stack are push and pop.
In this post I’ll show how we started by implementing the following three methods:
- push(String item)
The first test looked like this:
To make it green:
This is probably the most “degenerate” case as Uncle Bob would call it. The implementation is very simple and definitely not what we really want but it will make the test pass and for now that’s all that matters.
The next test is the following:
For this one to pass and not break the first test, I introduced a
size attribute. Initially I put a conditional but Mike corrected me by saying if the conditional can be avoided then it should as it adds complexity since with a conditional in this situation would create a two way stream. A good blog post that relates to this point can be found here by Uncle Bob. The code for the second test to pass then looks like this:
Next up was the test checking that a new stack starts with a size of zero. I can tell what you’re thinking and you’re right; this will pass out of the box although the reason for this test is to simply create a method that returns the size without touching the attribute itself:
Code to get this green:
Then we check if we can pop an item from the stack:
Again the least amount of code that could get this to pass:
Now you might think I’m taking too many small steps and you are right. I’m deliberately taking these steps however since writing the least amount of code has significant advantages. There’s a saying in the programming community that says The best code is no code at all. This can lead to surprising results. It’s amazing how little code you can write and get things to work by following this principle and we did have a moment like that with Mike while doing the above. Another benefit is the simplicity that comes out of following simple choices vs adding complexity that might not even be necessary.
The next test was the one that we thought would force us to actually put some more smart code and it looked like this:
Of course with us being lazy and following the least code principle this was the resulting code to make the above test looked like this:
Of course a small change was necessary as the above almost feels like cheating since we would be passing longer strings and not just string numerals:
And of course now the test will brake. In the next part I will show how the actual implementation looked like and explain it a bit more as it took me a while to wrap my head around. I’ll explain how the stack works a bit more especially with Linked Lists using some diagrams as well. Hopefully there’s plenty food for thought here until tomorrow.