Sorry for taking the time, I know I said I’ll post a day-after-day guide to algorithms and data structures but you’ll have to excuse me, I’ve been ill.
So on day #1 we talked about linked lists. If you don’t remember what linked lists are you might want to go back to previous post and go over it before diving into today’s guide since we’re going to talk about the stack and how to implement it using linked lists.
First things first:
In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.
But what is so special about the stack? what differentiates the stack from other data types? The stack has a special way to store and organize data. It follows a simple “rule” called LIFO (Last In First Out). This means that the item most recently added to the stack will be the first handed back from the collection.
I find that the easiest way to understand what is the stack and how it works is by visualizing a pile of pancakes on a plate one on top of the other:
Let’s just say, for argue’s sake that I eat pancakes. And let’s just say that if I was served a plate like this I would eat the pancakes one by one. I were to eat them as I said I would have to start with the top one, otherwise the entire pile will ruin and all of these beautiful diabetes-causing treats would become a diabetes-causing mess! What I mean is, that the last pancake put on top of the pile is the first one I’d have to eat and the same goes with stacks (no I did not start a data-structure diet where I only eat ints, I need my beef and veggies too!) the last item on the stack, aka the top of the stack will be the first to go.
The action of adding another item to the stack is called “push” and the action of taking out the top item from the stack is called “pop”. So adding more pancakes to the pile can be done with “push”ing pancakes to the plate, and eating the top one is done by “pop”ping the top one. pretty simple isn’t it?
On the previous post we’ve learned how a linked list is a series of nodes linked together and do a chain – we can use this type of structure to help build our stack. The stack would contain a linked list who’s head node pointed to the most recently added (top) item.
Let’s begin with creating a linked list:
Pushing to the list is basically just adding a new node to the beginning of the list. In order to do that we first need to create a new item, link the item to point to the head of our list and then set the head of the list to be our new item. This way, we will create a new head to the list with a new value and keep the rest of the list linked to it!
I am going to use a “pop” function and since we’re using C here, we’re gonna have to pass a pointer to the pointer variable (double pointer yayyy) so we could modify the pointer itself:
Using this function we can always add a new item to the stack. Now how about some popping???
Funny isn’t it?
In order to remove the last item and pop it from the stack we need to do exactly the opposite! I’ll explain; First we need to take the next item that the head is pointing to and save it, then “free” the head item and then all that’s left is to set the head to be the next item we’ve stored on the side.
That’s pretty much it.
But why was I using a linked list and not an array for instance?
The main advantage a linked list has over an array is that it has no size limit and on modern days computers we can add billions and trillions of nodes without having to think about size and memory consumption (ALWAYS THINK ABOUT MEMORY CONSUMPTION NO MATTER WHAT YOU DO!). Also, it’s a very straight forward way to implement a stack – an array for example would require bounds checking to make sure that a “push” didn’t cause the item to exceed the array’s bounds. However, there are some downsides to this approach, and many of them has to do with performance and scalability; like whenever a new item is being pushed to the stack, a memory allocation occurs every time. This can end up causing undesirable performance characteristics in high performance systems.
Hope you found this article to be educating 😉