All language subtitles for 10 - Queues English

The last video we talked about the stack data structure.

And in this one we're going to talk about the new data structure and one of the important things to

know about both of these types is they're what's called a abstract data type meaning that they really

don't exist.

They're more of a theoretical kind of method for data structures and then they have different implementations

in terms of how you can use them.

So last time we went over arrays and linked lists and were going to do the same thing in this video.

So with queues they're just like stacks are pretty basic.

The important thing to know is that cues are essentially the opposite of a stack in terms of how you

actually pull out the data.

So right here we have our array implementation.

And if we want to add a 5 Element we'll in queue it.

And so that gets put into the zero element.

And now we put a 1 in and you can see this all works essentially the same as a stack where you just

take it and you put these elements inside of the array.

And then just get put two more because we're going to use an example.

And I want to show exactly how that works in a real life type of situation.

OK there we go.

So we have six elements and there are 5 1 2 1 9 and 5.

The values don't matter it's more of just having some things in there.

Now if we want to take an element away if you remember back to our stack example when we popped we actually

popped the last element that we added.

And so that uses a design called The Last In First Out.

So in other words five in a stack if we popped would be the element that was removed.

Q uses the exact opposite methodology with a q.

It is first in first out.

So if I do.

Q I go up to the head.

I pull out that value of 5 and then I leave that as a null.

And so what that means is that this zero element in the array now does not contain anything.

It doesn't move items the items don't shift to the left or anything like that.

If anyone tries to access this element it's just going to give a known value and we can go down the

line and so will go dequeue again pull out the one and again pull out the 22.

And if you notice the array is still 6 values long because no does have a value it has a value.

No it means that there is no value inside of that element.

It's it's a little bit different than if you went to like the sixth or the seventh or eighth.

These elements really don't have anything at all.

But here these ones use two.

So that's very subtle but it is a difference because it shows that we still need to know how long the

array is.

So a really good example because I still find this not the most intuitive way of understanding how a

cue works the way I like to think of it is if you've ever seen one of these.

So does this Spenser's or in grocery stores that are used to hold canned goods quite often.

And the way they work is say you have a number of elements or you have a number of cans you can slide

all of those cans in one at a time.

And so say you add six cans you could slide them in one two three four five six.

The first item the first can that you put in rolls all the way down and it's this item right here.

Now if you want to go access one of these so if you want to get this can a tomato soup right here.

You actually take out the very first item that you pulled up.

So whatever you put in first is the same one that you pulled out.

And if I take another can it's going to be the second item.

It's the same exact way it functions the same way in the array we put in this.

First value.

Then we pulled it out first then this was the second one.

It was a second when we pulled out all the way down the line.

And this is with an array.

It works pretty similar with the linked list in the linked list implementation.

We'll put in a value 43 and now put in 11 and you can see the 43 has a pointer to 11 we also know how

tall it is we know that this is two elements long and the head is 43.

So if I do 51 51 is going to go at the end one will go at the end.

And then three will go at the end.

So here we have a link list.

The head is always going to be pointing at whatever the first item is.

And then this tall call right here this tall points to the last element.

And so we know that this link list has five elements.

Now if we cue it we're going to take this 43 pull it up and out and then we now have the head pointing

at this 11.

Now with the linked list this is represented a lot different than an array.

So it's important to understand how this works and with an array of those index values with the length

list you have pointers to whatever the value is to the right.

So 11 points to 51 51 points to 1 x enter etc. all the way down the line.

So that's how AQ works.

Please let me know if you have any questions whatsoever in the comment section and I'll see in the next

video.