In this module, I will be introducing the Stack data structure. I will build on knowledge explained in the linked list module of this course, so if you have not already read the linked list post, I encourage you to go there first.
Push & Pop
A stack is a collection in which data is added and removed in Last In First Out (LIFO) order, this means that the last item to enter the stack will be the first item to be removed. The best way to understand this is with an example, think of a stack of clean plates in a buffet.
Let’s imagine the stack of plates is empty, an employee gets a clean plate and puts it in the empty stack. In computer science, this operation is referred to as ‘pushing’ a new plate to the stack. Note, at this point, there is only a single plate on the stack and so this plate is also the top of the stack. Next, let’s imagine another clean plate is ‘pushed’ to the stack, this new plate is now at the top of the stack, this will continue to happen as the depth of the stack increases with every new plate.
A customer can ‘peek’ into the stack, viewing the top, and only the top, of the stack to determine if they want the plate that is on top of the stack. As a customer needs a plate, they walk up to the stack of plates and remove the top plate. In computer science, this operation is referred to as ‘Pop’. Note: the customer cannot choose the plate at the bottom of the stack, only to plate at the top.
Stack (Linked List)
We saw how a linked list is a series of nodes linked together in a chain, we can use this knowledge to help us make our stack. The stack would contain a linked list whose head points to the most recently added item or top of the stack. Say we push an integer to the stack…
Then we push another two integers, 2 & 3…
Next, we will pop an item from the stack, note we do not select the item to be popped…
This is because the top of the stack and therefore the 3 is the only option to be popped, the next none in the pop chain, 2, will be the new top of the stack.
Why use a LinkedList to implement a stack? Unlike an array, a linked list has no hard size, the stack can continue to grow and the data can continue to be maintained along with the increasing size. It's easy to implement and requires no bounds checking, however, every push does require its own memory allocation and each node has memory overhead which could be greater than the value being stored, this can result in undesirable performance issues down the track.
So far in this module, we’ve spent our time discussing the stack data structure. In the real world, however, it would be unlikely to come across many situations where you would create a linked list structure. Typically, you would use a language or framework that provides a linked list class which is already tested, performant and compatible with your application. Unless you have proven the need for your own implementation, I recommend using the ones provided in your given language/framework.