![Introduction to Data Structures for Interviews](https://static.frontendmasters.com/assets/courses/2018-08-09-data-structures-interviews/thumb.webp)
Check out a free preview of the full Introduction to Data Structures for Interviews course
The "Queue: Method Usage" Lesson is part of the full, Introduction to Data Structures for Interviews course featured in this preview video. Here's what you'd learn in this lesson:
Bianca defines the expected outcomes from the methods in the queue data structure and discusses considerations when implementing the code.
Transcript from the "Queue: Method Usage" Lesson
[00:00:00]
>> Bianca Gandolfo: All right, so let's check out our Queue. We have our prompt.
>> Bianca Gandolfo: I am going to fork it. I'm gonna go through this one a little bit more quickly, since we've gone through the stack already.
>> Speaker 2: It's kinda similar.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Yeah,
>> Bianca Gandolfo: It's very similar.
[00:00:26]
So let's think about how that applies to us. So enqueue, we need to take a value, same as the push method. Dequeue, takes nothing. Peek, takes nothing. Okay, so let's do var myQ = Queue, new Queue, not an old queue, it's a new one. We're gonna instantiate it, like that.
[00:00:57]
And, where is my, and we want it to look something like this.
>> Bianca Gandolfo: Uh-oh, too many open.
>> Bianca Gandolfo: Excuse me.
>> Bianca Gandolfo: Queue prompt, Queue solution, here we go. That's why I have to name them, very specific, or I get confused. Okay, so we want our Queue, so we want to,
[00:01:37]
>> Bianca Gandolfo: .enqueue. So when we enqueue something, we wanna push it to the back. So the same as our,
>> Bianca Gandolfo: This is the same order from our stack. So once we do this, we expect it to look like that, with a length of 2. And then we want to myQ.dequeue.
[00:02:04]
And we want it to look something like this.
>> Bianca Gandolfo: We wanna take the first one,
>> Bianca Gandolfo: Okay?
>> Bianca Gandolfo: All right.
>> Speaker 3: Did we wanna update the property in line 43? Does it wanna be number one, string one? Or should it be zero?
>> Bianca Gandolfo: What do you mean?
>> Speaker 3: I'm sorry, line 42.
[00:02:42]
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: The number one is the key, and then the string saying one is the property-
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Do we wanna update the key to zero, or it doesn't matter?
>> Bianca Gandolfo: Cuz we already moved the first one.
>> Speaker 3: Yeah.
>> Bianca Gandolfo: Yeah, if we want it to be in constant time, we can't go back and edit all of the indices.
[00:03:01]
>> Speaker 3: Sure.
>> Bianca Gandolfo: So this is the one thing that makes it different from an array implemetation, where we imagine array being a continuous block of memory, and the array indices need to stay consistent. So, kind of, but we're going to keep track of it a different way so that we don't have to reshuffle the contents of our Queue.
[00:03:27]
And it will keep our dequeue, and later subsequent enqueue's, in our constant time constraint that is required by our Queue. Okay, okay, so when we dequeue, we want it to look like this. And then, let's say, whoops, let's say we want to enqueue again. So let's enqueue,
>> Bianca Gandolfo: Two.
[00:04:08]
>> Bianca Gandolfo: So then, how might we,
>> Bianca Gandolfo: Make this work?
>> Speaker 4: Is that a trick question?
>> Bianca Gandolfo: No, it's similar-
>> Speaker 4: Should we use the length again?
>> Bianca Gandolfo: Yeah, we'll need the length.
>> Bianca Gandolfo: One thing we could do is we could just keep track of,
>> Bianca Gandolfo: The first, we could call it the head, even.
[00:04:39]
The value of the headIndex, or something like that.
>> Bianca Gandolfo: And then the tail index would be the headIndex, plus the length.
>> Bianca Gandolfo: So if the length is 1, let's see. So if the headIndex is 1, the length is 1, no, that's not gonna work cuz that's gonna equal 2.
[00:05:04]
But let's say our, in this case, our headIndex equals 0, and then we add 2. Okay, so we're saying that we're off by one here. So it would be the headIndex, plus the length, minus one. These are things that are really, really important to check, because making assumptions, you know what that does.
[00:05:29]
So we don't do that here. So now we're gonna enqueue two. So what that would look like,
>> Bianca Gandolfo: Is, so the head is gonna stay the same. The length is gonna increment to 2. So one plus two minus one is, one plus two, that's three, minus one is two.
[00:05:55]
This is why I don't teach the math problems, two.
>> Speaker 5: Because it'll assign the next possible index, since we moved something?
>> Bianca Gandolfo: Mm-hm.
>> Speaker 5: So we try to just assess where to-
>> Bianca Gandolfo: Yeah.
>> Speaker 5: The next sequential value of the index?
>> Bianca Gandolfo: Yep, yep, yep, exactly. And this way, we don't have to reshuffle anything.
[00:06:19]
And because our Queue doesn't, in our stack, we don't really use it to access anything in the middle, usually. We're really only operating on either, the front, or the back. So the indices in the middle really don't matter, we just need to keep track of the front, and the back.
[00:06:34]
And since we can derive the last index, we're fine. And we're using numerical indices, so it's just easy to come up with,
>> Bianca Gandolfo: The tail.
Learn Straight from the Experts Who Shape the Modern Web
- In-depth Courses
- Industry Leading Experts
- Learning Paths
- Live Interactive Workshops