Building a Stack
There is nothing better than a stack of buttermilk pancakes to calm that early morning sweet tooth. Now, I normally slice through the whole stack and eat a bit from each pancake at once but lets pretend, for the sake of this discussion, that I am a reasonable person that eats a single pancake at a time. To do so, the top most pancake would be pulled off of the stack and consumed followed by the next pancake on top. This is the same way the linear data structure of a stack works. In the data structure world, this methodology is referred to as “last in first out”.
In the pancake analogy, each pancake can be considered a node that contains some data and points the the next node. This node structure sounds very similar to the
Node class create in the previous article Building a Singly Linked List, so let's pull that code.
It is noted that the
next property of this
Node class defaults to
null so it doesn't have to be defined at instantiation. From this point we need to create an overall
Stack class which defines properties such as which node is on the
top of the stack as well as several functions including
To start, the
Stack class needs to have a property that points to the top
Node. This property should default to
null as the Stack will likely start empty.
From this point we can start adding functions to populate and remove data to the
Stack as well as a few helper utility functions.
Borrowing the function naming from standard arrays,
push will add data to the top of the
Stack. To do this, a new
Node will be created, it’s next property will be set to the current
top node, and then the current node will be set to the
Once again, similar to the array function naming the
pop will remove the last node in the
Stack which in this case is the
top. The node being removed will be provided as a return value. The
top property of the
Stack must also be updated to represent the new state.
pop functions in place the
Stack class is completely functional but some utility functions would be helpful. The
peek function will simply return the
top node without mutating the
isEmpty function will check if Stack itself is empty or not. This leverages the
peek function and compares it return against
null and then returns a boolean.
Node class successfully implement the linear data structure know as a stack but there is room for improvement. For example it would be ideal if the
Node class was nested inside the
Stack class and was only accessible by the Stack class itself. That is, an instance of
Stack should not have access to the
Node class. Another potential source of errors is that the user has direct access to the
top property of
Stack and could therefore overwrite it manually resulting in erroneous behavior of the class functions. Finally, the data types for the
It is always good practice to take a second look at your code and see what else could be refactored and improved. Keep a look out for a future article which will address some of these concerns! In the meantime, check out a very similar data structure in Building a Queue.