DOUG LLOYD: So if you've watched the video on stack,
this is probably going to feel like a little bit of deja vu.
It's going to a very similar concept, just with a slight twist on it.
We're going to talk now about queues.
So a queue, similar to a stack, is another kind of data structure
that we can use to maintain data in an organized way.
Similar to a stack, it can be implemented
as an array or a linked list.
Unlike a stack, the rules that we use to determine
when things get added and removed from a queue are a little bit different.
>> Unlike a stack, which is a LIFO structure,
last in, first out, a queue is a FIFO structure, FIFO, first in, first out.
Now queues, you probably have an analogy to queues.
If you've ever been in line at an amusement park or at a bank,
there's sort of a fairness implementing structure.
The first person in line at the bank is the first person
who gets to speak to the teller.
>> It would be sort of a race to the bottom if the only way
you got to speak to the teller at the bank was to be the last person in line.
Everybody would always want to be the last person in line,
and the person who was there first who has been waiting for a while,
could be there for hours, and hours, and hours
before they have a chance to actually withdraw any money at the bank.
And so queues are sort of the fairness implementing structure.
But that doesn't necessarily mean that stacks are a bad thing, just
that queues are another way to do it.
So again a queue is first in, first out, versus a stack which last in,
first out.
Similar to a stack, we have two operations
that we can perform on queues.
The names are enqueue, which is to add a new element to the end of the queue,
and dequeue, which is to remove the oldest
element from the front of the queue.
So we're going to add elements onto the end of the queue,
and we're going to remove elements from the front of the queue.
Again, with the stack, we were adding elements to the top of the stack
and removing elements from the top of the stack.
So with enqueue, it's adding to the end, removing from the front.
So the oldest thing in there is always the next thing
to come out if we try and dequeue something.
>> So again, with queues, we can array-based implementations
and linked-list based implementations.
We'll start again with array-based implementations.
The structure definition looks pretty similar.
We have another array there of data type value,
so it can hold arbitrary data types.
We're again going to use integers in this example.
>> And just like with our array-based stack implementation,
because we're using an array, we necessarily
have that limitation that C kind of enforces on us, which is we
don't have any dynamism in our ability to grow and shrink the array.
We have to decide at the beginning what is the maximum number of things
that we can put into this queue, and in this case,
capacity would be some pound defined constant in our code.
And for the purposes of this video, capacity is going to be 10.
>> We need to keep track of the front of the queue
so we know which element we want to dequeue,
and we also need to keep track of something else-- the number of elements
that we have in our queue.
Notice we're not keeping track of the end of the queue, just
the size of the queue.
And the reason for that will hopefully become a bit clearer in a moment.
Once we have completed this type definition,
we have a new data type called queue, which we can now
declare variables of that data type.
And somewhat confusingly, I've decided to call this queue q, the letter
q instead of the data type q.
>> So here is our queue.
It is a structure.
It contains three members or three fields, an array of size CAPACITY.
In this case, CAPACITY is 10.
And this array is going to hold integers.
In green is the front of our queue, the next element to be removed, and in red
will be the size of the queue, how many elements are currently
existing in the queue.
So if we say q.front equals 0, and q.size size equals 0--
we're putting 0s into those fields.
And at this point, we're pretty much ready to begin working with our queue.
>> So the first operation we can perform is to enqueue something,
to add a new element to the end of the queue.
Well what do we need to do in the general case?
Well this function enqueue needs to accept a pointer to our queue.
Again, if we had declared our queue globally,
we wouldn't need to do this necessarily, but in general, we
need to accept pointers to data structures
like this, because otherwise, we're passing by value-- we're
passing in copies of the queue, and so we're not actually changing
the queue that we intend to change.
>> The other thing it needs to do is accept a data element of the appropriate type.
Again, in this case, it's going to be integers,
but you could arbitrarily declare the data type as value
and use this more generally.
That's the element we want to enqueue, we want to add to the end of the queue.
Then we actually want to place that data in the queue.
In this case, placing it in the correct location of our array,
and then we want to change the size of the queue, how many elements we
currently have.
>> So let's get started.
Here is, again, that general form function declaration
for what enqueue might look like.
And here we go.
Let's enqueue the number 28 into the queue.
So what are we going to do?
Well, the front of our queue is at 0, and the size of our queue
is at 0, and so we probably want to put the number 28 in array element number
0, right?
So we've now placed that in there.
So now what do we need to change?
We don't want to change the front of the queue,
because we want to know what element we might need to dequeue later.
So the reason we have front there is sort of an indicator of what's
the oldest thing in the array.
Well the oldest thing in the array-- in fact, the only thing in the array right
now-- is 28, which is at array location 0.
So we don't want to change that green number,
because that's the oldest element.
Rather, we want to change the size.
So in this case, we'll increment size to 1.
>> Now a general sort of idea of where the next element is going to go in a queue
is to add those two numbers together, front and size,
and that'll tell you where the next element in the queue is going to go.
So now let's enqueue another number.
Let's enqueue 33.
So 33 is going to go into array location 0 plus 1.
So in this case, it's going to go into array location 1,
and now the size of our queue is 2.
>> Again, we're not changing the front of our queue,
because 28 is still the oldest element, and we
want to-- when we eventually get to dequeuing, removing elements
from this queue, we want to know where the oldest element is.
And so we always need to maintain some indicator of where that is.
So that's what the 0 is there for.
That's what front is there for.
>> Let's in enqueue one more element, 19.
I'm sure you can guess where 19 is going to go.
It's going to go into array location number 2.
That's 0 plus 2.
And now the size of our queue is 3.
We have 3 elements in it.
So if we were to, and we're not going to right now, enqueue another element,
it would go into array location number 3, and the size of our queue
would be 4.
So we've enqueued several elements now.
Now let's start to remove them.
Let's dequeue them from the queue.
>> So similar to pop, which is sort of the analog of this for stacks,
dequeue needs to accept a pointer to the queue-- again,
unless it's globally declared.
Now we want to change the location of the front of the queue.
This is where it sort of comes into play, that front variable,
because once we remove an element, we want
to move it to the next oldest element.
>> Then we want to decrease the size of the queue,
and then we want to return the value that was removed from the queue.
Again, we don't want to just discard it.
We presumably are extracting it from the queue-- we're
dequeuing it because we care about it.
So we want this function to return a data element of type value.
Again, in this case, value is integer.
>> So now let's dequeue something.
Let's remove an element from the queue.
If we say int x equals &q, ampersand q-- again that's a pointer to this q data
structure-- what element is going to be dequeued?
In this case, because it is a first in, first out data structure, FIFO,
the first thing we put into this queue was 28, and so in this case,
we're going to take 28 out of the queue, not 19, which is what
we would have done if this was a stack.
We're going to take 28 out of the queue.
>> Similar to what we did with a stack, we're not actually
going to delete 28 from the queue itself,
we're just going to kind of pretend it isn't there.
So it's going to stay there in memory, but we're just
going to kind of ignore it by moving the other two fields of our q data
structure.
We're going to change the front.
Q.front is now going to be 1, because that is now
the oldest element we have in our queue, because we've already removed 28,
which was the former oldest element.
>> And now, we want to change the size of the queue
to two elements instead of three.
Now remember earlier I said when we want to add elements to the queue,
we put it in an array location which is the sum of front and size.
So in this case, we're still putting it, the next element in the queue,
into array location 3, and we'll see that in a second.
>> So we've now dequeued our first element from the queue.
Let's do it again.
Let's remove another element from the queue.
In the case, the current oldest element is array location 1.
That's what q.front tells us.
That green box tells us that that's the oldest element.
And so, x will become 33.
We'll just kind of forget that 33 exists in the array,
and we'll say that now, the new oldest element in the queue
is at array location 2, and the size of the queue, the number of elements
we have in the queue, is 1.
Now let's enqueue something, and I sort of gave this away a second ago,
but if we want to put 40 into the queue, where's 40 going to go?
Well we've been putting it in q.front plus queue size,
and so it makes sense to actually to put 40 here.
Now notice that at some point, we're going
to get to the end of our array inside of q,
but that faded out 28 and 33-- they're actually, technically
open spaces, right?
And so, we may eventually-- that rule of adding
those two together-- we may eventually need to mod by the size of capacity
so we can wrap around.
>> So if we get to element number 10, if we're
replacing it in element number 10, we'd actually put it in array location 0.
And if we were going to array location-- excuse me,
if we added them up together, and we got to number
11 would be where we would have to put it, which doesn't exist in this array--
it would be going out of bounds.
We could mod by 10 and put it in array location 1.
So that's how queues work.
They're always going to go from left to right and possibly wrap around.
And you know that they're full if size, that red box,
becomes equal to capacity.
And so after we've added 40 to the queue, well what do we need to do?
Well, the oldest element in the queue is still 19,
so we don't want to change the front of the queue,
but now we have two elements in the queue,
and so we want to increase our size from 1 to 2.
>> That's pretty much it with working with array-based queues,
and similar to stack, there is also a way
to implement a queue as a linked list.
Now if this data structure type looks familiar to you, it is.
It's not a singly linked list, it's a doubly linked list.
And now, as an aside, it is actually possible to implement
a queue as a singly linked list, but I think in terms of visualisation,
it actually might help to view this as a doubly linked list.
But it is definitely possible to do this as a singly linked list.
>> So let's have a look at what this might look like.
If we want to enquue-- so now, again we're
switching to a linked-list based model here.
If we want to enqueue, we want to add a new element, well
what do we need to do?
Well, first of all, because we're adding to the end
and removing from the beginning, we probably
want to maintain pointers to both the head and the tail of the linked list?
Tail being another term for the end of the linked list,
the last element in the linked list.
And these will probably, again, be beneficial to us
if they are global variables.
But now if we want to add a new element what do we have to do?
What we just [? malak ?] or dynamically allocate our new node for ourselves.
And then, just like when we add any element to a doubly linked list we,
just have to sort of-- those last three steps here
are just all about moving the pointers in the correct way
so that the element gets added to the chain without breaking the chain
or making some sort of mistake or having some sort of accident
happen whereby we accidentally orphan some elements of our queue.
Here's what this might look like.
We want to add the element 10 to the end of this queue.
So the oldest element here is represented by head.
That's the first thing we put into this hypothetical queue here.
And tail, 13, is the most recently added element.
And so if we want to enqueue 10 into this queue, we want to put it after 13.
And so we're going to dynamically allocate space for a new node
and check for null to make sure we don't have a memory failure.
Then we're going to place 10 into that node,
and now we need to be careful about how we organize pointers
so we don't break the chain.
>> We can set 10's previous field to point back to the old tail,
and since '10 will be the new tail at some point
by the time all of these chains are connected,
nothing's going to come after 10 right now.
And so 10's next pointer will point to null,
and then after we do this, after we've connected 10 backwards to the chain,
we can take the old head, or, excuse me, the old tail of the queue.
The old end of the queue, 13, and make it point to 10.
And now, at this point, we have enqueued the number 10 into this queue.
All we need to do now is just move the tail to point to 10 instead of to 13.
>> Dequeuing is actually very similar to popping
from a stack that is implemented as a linked list
if you've seen the stacks video.
All we need to do is start at the beginning, find the second element,
free the first element, and then move the head
to point to the second element.
Probably better to visualize it just to be extra clear about it.
So here's our queue again.
12 is the oldest element in our queue, the head.
10 is the newest element in our queue, our tail.
>> And so when we want to dequeue an element,
we want to remove the oldest element.
So what do we do?
Well we set a traversal pointer that starts at the head,
and we move it so that it points to the second element
of this queue-- something by saying trav equals trav arrow next, for example,
would move trav there to point to 15, which, after we dequeue 12,
or after we remove 12, will become the then-oldest element.
>> Now we've got a hold on the first element via the pointer head
and the second element via the pointer trav.
We can now free head, and then we can say nothing comes before 15 anymore.
So we can change 15's previous pointer to point to null,
and we just move the head over.
And there we go.
Now we have successfully dequeued 12, and now we
have another queue of 4 elements.
That's pretty much all there is to queues,
both array-based and linked-list based.
I'm Doug Lloyd.
This is CS 50.