Stack Data Structure | JavaScript

[Music] hey what's going on guys so I've had a bunch of requests to do some videos on data structures and that's something that I've been wanting to do data structures algorithms things that really gets the gears going and gets you thinking like a programmer thinking in you know logical terms and it's good to know this stuff sometimes they'll ask you about this kind of thing on on interviews and if you start to get into like data intensive applications and algorithms you'll need to know this stuff so I figured it's a it's a good little playlist to start I already did a video on linked lists a few months ago and I'll add that to the playlist as well so today we're gonna look at stacks which are pretty simple it's a really simple concept I have a diagram here and you can think of the elements in the stack as kind of like a stack of books and you can only add and remove from the top so it's what's known as a last in first out data structure so the last item that's put in is the first item that's put out and the way that we do this is with a method called push and a method called pop now if you've been developing with JavaScript for any amount of time you probably know that arrays actually have prototype methods push and pop that do the same thing so what we're gonna do is create a class to create a stack and we're going to create our own push and pop methods instead of using the built-in array methods all right and I just have a diagram here of how push works very simple so we're just adding a data here just a1 adding it to the stack the next one is gonna get added on top of that on top of that and so on and then pop will take the top element off okay so five comes off four comes off and so on so it's pretty simple to wrap your head around so let's go ahead and and create this with a class okay and we're gonna have some other methods as well like I want to be able to to see if it's empty to see the size of the stack print out the values and the stack things like that so let's create our class I'm just gonna close that up so have a class class called stack and basically what I want to be able to do is initialize a variable to our class so create a stack object and then we'll have methods like push so we'll be able to push on some data I'm just gonna use numbers so 100 200 300 and that should add on to the stack now we're gonna need a constructor here because we need some properties so a constructor is a method that runs once we instantiate an object from this class and we need a place to store data I'll just call this items and then also I'm going to have a count to tell where we are basically the position of the element because I'm not going to use the length property in JavaScript I want this to be as low level as possible so the first method will create is push I'm just going to put a comment here we'll say add elements to our store to top of stack and let's say push this is gonna take in an element which as you can see below we're just passing in numbers and I'm not gonna use push like I could say I could take the items which is our data and I could call push because it's a JavaScript array method but I'm not going to do that I'm gonna take the items and then the index that I want is gonna be the count right and then I want to set that to the element that's passed in so if I call this it's gonna go ahead and add 100 to it right now for the next one if I just leave it like this it's going to replace the 100 I don't want it to do that I wanted to add on so we need to increment the count so let's say this dot count and plus equals 1 or plus plus whatever you want to use and then as far as what I want a return I want to return the the position that this is being added to now this dot count got incremented so the position of this is going to be 0 however count will be one after this runs so I'm going to return count minus 1 so that it returns in this in this case 0 because that's the position and what else is what the other thing I'm going to do is some console logs within each of these just so we can see what's going on so we get a response within our console whether or not terminal so let's put some back ticks here and we'll just put the element I will say element added to and then the count however we want to move this up because we want to move this up because we want to call it before the count gets incremented so let's save this and if we run this file I'm going to use node so you need nodejs installed and we'll run the file and you can see 100 was added to the zero position 200 to 1 and 300 to 2 now in terms of using pop we should be able to just call stack pop and that should remove the topmost item which in this case is going to be whatever the last item in the stack so 300 so the last that we add is gonna be the top right it gets added to the top when we push so let's go up here and let's say return return and remove top element in stack and then also I want to return undefined if stack is empty so let's say pop this doesn't need to take anything in because remember it's just popping it off the top there's there's no specific element that we're targeting here and like I said I wanted to return undefined if it's empty so to see if it's empty we can just say if the count is equal to 0 then we want to return undefined and if you want to pause the video at any time and try this yourself that's fine I'm gonna every time I create a method I'll you know put a comment here and tell you what it does although the rest of them are pretty easy now we want to return and remove the top element in the stack so what I'll do is create a variable called delete delete item or whatever you want really and then set that to this dot items and then I want the count however the count is going to give me one more than I need for the position one hundred is in the zero position this is the tube I'm sorry one position this is the two position but the count is going to be one two three so we don't want we don't want three because there is no three position we want the two position in this case so we want to subtract one from it okay hopefully that makes sense because our stack is zero based like most data structures so that'll put it in the variable now we also need to decrease the count because we're taking one off right so we want to say this count - equals one that'll decrease it by one and then we need to return the delete item and then I'm just gonna put a console log in here just to tell us what's going on and we'll put the delete I'll say delete item removed so now if I save this after knowing what a stack is and how it works you should know what what's gonna happen here right so let's go ahead and run it and what happened was we added one two and three hundred and then when we called pop it removed 300 because that's on the top of the stack if we call pop again it's pretty easy to figure out what's gonna happen it's gonna remove 200 okay if we call it again we get 100 removed and if we call it again we just get nothing cuz it's actually like a well we'll do is console.log because it's not gonna it's not gonna print out what's returned unless we console.log so this should give me undefined because it's empty okay so we get undefined and if I want to console.log this remember we're logging the position right I'm sorry we're not logging the position here logging the position on push this will return the actual item which is 100 if I console.log the push this should give me 0 so let's try that and you can see we get the zero position all right so let's just clear that up and I'm just gonna leave we'll leave two pops in there so the next thing I want to do is peek so peek is is used to just see what's on top it's not gonna actually remove it so let's say check check top element in stack and this is really simple after we do this you should know exactly how to do this we just need to return this right here whoops so we want to return that that's the top-level item or element and then I'm just gonna console.log here and let's just let's say top element is and we'll put in that all right so now if we peek let's actually put the peek right here before we push on the 300 so we'll say stack dot peek and that should give us 200 so let's run that and right here we get top element is 200 because we had we haven't pushed on the 300 yet okay and then 300 to added to 2 then 300 was removed then 200 was removed so now I want to be able to check if the stack is empty so it's a is empty which is also pretty simple we just need to check if the count is equal to zero we could put an if statement but a much cleaner way to do that would be just to return this dot count equal to zero which will give us true or false and then for a console log I'll say this dot count equal to zero and I'll just use a ternary and we'll say let's just say stack is empty if it's equal to zero else so we use a colon for else will say stack is not empty and then let's put the is empty up here at the top where we know it is and then let's put it I don't know down here and we'll run that so at the top we get stack is empty and then down here we get stack is not empty another thing I want to do is check the size so we'll say check size stack which is gonna be really easy we just need the count right we just need to return this dot count and let's go here and just put some back ticks in there because we want to grab the count and then we'll say elements in stack so we'll check the size let's check the size after we pop off those two items so stack dot size so right here one elements in stack because we we popped off 300 and then 200 so I'd also like to print out everything print out all the data in the stack at any given time so let's say print print elements in stack and if you again if you want to pause the video and try this yourself you can there's this there's a lot of different ways to do a lot of different things but what I'm going to do is just initialize a string because I want to print this out as a string and then I'll do a for loop and we'll say let's let the index equal 0 and then say as long as I is less than the count then we want to increment by 1 and then in here we'll take that string that we initialized and we want to append to it so plus equals we don't want to replace it through each iteration we want to append this dot items and we'll just out of space like that and then return the string now I'm not doing any console logs in the print so we do have to console.log down here and let's print out we'll go after 300 and say stacks prints actually we have to console.log and let's also do it after we pop this stuff off alright so we'll run this so let's see something is not right here 100 why is it printing out so many times oh I added the the entire thing here we just want the current index there we go so right here it's printing out one two three hundred then we removed two three and two hundred and then it prints out one hundred so that's working correctly now the last thing I want to do is just clear everything so it's a clear stack so we'll set this items to just empty and then this stock count to zero and then as far as what we want to return will return the stock items and let's just do a console log here and say stack cleared all right so we'll go down here and where should we put this so we have 100 we'll go right under right before we print out and let's say stack clear so this should print out nothing so let's clear this up and run and right here the stack got cleared we try to print it out there's nothing there zero elements in the stack when we call size and the stack is empty all right so everything is functioning as it should and I think a good idea for another video would be to maybe write a test to really test this out without having to do all these console logs let me know if that's something you guys would be interesting it interested in but that's it I just wanted to do a quick video I will be doing other data structures as well we'll probably do a queue next which is pretty similar it you just take it off the take it off the the end instead of the top so we might do that next and we'll get into some other ones as well and if you have any requests or anything like that you can leave that and leave those in the comments but that's it thanks for watching guys I appreciate it and I'll see you next time

Channel: Traversy Media

Views: 63,558

Rating: 4.962482 out of 5

Keywords:

Id: wtynhUwS5hI

Length: 16min 28sec (988 seconds)

Published: Fri May 29 2020