You probably heard about “Stack Overflow”.
Yes, it’s also the name of one of the most popular websites for finding/asking questions. But I’m not talking about that. (=
What the hell is a stack?
I’ll try to keep this as simple as possible so everyone can understand it. At a very high level, you can think of a stack as a Last In, First Out data structure! Wow, now we have another problem.
What is a data structure?
In the simplest terms, a data structure is a combination of AND | OR operations between symbols. String = (Empty) OR (A AND String) Huh? Let me explain it. “Narciss” is obviously a string, right? “arciss” is also a string, right? And the ‘N’ is a letter. Does that make sense? So, Narciss = ‘N’ + “arciss” -> String = Letter AND String arciss = ‘a’ + “rciss” -> String = Letter AND String rciss = ‘r’ + “ciss” -> String = Letter AND String ciss = ‘c’ + “iss” -> String = Letter AND String iss = ‘i’ + “ss” -> String = Letter AND String ss = ‘s’ + ‘s’ -> String = Letter AND String
Wait a minute, ‘s’ is a letter and also ‘s’ is a string? Are you high, Danial?
Yes! Do you remember how I defined a string?
String = (Empty) OR (A AND String)
Exactly, now let me redefine “ss”:
ss = ‘s’ + ‘s’ -> String = Letter AND String
ss = ‘s’ + ‘s’ -> String = Letter AND (Letter AND Empty)
Now it makes more sense, right?
Ok, now we know what a data structure is (I defined the string data structure in a recursive form. I had a blog post about recursion, but I’m not sure on which platform. If you search, you’ll find it though :D).
Ok, let’s get back to the stack.
A stack is a Last In - First Out data structure, which means if you have some kind of magic powers (mathematicians always have) and you are the last person to arrive to buy the new iPhone and you see a long queue of people waiting for the release, you can change that queue to a stack. This means you are the first person to buy the iPhone, because a stack is Last In - First Out!
Why do we need a stack?
Good question! Generally, we use a stack for problems with hierarchical nature and a queue for problems with sequential nature. By the way, don’t get confused, I’m writing this in mathematical language and we are “programming language” agnostic. You can use a Python queue as a stack or vice versa. The fact is if you have two operations add and remove and they both work on one end of your ordered structure, we call it a stack. If they work on two different ends of your ordered structure, we call it a queue. (You can use anything as your ordered structure, list, array, sequence, strings, whatever).
Again, let me clear this up for you. Do not care about fancy names in the IT space, they are just names. For example, pop-sub vs queue vs event stream. Don’t bother with these things, they are all talking about a problem with sequential order. For your first steps, try to understand the main logical concept behind these.
Example of a Stack:
Let’s say we want to solve this:
3 (4 + 4(8 + 2(5.2))) It’s very easy for humans because we have an eagle-eye view on this, we see the entire problem. But that’s not the case for a computer which can only read this as a string. This data is not a normal string in math, that parenthesis can change the order of execution, which means this data has a hierarchical nature. See:
What we see: 2 * 5 = 10 then 2 * 10 = 20 then 8 + 20 = 28 then 4 * 28 = 112 then 4 + 112 = 116 and finally 3 * 116 = 348
What computers see:
['3', '(', '4', '+', '4', '(', '8', '+', '2', '(', '5', '*', '2', ')', ')', ')']
In this case, you cannot use a queue because you need to calculate the inner parenthesis first and then come back to the outer operations. So each time you see a ”(”, you need to go down the stack, and when you see a ”)”, you need to come back up in the stack, like this:
Humm! I think now you understand the stack! Let me know if you have any questions, my email ID: [email protected]