Queue

[00:00:00]
>> So we're gonna get to the point where we're gonna run into, is this an algorithm or is this the data structure. Well it uses the data structure, and then performs an algorithm on top of the data structure. So this becomes a more common thing we're gonna see.

[00:00:12]
So is linked list a data structure or an algorithm? Well, you could argue that the insertion is the algorithmic side of it, the actual setup is the data structure itself, right? We can make these arguments bla bla bla bla bla. I'm not gonna be pedantic. Call it whatever you want, I'm not gonna be offended.

[00:00:27]
So, our first data structure on top of a linked list is going to be a queue. This is one of the most common data structures I have implemented. I've implemented a queue. Just this year, I had to shove video down into a video decoder. And the only way to have a buffer to be able to do this and make sure you insert it in the correct order is first in first out and what does that that's, that's cute, right?

[00:00:48]
And I was using it in C two, I felt a little bit smarter than everybody else. To writing C linked lists, it felt very good. So let's go over a queue. So we know what a linked list is now. A queue is just a specific implementation of a linked list.

[00:01:03]
So let's pretend that we have a pointer to head and we'll do the exact same setup so that way I can say, Bravo, Charlie and Delta. Let's see Bravo, Charlie, this is fun. I just decided to do this now, there we go. So this of course is our tail, this of course is our head.

[00:01:23]
And so if we want to insert in a queue, or before we go to that, a queue is simply a FIFO structure, a first in first out, this is what the Brits call a line, right? And so they call it a queue. We call it a line. That's all it really is.

[00:01:39]
So if we wish to insert into a line, what do you do at a carnival? What do you do at anything, you get into the back of the line? So just like that, if we want to insert, say, E, what we're gonna do is we're gonna have D, we're gonna have our current tail point to E.

[00:01:54]
Then we're gonna update our tail to point to E. Does that make makes sense? So it'd be kind of a two operation. You could imagine I'll just write this an actual type script, this dot tail these dot next equals E then we just go. This dot tail equals E.

[00:02:14]
So that makes sense. We break this link, we are now pointing to the end of the list. Awesome, this makes sense. But a popping operation, we don't pop from the tail. We pop from the head. Now also notice that I'm using a Singly Linked List. We don't even need a doubly linked list.

[00:02:29]
We don't even need that extra computation time. We don't need that extra property storage requirement. We need a very minimal amount of stuff. So, ahead if we want to pop it, we do the exact same thing. We would first set head to point to be, so we're doing the reverse operation.

[00:02:45]
Head points to be, we'd save off of reference of head of course, right? So we'd have some sort of consth head, equals the cont head right? We point head to B and then we can just simply take the previous the old one, remove the link, and then return out the value.

[00:02:59]
Remember, this is a node based data structure, which means we have a container around the value that you hand the cue. So therefore we have to do container A dot value and return that out. So just to write it out just to be complete we'd go head equals head I'm just gonna write this out without using this and all that you can apply this you, can apply const.

[00:03:21]
And then I would do h.next equals null and then of course Oopsies, we wouldn't want to do that. That is the worst possible operation. We'd wanna go head equals head.next, then set our saved off reference to null and then just simply return out h.value. Does that make sense?

[00:03:48]
Just simply move it forward, return it. Yeah, so if I did it the other way around, we'd lose the value then. You know your whole queue would suck and there you go, you lose all the values don't do that. All right, that's really all a queue is it's actually shockingly simple because what it's doing is constraining what you can do with a queue and by constraining what it can do.

[00:04:13]
What kind of performance are you getting out of queue, when you actually end what's the performance? Well, we don't traverse anything, right? We don't go over any sort of list. It's not based on how big of a value you give me, it's simply based on the fact that I have to set one thing.

[00:04:30]
One by one next value to a new node and I have to update where my tail points to those are two constant time operations right and creating a node itself is constant time operation in the sense that yeah It may require me to go get memory may require me to go out to the heap and grab memory.

[00:04:47]
But we consider those kinds of constant time operations when doing this. And all it requires us to do is just be able to point those new values elsewhere. That's it. So it's a constant time operation, pushing into a queue is constant, popping from a queue is the exact same thing but just in reverse, it's constant.

[00:05:03]
And so fantastic. We now have have reduced what we can do and we've made sure that it's very, very fast and it performs a specific algorithm, first in first out. It's that simple, all right? It's that simple. And so of course, there's also usually one other operation that comes with queues often, which is peak have the ability to see what is my first element without popping it off.

[00:05:24]
Of course, that would just be hey, head dot value, right? That's pretty much as straightforward as it gets. And so of course, up I already said this part we're entering into the world where we constrain things from here on out, you'll just notice that most things are constrained intentionally, such that we get very good performance out of it and you can only use it in a certain way.

[00:05:42]
Yes it is technically a generalized linked list underneath the hood often with a queue, but you can only use it in a certain way.