Implementing a Queue

[00:00:00]
>> This one is a great one to implement. I think it's fantastic, so we can jump back over to our editor. Remember if you do have VS Code, I do have a get ignore for everything that starts with the day and some number. So therefore make sure that you show get ignored files so you can be able to see day one.

[00:00:15]
And we can go down to queue, open it up, and look at this, it's a poorly formatted file. But there you go, we have a class that's generic over t. It has a length that has a number, we have availability for constructor, we have enqueue. So this is typically the phrase that is used when implementing a queue, is to enqueue something is to add it to the queue or push it to the queue.

[00:00:36]
And then we have deque, spelt without to UEs, which is always kind of mind boggling to me, but that one is to remove it from the queue, and of course, peak. So let's figure out first our constructor, and then we can figure out the other methods. So let's actually first get our typing here.

[00:00:52]
So we're gonna have a little type queue node. I believe type node is a reserved word if I'm not mistaken. We'll have a queue node that is a generical over t. And we want a value that is T, right? And then of course, we're gonna want a next that may or may not exist, right?

[00:01:09]
We don't know how many elements we have. We can't say it always exists. If it always did exist, you'd create one of them and you'd infinitely create memory forever and eventually blow up your system. So there has to be an optional point to this, and we'd go queue node.

[00:01:21]
I can't remember if node is taken, is node taken? I think, okay cool. At one point, you couldn't create node, it would actually fail on you. I don't know what's changed or why it's changed, but there we go, awesome. We have typed node, it has a value, it has a next, that is itself.

[00:01:36]
And so that means we can have a private head that's gonna be a node T. Great, right, we've now created this. And of course, this can be undefined as well, right? In TypeScript, you can always use the old question operator or whatever it's called. I forget what it's called.

[00:01:54]
And then we can go tail as well, ooh, that's teal. There we go, so now we have our two references, right? They may be undefined, but we have two references, one to head, one to tail. There are node T, generic or have node. Generic over T, RQ is generic over T.

[00:02:10]
That means we can pass in any value. We don't care what value you pass us. We create our own container and we manage the state ourselves. All right, constructor, this.head equals this.tail equals undefined. Okay, I wanna be super serious about this. Now, of course length, we have nothing in there, right?

[00:02:27]
Awesome, we've pretty much done the hardest part about a queue. Okay, not the hardest part, but one of the hardest parts, getting your constructor correctly. All right, let's start with peak, because peak is such a simple operation, right? All we have to do is return this.head and then, of course, do one of those little question mark values, right?

[00:02:45]
There we go, that's a null operator, I believe, this is our null coalescing operator, I forget the exact name. But effectively says that, hey, if head is not null or not undefined, I can get the value if it is undefined or return undefined. So there we go, we now have fulfilled our interface.

[00:02:59]
It's awesome. We've set it, let's go. All right, so let's deque next. Cuz I feel like deque is not only a restaurant that serves ice cream, but also is a pretty simple operation to do. The first thing we need to do is, do we even have a head?

[00:03:17]
All right, if we don't have a head, we can't deque it. So if there is no head, let's return undefined, right? Pretty straightforward, that makes sense, makes sense to me, awesome. After that, we need to do a couple of operations, we need to do some bookkeeping, this.length-- right?

[00:03:34]
If we want the outside world to know how many items we have, we kinda need to keep track of these things ourselves. Awesome, you're usually used to something like an array doing this for you, we are now the array, right? We are now the ones doing these operations.

[00:03:47]
And then of course, what is the operation? We first update head to point to the next value, then we return out our previous head. So let's go like this, const head=this.head. this.head.next equals, oopsies wrong direction. this.head=this.head.next, right? So we saved that our head. We've updated our head pointer to the next one.

[00:04:11]
Whether it's undefined or not, it does not matter to us. We just updated it to the next one. And then we just gotta do a little return head.value. Now, if we're using a more traditional language that doesn't have a garbage collector, we would probably wanna do some cleanup here, right?

[00:04:24]
You'd wanna do a free here. There's things you'd have to do here that we just don't do in JavaScript. So just to be somewhat complete or make it feel as if we're doing all of our own bookkeeping, I will go head.next = unDefined. We don't need to do that, but again just to give you the more complete feel.

[00:04:44]
Awesome, we just did deque. Was deque all that hard? No, it's really just those two simple steps, save your head, update the head, return the value. That's two simple steps, index 0. I'm not off by 1, I'm still correct. Dang it, we have to reduce our length. Okay, I am off by 1 in index zeroing.

[00:05:02]
So there we go. So let's do enqueue, right, which is really the opposite operation, we're gonna go to the tail this time instead of the head. So again, if there is no tail, that means we pretty much have an empty array, right? Now, if you're using a different type system, I would probably have chosen this.length===0, right?

[00:05:23]
Because at this point, I could say, hey, we do this operation when this length is here. But since TypeScript can't understand exactly your meaning if you don't intentionally check for null or undefined, then we're gonna check intentionally for undefined. So if there is no tail, that means this.tail = this.head, which equals a new node.

[00:05:43]
So let's create a new node, value is item, oopsies, as no generic over T, right? There we go, we've now just created the node. Our next is undefined. Our value is the item, it's of type T or node is generic over T. Everything is good except for one thing, we don't have our length correct.

[00:06:04]
So this.length++, make sure you spell length correctly. There we go. It was looking pretty good, right? We now have it officially done for the first or the base case. If it's not this, we need to do that whole tail updating thing. So we have to make sure we don't accidentally destroy all of our data or lose our tail pointer, right?

[00:06:26]
So this.tail.next needs to equal the node. So let's just create off the node right now. Value, really we could just take this const node =, paste up here, make it easy, right? And then node, I forgot that return value. There we go. tail.next, right here, so we've just took our tail and added a new one to the list.

[00:06:51]
So now we just need to take our tail and point it to the new one, right? Right, yes, you're absolutely correct. Thank you. There we go. Our tail now points to the last item in our list, because it became the last item, and then now we are pointing it correctly.

[00:07:08]
So that is all that is required to do a queue. Queues are actually fairly simple data structures, right? They're not too hard, you're only managing one link. You just have to make sure you're updating or deleting that one link properly.