Data Structures and Algorithms in JavaScript Stacks

Transcript from the "Stacks" Lesson

[00:00:00]
>> Bianca Gandolfo: All right, we're gonna start with our first elementary data structures, stacks and queues. So stacks and queues are used everywhere. You use them all the time, you might not even know. Under the hood, you use stacks and queues all the time. Someone has a question. So the question is, in what cases would you not basically dynamically set those properties by passing in an argument to the instance?

[00:00:38] So that's whenever you have some constant, right? Some constant that is gonna be matched through all of the classes. So if you have a certain type of building, maybe you have a yurt and yurts only have one floor. And so, you could have a constant, this.floors=1, yeah? And so whenever you don't want to, if you don't need to dynamically set, then you don't need to do that.

[00:01:07] And you shouldn't be adding extra part to the interface to make it complicated if it's not necessary. Stacks and queues, stacks and queues. Let's get started. So some ingredients to learn a data structure. You wanna learn the concept of this theory. How do you do that? You'd write, right?

[00:01:26] We draw a little figure. When you think of a data structure, you probably think of a circle, some lines connecting, and usually a number or boxes. So we draw out the diagram, we create the API or the operations methods. The APIs is just the interface, right? Your methods, just like we were putting in a .prototype.

[00:01:48] How are we gonna interface with our data, right? Are we going to be able to add things, are we gonna be able to delete things. Sort things, etc. Those are gonna be all part of the API that you're gonna define. Depending on usually depending on use case but in this case we're gonna be first talking about generals and then getting a little more specific.

[00:02:12] Cool, then we're gonna build it. This is the fun part, where you're maybe gonna pseudocode it out, if you're into that. If you're totally not into that, it's optional. I do recommend it. It does help kind of give you a little bit of an outline for how you're gonna approach it.

[00:02:29] And for those of you, someone mentioned in the chat that they feel like maybe it's hard to communicate their thought process, because it's not quite linear. Pseudocoding can help you organize things on paper in a non-linear way and then get it into a linear step-by-step. And this is gonna help you when you're communicating with your interviewers, when you're communicating with your teammates or your pair or even yourself.

[00:02:48] Getting your thought pattern to fall into some order is gonna help you solve problems faster. So, pseudocode if you want. Code out the data structure. This is not the optional part. This is the part where you say VAR blah blah blah equals function whatever whatever. You're gonna code it out, and you're gonna code the methods that go on to it, the parts that are sorting it, the parts that are adding, the parts that are taking off, all of that.

[00:03:16] Then you're gonna use it, you're gonna test it out. Pair it with a more complex algorithm if you want, and we'll talk about that in the coming days. And then, last but not least, we are going to need to understand a little more deeply, our data structure and the operations that go along with it.

[00:03:33] So what is the time complexity? We're gonna talk about that pretty soon, we might be able to squeeze it in today, but if not first thing tomorrow we'll learn how to calculate time complexity, which is, how fast is your algorithm? How many pieces of data can your algorithm process on a modern computer before it just [SOUND], or takes years and years and years and years to calculate.

[00:03:52] And how can you optimize it knowing that your algorithm is slow, how can you make it faster so that you can calculate more data, right? We have really fast computers these days, but we also have a lot more data than ever before. And so it's still important that we are optimizing cuz there are many, many, many algorithms that modern computers cannot complete because they're just too slow and there's two much data.

[00:04:19]
>> Bianca Gandolfo: Great, so these are our ingredients. So have the concept, we have the code, we have the playing with it, and then we have the deeper knowledge. And so when you're thinking, I think I knew what a hash table is. You've got this list, and make sure that you're able to do all these things.

[00:04:35] If you can do all these things, you're good. You have it. And I'll mention this again in a couple days as well. All right, so we're gonna jump in to the concept of stacks. So stacks, they're an elementary data structure. They are last item in, first item out.

[00:04:59] What does that mean? So it's a list data structure of items, we use push and pop. Sounds familiar, yeah, sounds familiar. Maybe we used this was arrays. So a stack is basically an array, except the only thing that you can do on it, more or less, is to push and pop.

[00:05:19] Yeah, if there was no shift and un-shift on an array, would just be a stack. And this is just a theoretical concept of a stack and so, look at our little pancakes, so cute. So we have one little smiley pancake, so we just pushed onto our stack. The zero there is our index number.

[00:05:40] One so we push, push, pop, pop. Push, push. Notice when we take one off it has to be the top one. We can't take off smiley pancake number zero. Right, until we take off one and then we can pop them, yeah? This is a stack.
>> Bianca Gandolfo: Cool? Good to go?

[00:06:12] Great. So an example of a stack is our call stack, and you know what? I need to do this, really quick. All right. So we're going to do just a really really like high level, like how is our code executed, and being pushed into the call sack. Again, this is gonna be sort of like, kinda hand-wavy a little bit, but basically this is how it works.

[00:06:47] So we're going to use this function. It's a procedural function that makes eggs of any style. So here's our procedure. It's a function. It takes the style of eggs. I like my eggs scrambled, and I like them three at a time. Now we're just gonna walk you through the code, and we're going to put it on the stack.

[00:07:07] And this is just an example of like, a stack, a stack in the wild. You know, free and how we use it when we're under the hood. Awesome, so first thing's first. Whenever we call a function we jump into the body of the function. And somewhere in there it gets pushed onto our call sack.

[00:07:40] So, we could say make eggs, yeah? And then once we jump inside, we're gonna say okay, we have this completed egg, great, if the style is not boiled, style scrambled is not boiled, we want to crack our eggs. So the next thing we need to do is we need to crack eggs.

[00:08:05] So we're pushing the next function on to our call stack. And let's just imagine for a moment that inside crack eggs we have even more functions, right? We don't have that much scream real state here so we'll have to use our imagination that we're calling cracked eggs maybe in the first line is what?

[00:08:24] Maybe you need to get a bowl. I don't know. You need to get a bowl. And then in order to get a bowl inside of that, maybe the first thing you need to do is open the cabinet. So as we are executing our code, and we're getting into layers and layers of functions inside functions, we're going to stack them in what we call a call stack.

[00:08:47] A one little cube of that is called a stack frame. And again, this is kind of reductionist, but I just want to use it to show you an example. Then once we finished opening the cabinet we're gonna pop it off, once we finish executing getBowl, it returns something, right?

[00:09:08] We're gonna pop it off and then we're at crackEggs. Where are we? There we go, crackEggs. And then once that's done, we pop it off. And then once this is done, we pop it off. And so that is higher stack frame more or less works under the hood when we're executing functions.

[00:09:32] Does that makes sense? So once you go layers deep, it's a way so that it can trace how to get back to where it left off, more or less. Does that make sense? So this is gonna be useful when we talk about recursion, because recursion is one of those abstract things where we're calling functions inside of functions, and it's important that we're able to sort of trace this line of thought through.

[00:09:56] Yep?
>> Speaker 2: A request, if you could explain how call stack relates to the error call stack size exceeded.
>> Bianca Gandolfo: Yeah, so there's, you have limited memory in your browser, and if you have an unlimited loop that loops, loops, loops and keeps calling functions. People who are just getting started with recursion, I always recommend new window if you're running this in your browser, because you might have an infinite loop which means that as we're filling in these call stacks.

[00:10:27] So my call stack is pretty short, I only have seven spots. So once I have all of these spots full, it's exceeded and it's just you run out of memory and it just explodes. And that's your call stack exceeding. Cool. Or a stack overflow. Our favorite programming website.

[00:10:50] All right. Any questions here? So this our stack. So we have them under the hood. We also can create them. We can use them like arrays. We're gonna implement them not as an array because we like to do things a little more interesting here. You have a question?

[00:11:08]
>> Speaker 2: Another question, what exactly is a stack frame?
>> Bianca Gandolfo: So a stack frame is basically, it's just like the instance of the function inside of, it's like in the stack, so if you think of the stack as an array, you have indices 0 through and n, right? So stack frame would be one index in the, or one item in your array.

[00:11:36] So you can think about it like that. So say you have an array that's defined and you only have 0 to 7, so you have 8 spaces. Once you get to index eight, or nine, ten, whatever, there's no more space, yeah? So, that's sort of the idea here.

[00:11:59] All right, great. Any more questions?
>> Speaker 2: One follow up to that.
>> Bianca Gandolfo: Are there multiple stack frames going on at once? The short answer is no. The long answer is maybe. [LAUGH] So JavaScript is a single threaded language. The idea is you can only execute one line at a time.

[00:12:27] But that's not always true cuz it gets, like there's a little asterisk there. Like the language, yes is singly threaded, but it really depends on the environment if you're using like the DOM-API for example. There's web workers. There's a bunch of different ways to make it not singly threaded.

[00:12:43] So that is why the short answer is no, but the long answer is hm, maybe. Does that makes sense? Good question.