Queue: Enqueue & Dequeue

[00:00:00]
>> Bianca Gandolfo: Okay, so let's figure out how we're going to do that. Okay, so when we enqueue, we're gonna add it to the storage, so let's start with that. So we're gonna say this.storage = our this.storage. Then we need to do the length. So we have our length here.

[00:00:24]
Let's start that at 0 and then we can also do r.
>> Bianca Gandolfo: And notice I call this head index. Personally, I like to be really annoying with my naming. So this is clear cuz this is a head index, this is not a pointer to the head. So in a link list, maybe you would say this.head, or head node I think would even be better so that you know that it's either a node or an index.

[00:00:54]
So it's better when things get complicated and you can't remember what something is. So we're gonna say this.length = our value, right? Same as before.
>> Bianca Gandolfo: All right and then now we wanna set our head, do we wanna set our head index? We want to initialize our head, so every time.

[00:01:23]
Only if, so here's a good one. So if,
>> Bianca Gandolfo: I'm gonna put it up here, and we might move it. So if (this.length === 0), we want to say this.headIndex =
>> Bianca Gandolfo: So if it's zero we want to make sure the head index, well it's still zero. So if it's one, we wanna set it to one.

[00:01:58]
No, we don't wanna do that, we'll keep it as zero, we're good with it at zero. We won't change it until we delete it
>> Bianca Gandolfo: Yeah, okay. So then,
>> Bianca Gandolfo: Let's just increment it.
>> Bianca Gandolfo: I think that'll get us there. All right, so and we have some other to do's here.

[00:02:27]
We could do type checking. Whenever I see this I'm like, is it off by one? No, in this case we start by zero. Okay, we're good. Type checking input validation and stuff like that. We can just call this and put validation. Our argument validation, argument validation. Okay, all right, and the other thing is I would to ask an interview like, do you want me to return anything?

[00:02:57]
Typically I don't return something from enqueue, but you can always just clarify if they want something to be returned or not. So don't just make an assumption about what they expect. Let's do the DQ. So actually, let's test this, so let's make sure NQ works. Let's get rid of that.

[00:03:20]
We want to run this and see if it matches. That's cuz I'm not console logging anything. Is it plugged in? This is my, is it plugged test. Okay, so we have zero and we have one we have a length two. Head index is two, that is a problem.

[00:03:43]
We don't wanna change it every time. All right, maybe we just don't need that in there at all, yeah. That makes sense to me.
>> Speaker 2: Well, cuz we really don't care, we only care about the very first time and initialize.
>> Bianca Gandolfo: Yeah, which we said it here. And it's only gonna change once we dequeue.

[00:04:10]
I'm glad we checked that because would have introduced a weird bug. It would have been a problem. Okay, so dequeue we are going to say lastValue = this_storage and then this done. So we're gonna get the last one which is the length minus one. Key that minus one there.

[00:04:46]
What do I wanna do? Then we wanna delete it.
>> Speaker 2: Why do we care about that length going to the first letter.
>> Bianca Gandolfo: You're right, thank you. You guys are so good at this. Okay.
>> Speaker 2: Just the first value maybe.
>> Bianca Gandolfo: Hm?
>> Speaker 2: Const first value.
>> Bianca Gandolfo: Thank you.

[00:05:13]
We're gonna delete the first value and then we will delete it. So we store it, we delete it, and now we need to make sure our pointers are catching on. Okay, so our length needs to be decremented.
>> Bianca Gandolfo: And then our head,
>> Bianca Gandolfo: Needs to be incremented.
>> Speaker 2: Why?

[00:05:38]
>> Bianca Gandolfo: Because-
>> Speaker 2: Because we moved the first one.
>> Bianca Gandolfo: Yeah, and then we want it to go to one, and then-
>> Speaker 2: Makes sense.
>> Bianca Gandolfo: Yeah, we wanna just keep.
>> Speaker 2: We're like resetting it to the next one because we know we removed the first one.
>> Bianca Gandolfo: Mm hm.

[00:05:50]
>> Speaker 2: So we know now it's kinda moving on to the-
>> Bianca Gandolfo: Yep.
>> Speaker 2: Index one.
>> Bianca Gandolfo: Yep, exactly. What else do we need? I think, so again, if it was empty we could check for that if this.length.
>> Bianca Gandolfo: All right, so let's test out our code. So we're going to dequeue it and we're expecting it to look something like this.

[00:06:34]
Let's check it out, make it a little bigger. Okay, so one, length is 1, head index 1, awesome.
>> Bianca Gandolfo: And then we wanna check this one. To make sure that, oops, we don’t wanna do that, that we're still getting the correct.
>> Bianca Gandolfo: Okay, one, two. Interesting. We have a weird bug here.

[00:07:02]
So one is equal to two, off by one error. Let's check that out.
>> Bianca Gandolfo: We need to, so when we dequeue, the length is two.
>> Speaker 2: The length is right but the value is wrong. It's like we rewrote it.
>> Bianca Gandolfo: Maybe we don't need to, well I feel like, so we wanna decrement it there.

[00:08:03]
It's interesting that it's setting maybe we also forgot to return this. So we forgot to return that. That's not our issue. So this.length is 1 but we want it
>> Bianca Gandolfo: Maybe we need to do this because we want it to be the length after the head. Remember we need to move it.

[00:08:39]
So once head is incremented, so if the first go around is 0, the headIndex, but then the next round it's going to move up one. And let's check it out. Do you guys understand what our bug was?
>> Speaker 3: Can you explain it again?
>> Bianca Gandolfo: Yeah sure, so remember down here.

[00:09:04]
So when we enqueue two, we need to get the value 2, but the length is 1 before, right? So with the length 1, remember I was saying like head plus lass or something I forgot exactly what i was even talking about at that point. But we need to add these together because the length is 2, but the head starts at 1.

[00:09:35]
So this is 1, 2, but say this started at 14, you can't just look it up at the length because the length could be a list of length one, but it should be starting on the 14th index. So when we enqueue, or on queue, we can't just use distance length.

[00:09:57]
We need to find what the last Index is in that kind of sub-array that we're creating. So the head index is the very first on the list, and then the length is how many more after you need to put something. So to put it another way, let's say we have, so when we onqueue here two goes into our on queue method, the top in there, let's take this with us though.

[00:10:36]
>> Bianca Gandolfo: We'll take it with us so we can look at it. So here's our
>> Bianca Gandolfo: Data structure. So we've dequeued, and we only have this right now. So our head starts at 1, the length is 1. If we wanna insert the value 2, we want to insert it into the second index.

[00:11:01]
And the reason we wanna do this is so that we can mathematically figure out which index we're going to next. Otherwise, our look up would be in linear time, cuz we would need to loop through the whole object to find what we're looking for. So we need to be able to just add it up mathematically for constant time.

[00:11:20]
So we wanna get the index to two, and then we're gonna put our value there. So that's what we wanna do. So based on the data that we have which is our headIndex starts at one, and the length of our original is just one, we can say length plus headIndex gives us that index that we are interested in and that's why we have this math here.

[00:11:51]
So we can even do something like this, const nextIndex, so that we are really clear about what this represents.
>> Bianca Gandolfo: Or even like, actually let's say lastIndex. Good?