Building a Stack Class in Java
A stack is a fundamental data structure in programming. It behaves like a data container where new items are added to the top of the stack and you only have access to last one added (most top item).
A definition by Oracle (source)
The Stack class represents a last-in-first-out (LIFO) stack of objects. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
Today, we try to recreate this data structure in Java with our own generic class and interface. The class is generic in order to store different data types. It should provide the following six methods:
- push (to add a new item to the top)
- pop (to remove the most top item)
- peek (to get the most top item)
- isEmpty (to check whether the stack is empty)
- size (to get the size of the stack)
- search (to search for objects)
Interface: Stackable.java
Let’s start with the interface for our stack. The interface specifies which methods have to be implemented inside the stack class. We declare the six methods I just mentioned before.
The <T> construct marks the interface as generic. In this case T can be any data type. For example Integer or String.
Class: Stack.java
As next, we create the stack class. Here we need two private attributes: previous and value.
previous is a reference to the item that is located below the current instance in the stack order (the underlying item). This results in a recursive implementation.
The value attribute contains the value that the current instance of stack stores. It can be any data type.
Moreover, there are multiple constructors we need later on. Since the class is generic we need here the <T> construct as well.
Method: push
This method pushes an item onto the top of the stack. Therefor, we set the current instance of stack to our previous one and store the new value.
previous references now to our old stack instance.
Method: pop
This method removes the item at the stack’s top and returns its value.
First of all we store the current value in a temporary variable because it gets overwritten and we need to return it later.
Afterwards, we set the current value to the one from our previous stack item. Moreover, we reference the currentprevious attribute to the previous item of the underlying item.
At the end, we return the removed value.
Method: peek
This method looks at the value of the item at the top of the stack and returns it. Here we just need to return this.value.
Method: isEmpty
This method tests if the stack is empty. Since the last stack item has no reference to another (underlying) item, we just need to check if the previous item is null.
Method: size
This method returns number of items in our stack. Here, we recursively count until the last item is reached.
Method: search
This method returns the 1-based position where an item is on the stack. Therefor, we loop over all our stack items and increase a counter until the one that equals the target item is reached. Last but not least we return the counter.
If there is no match, -1 is returned.
Try it out!
Let’s create a new instance of our stack class and try it out.
That’s it! Here you can find a GitHub Gist including the complete code.
