Introduction to Data Structures for Interviews Stack: Push & Pop Methods
Transcript from the "Stack: Push & Pop Methods" Lesson
>> Bianca Gandolfo: We are gonna get started with talking about the implementation, so we spent about 40 minutes giving this a go with only minimal direction. So those of you who are at home working on this, know that most people weren't able to finish the one data structure implementation in a 40-minute period, so don't get discouraged if you're finding that this takes a lot of time.
[00:00:53] And so, it's just a different way of thinking about it, but a really good exercise to improve the way that you understand your code. So let's get started, we're gonna implement a stack, okay? And what I'm gonna do here is I'm gonna ahead and fork it and we'll work on this together.
[00:01:15] So I'm gonna rely on all of you to ask me questions, to give me suggestions as I walk through how I reason about solving this problem, okay? So I'm going to implement this by hand, and so we'll do it together. So again, when I run it, we have the stack over here.
[00:01:40] It's just an object that has a property_storage, that holds a reference to this object here, okay. So the first thing I do when I'm thinking about a data structure is, I think about okay, how do I draw it out in kind of like code terms? So I would kind of just think about it like this.
[00:02:01] This is how I think I just you know, and then I'm like okay, if I wanna insert it, how am I to do that? Maybe like if I wanted to have some order, I might like have like a key. That's a zero, and then I could put a value here like three.
[00:02:21] And then okay, if I would just keep inserting like this, so we have a key value pair.
>> Bianca Gandolfo: So this is like an object of objects, I'm realizing that that's the next thing that I need to make sure that there's a containing object. And maybe, I'll just do like this, actually put a comma there and then I just have one object, and needed to and then,
>> Bianca Gandolfo: See, maybe I'll just keep this consistent, okay. So this is I'm inserting, I'm inserting, okay now, I'm pushing, I'm pushing. Now I need two, and the reason I'm using numerical indices is because I know that a stack is really like an array and I know that an array uses numerical indices.
[00:03:19] And so that's kinda how I made that leap. And then, so now I need to push, so in order for me to, I'm sorry I need to pop. In order for me to pop, I need to know which the last index is. So that means, I probably need a way to keep track of that, right?
[00:03:38] Any ideas?
>> Bianca Gandolfo: Maybe like a length property, something like that.
>> Bianca Gandolfo: Seem reasonable?
>> Bianca Gandolfo: We have a length property.
>> Bianca Gandolfo: At this point, I would want it to be 2, but how do we get it there? So those are some things that I'm just thinking about as I'm thinking about how to code out the solution.
[00:04:08] So then peek, peek I feel like is really similar to pop, so it would be knowing what the last one is because a stack, right, we need to have a reference to the last one. That's gonna be important so that's what I'm thinking about. And then the next thing I like to do is, like, okay, so that's, kind of like, me drawing it in my code and then the next thing is, okay so, what would that look like in terms of the API?
[00:04:30] And the API is just like, how am I interacting with this data structure. So right, I'm gonna be pushing, the first time I'm going to build it like this, I'm gonna push zero. And then I'm going to push one. And I expect it to look like this, and I expect it to have a length of two.
[00:04:49] And then when I pop,
>> Bianca Gandolfo: Let's put this under here so, and then when I pop, I will expect it then. So I don't pass anything to pop just like you would in if you are popping off an array. I would expect it then to look like this and have a length of 1.
[00:05:21] So those are some things that's kind of how I'm thinking about I would interact with it. And then, so all the things that we think about and talk about with my interviewer would be edge cases. Okay, so what if it's empty, how might my logic need to accommodate like an empty list or another thing that you should consider is okay, what if I pass something that into?
[00:05:42] Maybe you have a function that is requiring other function to be passed, what if it's undefined, what if I pass a string instead. So these are kind of age cases, error handling kind of things that you might wanna think about and talk about with an interviewer, especially if your interview prompt is kind of a shorter one.
[00:06:04] They might be looking for more details like that if you are doing really long one like implement a whole data structure, it might like be okay with you just saying like, okay to do, I will handle these kind of edge cases. So do some tips from little old me, okay.
[00:06:28] So now that I kind of have an idea, the next I might do is pseudo code it out. But it's pretty straightforward in my mind. So I'm gonna go ahead and code it. But I recommend that once you kind of go through this process, and you feel like you know what your approach is, you discuss it with your interviewer.
[00:06:48] Your interviewer thinks it's also a good idea. You can ask them what their opinion is. And then, if you still don't have the specific step by step edge start in your head, you may want to just do some pseudocode which just in English say first, I would loop through this loop.
[00:07:11] Then I would do ten jumping jacks, else, whatever. Just write it out like that and to get your head around it you can even debug your pseudocode, which we might do if we have time. Not for this one though. And kinda go through and see,
>> Bianca Gandolfo: If you're bug-free, okay.
[00:07:37] All right, so we'll start with push.
>> Bianca Gandolfo: Okay, so push adds a new value of any type and like that thing there. Okay, all right, so I want to add a value, so I need a length. So maybe I'll say this.length.
>> Bianca Gandolfo: We'll initialize it at 0, cuz the first time we won't have anything.
[00:08:11] So let's see, so I could say this._storage,
>> Bianca Gandolfo: At the length,
>> Bianca Gandolfo: Equals value, okay? The second time we add it, we're gonna want length to be one, so we'll increment length after, okay, push.
>> Student: The basic thing at this place in the stack, right? This is the value that is assigned to it.
>> Bianca Gandolfo: Yep, so the very first one is gonna be zero and you're gonna be counting up. Then when you pop, you are going to start from the highest on and go down.
>> Student: Which we'll know from the length property?
>> Bianca Gandolfo: Exactly, we can derive that from the length, for sure.
[00:09:10] Okay, so that seems reasonable. Let's just,
>> Bianca Gandolfo: console.log, and make sure that we're on the right track, all right. Great, that seems to be what I am expecting.
>> Bianca Gandolfo: I apologize that's really small.
>> Bianca Gandolfo: Okay, I feel happy about that, how do you guys feel about that? Any questions about our push?
>> Bianca Gandolfo: Something I used to think about, since this an object, we can't support a function. We can't support an array or anything like that. So those are some type checks you could use, so I might do,
>> Bianca Gandolfo: Something like that. Okay, so let's think, if this is empty would it work any differently?
>> Student: Meaning that if it didn't get an argument in?
>> Bianca Gandolfo: That's another thing to check, if there is no argument.
>> Bianca Gandolfo: Go on, anything else?
>> Student: [INAUDIBLE] Like edge cases-
>> Bianca Gandolfo: Yeah.
>> Student: If something would break this.
>> Bianca Gandolfo: Exactly.
>> Bianca Gandolfo: Okay, ready for pop? So pop, what does pop take?
>> Bianca Gandolfo: As an argument, what does it take? Nothing, right? Okay.
>> Student: It's always gonna be the last one.
>> Bianca Gandolfo: Yep, it's always gonna be the last one. You want to return it at the end. So we can see for my signature, tells what's doing and just return the last and newest value in the stack, okay.
[00:11:16] So how can we do this? We can say,
>> Bianca Gandolfo: Let's say, const lastVal = this._storage and this.length- 1, right? So that's another thing to be mindful of, off by one errors.
>> Bianca Gandolfo: And then we need to delete it, we can actually use a delete keyword, or what I usually do as I just.
>> Bianca Gandolfo: this._length- 1.
>> Bianca Gandolfo: Set it to undefined, same thing as deleting it.
>> Bianca Gandolfo: And then, we wanna return our last value. And before that, I think Tom mentioned we need to decrement our length.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: What do we think?
>> Student2: They'd have returning.
>> Student: So what is 125, walk me through that again?
>> Bianca Gandolfo: Yeah, so what we're doing is we have let's say, so we pushed, we have zero, this is our storage object, we have zero like this in here. And then we also have one, right? We have two. So when we pop, we are grabbing this value, which is one, at property one.
[00:13:21] Saving it in there, because we're gonna delete it. Once you delete it, so you have to save a reference before you delete it. And so what we're doing here is we're just setting this value to undefined.
>> Student: Reset it almost.
>> Bianca Gandolfo: Yeah, yeah, it's the same. I think the implementation details of the delete keyword and sending it to undefined are pretty much exactly the same, so I don't care.
>> Student: So we saved the reference on line 24, so we don't care. Now it's stored there cuz we grabbed it.
>> Bianca Gandolfo: And you have to delete it, somehow, right. Another way that you can do it is you could instead of, yeah, I would just said undefined. There are a few other things you could do, but this is the easiest thing.
[00:14:00] Or if you like the delete keyword, you can just delete it, too.