What a stack is and how it REALLY works in JavaScript... are you really sure you know?

hey welcome back and in this video we are going to be looking at the stack now the stack is one of the most fundamental abstract data structures and one of those concepts that you really need to understand the computer science and we're going to look at it from a javascript perspective now from a javascript perspective it doesn't quite behave in the way that you might expect so listen on [Music] so before we get on to how the stack works let me talk about how this video came around so i was messing around with some coding characters and some coding exercises and anyone who's ever had to do some sort of coding test as part of an interview probably recognizes some of these things but i like to do it to just kind of keep my mental programming agility and and kind of place and i was looking at the the exercise of reversing a string and it suddenly occurred to me that when somebody's asking you to how to reverse string they're probably not interested in here is the syntax that you know in javascript or whatever programming language you work in but what they're probably interested in is what fundamental computer science knowledge and knowledge of abstract data structures that you actually have because that's what powers these types of coding exercises and once you understand those theories then you can apply it onto different types of exercises so it's less about learning the syntax although syntax is important it's more about understanding these fundamentals so for something like reversing a string or reversing an array then actually taking away the syntax actually understanding what a stack is and how that works becomes absolutely critical so what we're going to do just now before we look at the stack itself we're gonna familiarize ourselves with that typical type of question we're gonna sort of answer it in syntax you know so we'll write a couple of answers in javascript and then what we're gonna do is look at the stack and then how we could solve the same problem by using the stack so the first thing i'm going to do is i'm just going to open up the visual studio code so let's just open that just now and what i'm going to do is i'm going to use a tool called quaker which is one of my sort of favorite kind of interactive editors for javascript so it's really simple it allows you to write some javascript code and then you can get some instantaneous feedback so rather than having to run things on the terminal now the typical question as i said before was take an array or a string or something and then reverse it so we'll start with an array and then we'll work our way up to strings a little bit later and then as i said i will show you how it works with stacks so let's let's create an array so i'm just gonna uh let's take the word fish for example so we'll just create an array here and we'll do that and that will give us uh fish as an array and i'm just gonna assign that to um a variable called r and this isn't a pirate show but let's call it r it stands for array it's not me being a pirate and then we'll just console log that so cuz log r and then you can see fish appears that's the output and i can change any of these values i can put there fashion and it would say it will just be updated interactively that's why i like quaker in that sense let me just make this a little bit bigger actually okay and we'll we'll get rid of that as well so i've got my my first example so i've got uh fish and i'm logging it out now if i wanted to reverse that then all i need to do is do an r dot reverse right uh and if i just console log that out for a second so let's console log r you can see it's coming back with h s i f so fish is reversed now the first thing to kind of point out there is the reverse function in javascript is uh mutatable so it's a mutation that's occurring here it's not a copy yet so um if i were to as you can kind of see that console log that i've got there you know is fish i've called our reverse it's not returning any value what it's doing is modifying that uh fish array uh when i perform the operation so that's my kind of starting point and this is sort of what i'm trying to get at right if somebody's asking you please reverse an array or reverse a string they're not testing if if you know how to find the reverse method off of a string come on we we all kind of know how to do that right that what what they're trying to get at is some of these fundamentals which as i said before is something like the stack so this isn't going to be one of those videos where we go through all the 20 000 variations in javascript and how you can uh reverse an array or reverse the string um as i said we're going to go and look at stacks which is the fundamental but for all of those people who like to scream at the screen and go ah you could do a reduce on this please show me how to do i will do the reduce and then we will go into how it works with the stack so if i was going to do a reduce on this then how i would do this is i would give it a name so in this case i'm going to call it reverse i'm going to use arrow functions in this case and i'm going to use function expressions rather than declarations so we're going to call my function reverse and in this particular case i am going to accept in a parameter called r and uh here's my arrow function and then what i'm going to want to do is call reduce on my arrow function and therefore i also need to provide an arrow function within reduce which is going to be my reduce function so in this case uh reduces have um basically the uh the previous value that you passed in and the current value so we'll pass in total and we'll pass in uh cur yeah and then we will put another arrow function in here and all we're going to do is return the total plus the current now this will return it as a string and then we'll turn it back into an array so if i do total plus cur and then if i have a look uh down here and do a console.log reverse and if i pass in r you see it's coming back with hsif which is what i passed in before so i'm just gonna create myself a new array that we're going to work from so we'll just copy this from up here we'll call this uh r2 uh not as an r2d2 um but r2 so there we go is um r2 r2's fish and then we're just going to pass in reverse there and it's coming back with fish now if i wanted to reverse that as a string then i could just do a cur plus total and now it's hsif now that is how that works um but that's a string and not an array so if i wanted to return an array i could just use my dot syntax so i'll use the spread operator and then i'll spread total and then what i want to do if i wanted to return fish i could just do comma cur and you can see it returns fish and if i wanted to reverse it i could just put curve before here and then it's back to hsif so that is how i could do that using a reducer as i said before though the purpose of this video is not to mess around with all the various javascript syntax is to understand abstract data types and understand how you could use a stack to solve the exact same problem and therefore give you an understanding of what a stack is so here is the stack um as you said so javascript has its own uh ability to operate as a stack today with arrays so you can kind of see i can create a stack by creating an array and then calling this push function um and then passing my uh string onto that now the reason that sort of works in javascript today is because a stack has sort of been pre-built into array so before i show you what this looks like let's say let's go back into quarker and then we will create an empty array so we'll do it let r equals uh empty array and then we can call the push function so let's push fish onto the stack again so we'll do r.push and then what i'm going to do is just so we'll do that four times and then we'll put f i s h and then if i wanna console log that out um we'll just put an r here and then you can see it's returning f i s h so javascript has a sort of built-in concept of a stack built into it so what is a stack what is pushing a stack in this sense so let's come back into my uh funky little slide for a second so we've got this empty array and then what happens with the stack.push so when i push this f on here what you're going to see is this f appearing at the top of the stack right that is the the top item of the stack now when i then push the next uh item onto the stack which is an i you can see the i goes on top of the f so you're building up this stack and then we can do the same with s f i s and then h so we end up with my stack h now being at the top s being below that i've been below that f being below that so it's kind of like a stack of papers so as i keep adding uh an item to the stack the stack gets bigger and bigger and bigger and and that's essentially what happens when i'm pushing an item onto the stack now if i wanted to i could also pop an item from a stack and how i do that is by calling the pop function and then you can imagine what a pop's going to do so if i hit pop it's going to take the top item off the stack and then i hit pop again it takes the next item off the stack um i hit pop again it takes a night next slide i'm off the stack and i hit pop again and then it's gone and we can run that sort of same function back into javascript so if i take my array that i've got here um and then let's just take this out of here and then what i'm going to do is we are just going to do a little while loop so while um our daw length is uh greater than 0 so we're just gonna loop around and then what i'm gonna do here is we will then do a console.log so we're just gonna log whatever is coming out and then we're gonna do an r dot pop and what a pop does from an array is it pops off the top item from the stack so you now end up with h s i f so if we come back into the slides for a second what we'll do is just kind of show how that works with the funky little animation that i built so as we are looping around so when you call pop off the stack it's going to remove that item from the stack and return that so that's why we can console log it out so if i pop h you can see it now appears at the bottom there as my console log and then i pop the s and then that appears as a console log so i pop i off of the stack and then i console log it out and then uh pop f off of it and then a console log side out so that's how a stack works it as i said it's a fundamental uh data structure but essentially there is this push operation there's this pop operation so i can push something onto the stack and i can pop something off of the stack and then obviously i can check the size of the stack as well i can see if it's empty or if it's full etc and and as you see this very simple algorithm that i had is that if i push some letters so f i s h onto the stack when i pop an item back off of the stack it's gonna be in essentially last in first out order so the last item that you pushed onto the stack will be the first item that you pop off of the stack just like a stack of papers so if you think about that and you probably noticed this already that is a fundamental way that you reverse a string so if i wanted to reverse the word fish f i s h h is the last item that was on to the stack and now as i start popping it off and console logging it you will see h s i f which is in reverse order and that's why these sort of coding exercise i i could be wrong i've never done one of these things but my feeling in these cases is not about trying to understand what syntax you understand in javascript it's more about the concepts that you understand now i did say things get a little bit weird in javascript and and let me explain why and in order to explain why what we have to do is move beyond just looking at an array and using the push and pop what we actually want to be able to do though is implement a stack for ourselves and that's what we're going to do now so what we're going to do is we're going to create a reverse function um so in this case i'm going to call my function reverse it's going to be an arrow function so i am going to pass in an array as a parameter so we'll put past an r and [Music] we will just put our brackets in place now i need a result to return because i don't want my reverse function to be mutatable i want it uh to return the actual array so we'll just put an empty array in here for just now that'll be result but i therefore i need a copy of that array to um to to do my operations on so what i'm going to do is i'm going to call that stack uh and we will set stack being equal to whatever is in the array so i'm using that wonderful spread operator there again so i've got my result i've got my stack and then essentially all that's going to do is copy the contents of the array into my stack now the reason that i'm not doing let stack equals r as we discovered earlier then r is would just copy a reference so these two things would point to the same thing and i i and therefore they would mutate and i don't want that what i really want is a copy and isolated that's why i'm doing a spread operator and copying all the contents of my array into my stack so now that i've got my my stack all i need to do is loop around my stack so while stack dot length is uh greater than zero and then what we're going to do just now is we're going to do that sort of pop operation that we had before and then what i'm going to do is pop off the item from the stack and then i'm going to push it onto the result so how i do that is i'm going to do a result.push and then i'm going to do a stack dot pop okay and that should be the equivalent of what we saw before so i'm popping off e f i s h and then essentially uh i'm pushing it onto my stack so the final thing i need to do is uh return the contents of my stack so we will return result because that's where i'm pushing everything onto and then finally if i do a console.log and i call reverse and then i pass in r you can see it's now returning h s i f so i've got my function which means we're cool and what we're now going to do is we're going to start creating our own stack manually rather than using the built-in function uh or off of the array and then we will understand how to build a stack from there so to do that i'm going to create a class called stack and that is going to be my new data type and that's obviously going to be an object so what i want to be able to do at the moment is the first version of this i'm i'm going to sort of essentially hide i'm still going to use an array but i'm going to hide that underneath so i am going to create a private variable and i'm going to call this stack and that's what i'm going to use to um underneath to to hold all my variables so next thing i need is a constructor um so let's create my constructor and then what i want to be able to do is set uh the value of instructor to being an empty array so i've now got my stack and i've got an empty array that i'm going to be using now you see the squiggly lines and that's because i need to do this dot stack so that is a private um variable in that sense so it's a private property so there's there's that you cannot access this outside of uh here so if i tried to let's say if i try to create my stack for a second so if i did a let's get rid of the reverse for just now so if i try to instantiate that so let's uh create a new uh variable so we'll call let stack equals new stack and then if i try to access there there's there's there's no way i can access that stack right is it's not gonna let me do anything because um it's it's completely private so i've got my stack there which is cool the next thing i need to do is i need to put a uh push operation because i want to be able to push items onto the stack so for just now i'm going to create a new method on this so i am going to create something called push and then i need to accept an item that i'm going to push onto the stack so we'll push an item and then what we're going to do is we are for just now we are going to use the push operation on the stack but of course we're going to change that as we go along so if i call this.push and call item and then this is now being pushed onto my stack and similarly if i wanted to pop something from the stack then i could do the same thing so i will do a pop and then we will do the same thing here so i will return this dot hash stack dot pop i don't need an item in this case and then that's going to pop that item off of the stack if i wanted to get the size uh so we'll call that a length at the moment then i'll create a getter i will give it a length and then and then all i'm going to do is return this dot hash stack dot length that's fine and that gives me uh the basics of my stack so now if i wanted to i could do a stack dot push and uh let's push on f for fish and then i guess i could do a console log stack dot pop and you can see the f is appearing so i now have a working stack and if i wanted to i could console log the length so stack dot length and then you see it's a one there and then if i console log the length after the pop you can see it's zero so my pushing and my popping is uh working now one of the other things that you need in a stack in general is you want the ability to peek at whatever is at the top of the stack without popping it up so it's like a pop but rather taking the item off you just see what's there so we can do a peek very quickly so we'll copy the pop and then we'll do a peek and uh actually i shouldn't have copied the hair so we're going to do a peek and let's tidy that up that pop shouldn't have an item on there um and then all i'm going to do is return from the stack whatever is is the item there so we can just uh essentially put in uh this dot length uh minus one and then if i run that if i here if we do a console.log stack dot peak you can see the f but the important thing is that it is not popped off there which is really important all right now that we've got our stack working what we want to do is change our reverse that we created earlier and make that work with the stack so what i'm going to do here is i'm going to take the the reverse in fact i'm going to take all of this up here and we're going to bring this down a little bit so we're going to keep our stack up here and then what i'm going to do is i'm going to take my array here we're going to get rid of this console log for a second and then we're going to move this down here for a second so from my reverse function perspective rather than passing in an array we're going to be passing in a stack so for clarity i'm just going to call this stack because i'm going to be passing my stack in i don't need to do anything and do any spreading on it because that's going to be there automatically i'm going to do the same thing as i did before i've still got a length on my stack i've still got a push and i've still got a pop so i'm going to do the same thing as i did before uh and and sort of uh do my stacked up port put it onto this array here to output it and then return it so that kind of works there i'm going to get rid of this f a s i h what we need to do is just push the values that we had on there before so we'll just put in f i s h and you can see the i've got fish now on to my stack my stack length is four and then i can peak the last value which was h and then if i pop it is three so that's all working in that sense so i'm gonna remove all of this and then what we're gonna do is run a reverse and we'll just do a um and we'll just do a console.log we will call reverse as we did before and then we are going to pass in stack and then we get h h s i f so this we've got rid of the array that we were doing before and we're now running with the stack class that we created there now i i think we're probably not entirely happy with this operation because we're still relying on this push and this pop from the array so what we want to be able to now do is implement the push in the pop ourselves so we're going to do that so in order to push an item onto an array in uh javascript i can of course use this push mechanism but the other way i can do that is i can just add an item onto the end so the way that i can do that is by essentially just let's take this uh dots.length and then what i'm going to do now is rather than doing a minus one i'm just going to add a new item onto that so let's just close that and we're going to say this is equal to item so what we're essentially doing there is if i had f i s h then if i wanted to add a new item on top i'm just putting it as one item above so it's a an element higher so in this case all i'm doing is is setting this i'm creating a new maximum value and then setting that item so that is the sort of push so if i were to go down to the bottom here and then as you can see if i do a stack dot push and we'll just add a y on there you can see that i pushed on y my function is it's still working as it stands right so even though i've replaced this uh push operation um it's it's sort of uh dealt with now the next thing that i want to be able to do is get rid is deal with the pop so rather than calling the pop function there what i can do is essentially get the last item from the stack so the way to do that would be to let's say uh let item equals this dot stack pop rather than pop we will use um the this dot length uh minus one we will use the this dot uh stack dot length minus one um so that will get me the last item uh on the stack which is cool and then i want to remove that item from the stack so the the way that i essentially do that is i change the length of the stack so that's pretty simple so all i need to do now is uh set this.length and i need to equal it to uh one less than the length it was before so that's essentially this dot stack length uh minus one if i if i wanted to be super simple about it i could just do a minus minus and then all i need to do is return my item and that is the equivalent of me running a pop so now you can see this is all still working so if i change that to an e or an h you can see my reversing is still working so i'm slowly but surely changing all these items so i'm no longer using the push or the pop mechanism uh from the array and i'm just using my own manually implemented sort of version so we're we're we're sort of doing well at the moment um which is cool but the next thing i want to get into is actually can i get rid of this array completely and the answer is yes and the reason the answer is yes is that arrays aren't what you think in javascript and this was the bit that i was saying which is different from everything else so in other programming languages arrays have contiguous memory and what i mean by that is uh and in fact if i bring up my ipad uh for a second let me let me draw what i mean there so in any other system in the world maybe not every other system but mainly any low-level static languages uh like roster c or whatever if you were to create an array then from a memory allocation perspective it's contiguous so you could take this sort of starting memory block maybe address zero and then uh you could put it in a character so you could put in let's let's stick in a b c d and then how memory is allocated would be in order so this this could be two bytes this could be two bytes this would be two bytes but they are essentially in order they are contiguous and that makes it super efficient to kind of go up and down the stack and be able to run because you're not jumping from memory location to memory relocation you know that essentially if this was sort of a size of two bytes or whatever it would be zero plus two plus two plus two plus two and so essentially just by adding two all the time you could get there javascript doesn't quite work that way right um javascript is if we look at how arrays are actually created in javascript then an array is essentially an object right that it's it's got different methods etc but underneath the hood it's it's an object which means that it works in the heap it's not working with a contiguous memory and that is completely uh uncontiguous now there is optimizations to various javascript uh interpreters so v8 for example has a whole set of um optimizations for things like integers to which effectively make it contiguous in that sense but that's really uh an implementation of the underlying um interpreter or underlying engine but but essentially it's non-contiguous so there's there you could have a piece of memory that's having a here and that could be a memory location one and then you could have b and then you could have c and that could be zero one two but they could be in different memory locations all to all together that could be a two three two this could be at 1 3 1 and then that sort of joins that all to kind of gather so it that's something to kind of be aware of but since therefore javascript arrays are essentially objects there is nothing stopping me from doing that so rather than declaring my stack as an array i can get rid of it completely and i can put in these two brackets and now i'm just creating my stack off of an object now that becomes super interesting so if we were to look at this well actually if i was pushing an item onto the stack this dot length uh equals item then i'm sort of good yeah so that will continue to work now problem is i i don't really have a length i want to i want to start to be able to deal with that myself so the next thing i'm going to do in this sense i'm going to start to track the size of the array myself so i am going to add in something called a length here um which is going to be fine and then i am going to set my length equal to zero which is cool um and then i'm gonna that get length i'm now gonna return this dot length here so and we'll put that here um so i'm now in control of of my my length um for easiness sake i am going to then just start using my this dot length here so this dot length uh minus one uh i'm going to get rid of this and this is going to be a this dot length minus minus so what i'm doing here is is i'm going through all my operations my pushes and my pops and i'm now using my new length so every time i pop something i'm going to do a minus minus and every time i push uh then i'm i'm obviously going to increase uh my length as well so i'm going to change this so that the uh the uh this dot stack.length is a plus plus let's get rid of the stack part and [Music] the last thing that i need to do here uh of course items so my push works my pop works uh my peak now works uh and i'm now sort of modified everything uh so that we're in a good place but so even though i've sort of moved everything into my sort of new structure i haven't deleted this object on a pop right so i've converted everything in but i still haven't deleted this object right i may have minus my count there but it still exists so let's pause for a second before i do the final part i've now introduced a i've now converted my stack so that it's uh an object rather than an array by a razer object anyway i'm now controlling the length of the array my or my stack myself by introducing this new property called length and i've set it to zero now whenever i push an item onto the stack i'm i'm obviously doing what i did before which is i'm setting the item the out on the index to there i'm obviously incrementing my my length every time i push an item off when i pop an item and then i'm doing a this dot length minus minus i'm going to come back to this in a second so my pop works in the same way and then i can peak i'm just looking at the the index for this dot length minus one so that's all good on that sense as well and then obviously i'm getting a length there at the end so the last thing is as i said i'm not dealing with my memory allocation i may be at decreasing the length of that counter but but this item is still the you know so even though i'm returning my my previous item when i'm popping i'm not removing it from the array so to remove that from the array what i need to do is run a delete so to do that i use the i think it's es6 and introduced it but the delete property and then i'm going to run that on my stack so i'm going to say delete this stack and then i'm going to pass in the item i want to add delete which is going to be this dot stack length minus one because that's the the last item on the stack and then that is going to delete the item so now if i come back into my stack and we start messing around with it do an e on that and h you can see my reverse is still working so now i've got a fully implemented stack uh where i can push i can pop and i've got nothing from my array previously all right so you're probably thinking to yourself well if an array is an object anyway and i've implemented my stack what is the difference between a stack and an object in that sense and that is a fantastic question so what we're going to do is we're going to add a new method onto our stack and i'm going to call it log and all we're going to do is do a console.log and we're going to log out whatever our stack is so let's just do that so console.log this dot stack and you see there's nothing coming up just now but if i were just to add in a cons stack dot log at the bottom here you see nothing appears there because it's going to do up here and you see f i s h so what's actually occurring is our stack is indexing things are zero one two three yeah so with that's how it so when you think about an array an array is just an indexed object that is the underlying structure of an array uh underneath the hood all right so what we're going to do now is is just to prove that these things are the same thing underneath what i'm going to do is i'm going to take uh what we just built there and i'm going to move that into another folder i'm going to move it out of quokka and i'm gonna shove it into uh or play this sort of pre-defined node.js folder so i've moved my uh stack into here for a second so what i'm gonna do now is i'm very quickly gonna create a function called hello the reason i'm going to call this function hello is what i want to be able to do is look at the underlying byte code and compare the two so i'm going to do this as an arrow function we're just going to put in the stack that we created earlier so we're just going to push in fish and then i'm just going to return one of the values to the stack so we'll just do a peek on that so we will peak and then we'll return that value and then i'm just going to console log out the hello so we'll call hello here and if we then switch to my terminal for a second and if i run node00play.js which is the name of the file you can see it returns h as we would expect so if i wanted to convert that from a stack to an array then all i need to do is do this to make an array rather than a stack obviously stack.peak's not going to work so i would need to return length at -1 if i save that run node play you see it returns the h so it works and then i run node play as i did before then you will see it returns the h as as as it did previously so whether i use a stack or whether i use an array then both things would work now what i want to do is look at the underlying byte code for this so how i'm going gonna do that is i'm gonna use the dash dash print byte code and then i'm gonna filter on my hello function so if i just run that for a second uh what you can see here and i'm not gonna we're not gonna spend too long looking at the underlying byte code but there's a couple of things i want to point out you can see it's creating this empty array literal so that's that's the key thing create empty array literal i'm doing this with an array at the moment there's a whole lot of stuff there we're removing data back and forward calling properties loading things from the accumulator not going to go into the detail there it's not that important the thing i want you to see though is here's my array you see string f i s h i want you to remember this number here which is c12c1 so we're looking pretty good and you can see 4d19 there so that's my that's my bytecode as i run that as an array let's bring this back to being a stack so we are gonna back to the stack peak and then we're gonna put that back to new stack now if i run that one more time you see it's returning back as an h but look you can see f i s h remember c one that i had before [Music]

Channel: Chris Hay

Views: 90

Keywords: chris hay, chrishayuk, javascript tutorial, stack implementation, stack data structure, data structures and algorithms interview questions, data structures and algorithms, javascript tutorial for beginners, data structures, data structures and algorithms playlist, computer science, data structures playlist, javascript tutorial advanced, reverse a string javascript, es6

Id: rj7cIlHB_Ho

Length: 39min 22sec (2362 seconds)

Published: Mon Nov 01 2021