Welcome back, daredevils! I see you like to live dangerously.
If you’ve no idea about I am talking about, you should check out this post before reading this article.
The goal of this data structures series is to ruin your life(for good) by thinking and applying data structures to real life setting. It will not introduce you to the practical world of programming, but a mastery of the concepts will provide a start toward understanding the nature of computation.
Let me start this series with simplest of all yet among the most important data structure – ‘Stacks’. In recent times, this word is being used everywhere. Be it about companies looking for full stack developers to startups sharing their tech stacks.
So what is a stack, exactly?
Before I proceed with the explanation, let me give a fair warning. This article is not advised for people who are on dieting.
Food appears in many of our examples for simple reasons:
- First, food is easier to visualize than complex codes & abstract symbols.
- Second, I want to provide you with a little distraction. They can get on your nerve at times, and a little distraction will help you keep your sanity.
** Prerequisite For This Article** :
The reader must be comfortable reading English and must be pro at controlling food cravings.
What the heck is Stack?
Although the word has different meanings — in programming, the stack is a collection of objects(data) that are inserted( pushed ) and removed( popped ) according to the last-in, first-out ( LIFO ) principle.
I hear you say this was a bit complicated. Don’t worry, brace yourself for (food) example to simply this.
Let’s talk about Pringles tube today. If you observe closely, Pringles tube is nothing but a stack of potato chips. The last chip to go in the tube during packaging is the first chip to go in our stomach while eating.
You simply can’t have chips at the bottom of the potato tube before eating the chips present at the top as the tube has a single opening at the top.
You see what I did there?
Well, resisted the urge for having the Chips and taught you crucial concepts of Stacks.
If you go back and see the definition of the stack earlier, you’ll see I have bolded few terms push, pop and LIFO. Let’s try to connect the dots now.
- Additions (push) & Removals(pop)
Just like we add(push) and remove chips(pop) from the top of the Pringles tube, in Stacks you add and remove just from one end i.e. from the top only.
- Last item In is the First item Out (LIFO)
Just like you can’t have chips at the bottom without finishing the upper ones, the item which was pushed in the stack last will be the first one to be taken out.
The fundamental operations of Stack are as follows:
- push(element) — Adding new elements at the top of the stack
- pop()— Removing/Returning element from the top of the stacks
- peek()/top() — Returns a reference to the top element of the stack
- is_empty() — Returns Boolean true is the stack has no elements
- len(stack)– Returns the number of elements in the stack.
Yes, Yes…I hear you say I just explained first two methods to you.
Let’s take another example to understand rest of them.
Say you have a stack of pancakes(an organized pile, one on top of another).
- Peek/top :
One should eat one pancake at a time. Any more than that at once, and you don’t get enough syrup on them.
So, you’ll use peek/top function on the stack to get the topmost pancake.
- Is_empty :
I am sure you are wondering who eats one pancake at a time. Together (stacked), with a layer of syrup applied to the top of each one is a proper way to eat this stack of cakes. Let’s say I ate the entire pancake in one go. Now, if someone asks me is there any pancake left, I’ll turn my head to say no.
Similarly, this is_empty function tells us the status of elements in the stack. If the stack is empty, it will return true otherwise false.
- len(stack) :
If I call this function on our pancake stack, it will merely return a number of pancakes (5 in our case).
And here we are. At the bottom of the stack.
There are two ways to implement a stack:
Like I mentioned at the beginning of the article, this article aimed at covering concepts of the stack. I will cover the code implementation with this data structures in future articles.
That being said you can go ahead and get your bellies full now.
See you soon!
Thanks for reading! If you liked this post, you can check out my other writings here or please consider entering your email here if you’d like to be added to my once-weekly email list or follow me on Twitter