Stack Data Structure Tutorial - What is a Stack?

Key Takeaways

so what is a stack the easiest way to think of it a stack is like a stack of plates if you have a table say this one right here when you start stacking plates you're gonna put them on top of each other so you have a plate here you have another one and then you keep adding a few more now the last plate that you stack so the one on top is actually always gonna be the first one you take off so this fall is what's known as Philo first in last out the first plate that we put was actually this one and it's gonna be the last plate that we take off the stack because we need to take off plates two three and four before we can access that one and if you understand this you understand stacks they're very straightforward so now let's talk about some of the methods involved with a stack and how this actually works in kind your computer's memory and all of that now firstly just like use all these methods on the side follow what's known as constant time and that means doing this does not change based on how many items you have in your stack so it's gonna happen pretty well instantly in the computer and if you have 10,000 item integers in your stack it's gonna take as much time as if you have two or three items in your stack so that's the way to think about constant time so let me just erase this no will move on to these methods so to add something to our stack we can use one of two methods now I'm just putting the over here because this means that they can be named something differently but we can use what's known as put or push now the standard convention is usually push and this means push an item on top of a stack just like if you're gonna push a new plate on top of the stack of plates so if we go here and we say push and we push maybe the item 7 onto our stack what's gonna happen is we're gonna come in from one side because our stack is one ended as opposed to two ended like our queue that we talked about previously we're gonna come up through the front which is also at the back because it's one side we're gonna put our item seven at the very bottom of our stack well in this case there's only one item but again it's still gonna be the bottom now if we go and we decide to push another item onto her stack let's do that and let's see what happens when we push let's say the item six onto our stack well six is gonna come in through the front but it's also coming in through the back because there's only one end and well we're gonna get sick on top of seven and that is how we push or add items onto the stack and notice that they well stack and that the most recent item you added is always gonna be at what we call the top of the stack alright so now that we've done that let's talk about how we can get an item off of the stack so if we want to get and remove an item from our stack we can use one of two methods yet or pump again these just really depend on what you're naming your methods they do the same thing so if we decide to pop an item off our stack what actually ends up happening as we go to the very top of our stack so the last item we added on which in this case is six and we bring it we delete it and we bring it and return it to wherever pop was called so what's actually happening here is let's say you know we go maybe something like x equals pump well now X is actually gonna be equal to six because that's what we popped off of the stack and we're gonna remove 6 from our stack entirely now if we do pump again what will happen is we will now be removing 7 because 6 was already removed so now 7 is the highest item on the stack or the last one to go in so it's now coming out again following this first in last out right and that is kind of the principle to go by with these stacks so let's go back and now let's look at another method so let's pretend that instead of removing an item from our stack we actually just want to look at what the top item is well a lot of times we want to do that and this is where we can use what's known as peek or front so if we want to check what the front item in our stack is at the highest item the most recent item to go on we can use peek or front and this is gonna look and tell us what the item is without actually removing it so if I call front here what's gonna happen is we're gonna look we're gonna see 7 is there and we're gonna return 7 to wherever we called front so it's gonna go 7 is gonna go here but we're not gonna remove it from the stack again it's a very useful thing that we often want often times we want to do all right so that is how you kind of do that we can use peek front whatever we're calling it again for that now the last two methods to talk about our is empty n is full these do exactly what they say they're going to tell us if the stack is empty or if the stack is full now the reason we need these methods is because if we try to pop an item or peek an item and their stack is empty we're gonna run into an error so oftentimes we need to check by using an if statement and saying if not stack is empty right then we can go ahead and we can do that pop or we can do that peek that we want to do now this applies the same to is full sometimes depending on what language you're programming in and how you implement a stack you may have a limit on the amount of items that can go into the stack so before you push a new item onto the stack you need to make sure that there's enough room for it and that it can accept it right just like if you try to put a plate too high on a pile of plates it's gonna fall over if it can't hold that right I'm just a basic example so it means that is kind of how each stack works so now I want to demonstrate the use of stacks an example where I want to use two stacks to simulate a queue now if you haven't watched my video on queue I recommend that you do but essentially a queue is kind of the opposite of a stack where rather than the first item in is the last item out the first item in is the first item out so you can see our queue is on this side here and when I add items the first item to be added will be the first item to be taken off when we're using those push pop operations or those debts and on Q&D queue and all of that that I've talked about previously anyways thank for yourself for a second how can I use two stacks to simulate a queue now once you're done thinking I'm gonna explain this example in detail so let's start by just creating and adding a few things to our stack so we're gonna turn this into a queue in just a second but let's add a few items so let's add three two and one actually that's kind of weird numbers to add in that order we'll do like five seven and negative four in this order so starting with five so let's add that to stack one so we know that when we add items and we stack them on here we push them we have five we're gonna have seven and then we're gonna have negative four and since negative four was the last item it's gonna be the first one that we take off of stack one okay so that's great but that doesn't really work for our cube does it if we add our queue what our queue would look like would be five seven negative four we're five right here is gonna be the first item to come off so how do we use this other stack to do that well this is how we do it when we add items so remove these items from here now we're gonna follow a little bit of a different procedure we're gonna use this second stack we're gonna start by taking all the items in stack one and putting them onto stack two so pushing them off or sorry popping them off stack one and pushing them to stack two so in this case it's empty so all we actually end up doing is just putting this first item that we want to add here which is five on to stack one now this works as our cube because well there's only one item so obviously that's gonna be the item we take off but now let's move to the next example where we have seven so how do we now make sure that seven since it's added after five isn't gonna be taken off first because we just put seven and we start taking it off well then seven is gonna get taken off first what we actually do is we move all the items from stack one on to stack two so we put five which is this right here on to stack - I know I'm butchering writing five and we erase five from this stack we then take seven which we want here and we push it onto stack one like this now we take all the items from stack two and we re stack them onto stack one so we pop them off here and push them back and now when we do that we get five here and well we can erase this from stack two is this is just kind of our intermediate stack all right that's great pretty simple for two items now what about three we'll watch this same process as before we take five and we stack it on to stack two so we pop off the top of this and push on to the top of this then seven same thing seven goes here now we can erase these from here they no longer exist we take our new item which is negative four now and we put negative four on to our stack which is stack one now from stack two we take all these items and we put them back onto stack one so when we do that we're gonna get these in reverse which means we're gonna get seven and five and now you can see this is following the queue order so when I want to take items off and I'll just erase them from here to make sure no one's confused we start by taking five then seven then negative four and every time we add an item we simply take all the items off stack one put them on a temporary stack - just by popping and pushing and then we add that item to stack one and then pop and push back off the temporary stack so we get in the correct order so the new item you add will all be at the end of the stack and be the last item to take off which follows FIFO which is the way that our cubes work first-in first-out so it means that has been the video on stacks I hope you guys learned a little bit if you did make sure you leave a like and subscribe and I will see you guys again in the next data structures video