WEBVTT
X-TIMESTAMP-MAP=LOCAL:00:00:00.000,MPEGTS:900000

00:00:05.204 --> 00:00:07.370
DOUG LLOYD: So if you've
watched the video on stack,

00:00:07.370 --> 00:00:09.870
this is probably going to feel
like a little bit of deja vu.

00:00:09.870 --> 00:00:13.850
It's going to a very similar concept,
just with a slight twist on it.

00:00:13.850 --> 00:00:15.530
We're going to talk now about queues.

00:00:15.530 --> 00:00:19.350
So a queue, similar to a stack,
is another kind of data structure

00:00:19.350 --> 00:00:22.412
that we can use to maintain
data in an organized way.

00:00:22.412 --> 00:00:24.120
Similar to a stack,
it can be implemented

00:00:24.120 --> 00:00:27.000
as an array or a linked list.

00:00:27.000 --> 00:00:30.320
Unlike a stack, the rules
that we use to determine

00:00:30.320 --> 00:00:34.210
when things get added and removed from
a queue are a little bit different.

00:00:34.210 --> 00:00:36.590
>> Unlike a stack, which
is a LIFO structure,

00:00:36.590 --> 00:00:45.610
last in, first out, a queue is a FIFO
structure, FIFO, first in, first out.

00:00:45.610 --> 00:00:49.320
Now queues, you probably
have an analogy to queues.

00:00:49.320 --> 00:00:52.820
If you've ever been in line at
an amusement park or at a bank,

00:00:52.820 --> 00:00:56.430
there's sort of a fairness
implementing structure.

00:00:56.430 --> 00:00:59.160
The first person in line at
the bank is the first person

00:00:59.160 --> 00:01:00.760
who gets to speak to the teller.

00:01:00.760 --> 00:01:03.522
>> It would be sort of a race
to the bottom if the only way

00:01:03.522 --> 00:01:06.730
you got to speak to the teller at the
bank was to be the last person in line.

00:01:06.730 --> 00:01:09.146
Everybody would always want
to be the last person in line,

00:01:09.146 --> 00:01:12.580
and the person who was there first
who has been waiting for a while,

00:01:12.580 --> 00:01:14.715
could be there for hours,
and hours, and hours

00:01:14.715 --> 00:01:17.590
before they have a chance to actually
withdraw any money at the bank.

00:01:17.590 --> 00:01:22.510
And so queues are sort of the
fairness implementing structure.

00:01:22.510 --> 00:01:25.780
But that doesn't necessarily mean
that stacks are a bad thing, just

00:01:25.780 --> 00:01:28.160
that queues are another way to do it.

00:01:28.160 --> 00:01:32.420
So again a queue is first in, first
out, versus a stack which last in,

00:01:32.420 --> 00:01:34.440
first out.

00:01:34.440 --> 00:01:36.190
Similar to a stack,
we have two operations

00:01:36.190 --> 00:01:38.470
that we can perform on queues.

00:01:38.470 --> 00:01:43.910
The names are enqueue, which is to add
a new element to the end of the queue,

00:01:43.910 --> 00:01:47.330
and dequeue, which is
to remove the oldest

00:01:47.330 --> 00:01:49.670
element from the front of the queue.

00:01:49.670 --> 00:01:53.600
So we're going to add elements
onto the end of the queue,

00:01:53.600 --> 00:01:57.220
and we're going to remove elements
from the front of the queue.

00:01:57.220 --> 00:02:00.790
Again, with the stack, we were adding
elements to the top of the stack

00:02:00.790 --> 00:02:03.380
and removing elements
from the top of the stack.

00:02:03.380 --> 00:02:07.570
So with enqueue, it's adding to
the end, removing from the front.

00:02:07.570 --> 00:02:10.639
So the oldest thing in there
is always the next thing

00:02:10.639 --> 00:02:13.620
to come out if we try
and dequeue something.

00:02:13.620 --> 00:02:18.330
>> So again, with queues, we can
array-based implementations

00:02:18.330 --> 00:02:20.110
and linked-list based implementations.

00:02:20.110 --> 00:02:24.620
We'll start again with
array-based implementations.

00:02:24.620 --> 00:02:27.070
The structure definition
looks pretty similar.

00:02:27.070 --> 00:02:30.720
We have another array
there of data type value,

00:02:30.720 --> 00:02:32.690
so it can hold arbitrary data types.

00:02:32.690 --> 00:02:35.570
We're again going to use
integers in this example.

00:02:35.570 --> 00:02:39.830
>> And just like with our
array-based stack implementation,

00:02:39.830 --> 00:02:42.340
because we're using an
array, we necessarily

00:02:42.340 --> 00:02:46.850
have that limitation that C kind
of enforces on us, which is we

00:02:46.850 --> 00:02:51.670
don't have any dynamism in our
ability to grow and shrink the array.

00:02:51.670 --> 00:02:55.710
We have to decide at the beginning
what is the maximum number of things

00:02:55.710 --> 00:02:59.300
that we can put into this
queue, and in this case,

00:02:59.300 --> 00:03:02.070
capacity would be some pound
defined constant in our code.

00:03:02.070 --> 00:03:05.430
And for the purposes of this
video, capacity is going to be 10.

00:03:05.430 --> 00:03:07.690
>> We need to keep track of
the front of the queue

00:03:07.690 --> 00:03:11.160
so we know which element
we want to dequeue,

00:03:11.160 --> 00:03:15.070
and we also need to keep track of
something else-- the number of elements

00:03:15.070 --> 00:03:16.690
that we have in our queue.

00:03:16.690 --> 00:03:19.360
Notice we're not keeping track
of the end of the queue, just

00:03:19.360 --> 00:03:21.150
the size of the queue.

00:03:21.150 --> 00:03:24.310
And the reason for that will hopefully
become a bit clearer in a moment.

00:03:24.310 --> 00:03:26.143
Once we have completed
this type definition,

00:03:26.143 --> 00:03:29.080
we have a new data type
called queue, which we can now

00:03:29.080 --> 00:03:30.630
declare variables of that data type.

00:03:30.630 --> 00:03:35.350
And somewhat confusingly, I've decided
to call this queue q, the letter

00:03:35.350 --> 00:03:38.090
q instead of the data type q.

00:03:38.090 --> 00:03:39.600
>> So here is our queue.

00:03:39.600 --> 00:03:40.700
It is a structure.

00:03:40.700 --> 00:03:45.730
It contains three members or three
fields, an array of size CAPACITY.

00:03:45.730 --> 00:03:47.340
In this case, CAPACITY is 10.

00:03:47.340 --> 00:03:49.580
And this array is
going to hold integers.

00:03:49.580 --> 00:03:55.240
In green is the front of our queue, the
next element to be removed, and in red

00:03:55.240 --> 00:03:58.610
will be the size of the queue,
how many elements are currently

00:03:58.610 --> 00:04:01.190
existing in the queue.

00:04:01.190 --> 00:04:05.300
So if we say q.front equals
0, and q.size size equals 0--

00:04:05.300 --> 00:04:07.120
we're putting 0s into those fields.

00:04:07.120 --> 00:04:11.070
And at this point, we're pretty much
ready to begin working with our queue.

00:04:11.070 --> 00:04:14.140
>> So the first operation we can
perform is to enqueue something,

00:04:14.140 --> 00:04:16.860
to add a new element to
the end of the queue.

00:04:16.860 --> 00:04:19.089
Well what do we need to
do in the general case?

00:04:19.089 --> 00:04:23.690
Well this function enqueue needs
to accept a pointer to our queue.

00:04:23.690 --> 00:04:26.370
Again, if we had declared
our queue globally,

00:04:26.370 --> 00:04:29.490
we wouldn't need to do this
necessarily, but in general, we

00:04:29.490 --> 00:04:32.330
need to accept pointers
to data structures

00:04:32.330 --> 00:04:35.040
like this, because otherwise,
we're passing by value-- we're

00:04:35.040 --> 00:04:38.140
passing in copies of the queue,
and so we're not actually changing

00:04:38.140 --> 00:04:41.050
the queue that we intend to change.

00:04:41.050 --> 00:04:44.860
>> The other thing it needs to do is accept
a data element of the appropriate type.

00:04:44.860 --> 00:04:46.818
Again, in this case, it's
going to be integers,

00:04:46.818 --> 00:04:49.330
but you could arbitrarily
declare the data type as value

00:04:49.330 --> 00:04:51.160
and use this more generally.

00:04:51.160 --> 00:04:56.030
That's the element we want to enqueue,
we want to add to the end of the queue.

00:04:56.030 --> 00:04:58.573
Then we actually want to
place that data in the queue.

00:04:58.573 --> 00:05:01.490
In this case, placing it in the
correct location of our array,

00:05:01.490 --> 00:05:05.040
and then we want to change the size
of the queue, how many elements we

00:05:05.040 --> 00:05:07.050
currently have.

00:05:07.050 --> 00:05:07.990
>> So let's get started.

00:05:07.990 --> 00:05:10.890
Here is, again, that general
form function declaration

00:05:10.890 --> 00:05:13.980
for what enqueue might look like.

00:05:13.980 --> 00:05:14.910
And here we go.

00:05:14.910 --> 00:05:18.335
Let's enqueue the number
28 into the queue.

00:05:18.335 --> 00:05:19.460
So what are we going to do?

00:05:19.460 --> 00:05:23.390
Well, the front of our queue is
at 0, and the size of our queue

00:05:23.390 --> 00:05:29.680
is at 0, and so we probably want to put
the number 28 in array element number

00:05:29.680 --> 00:05:31.124
0, right?

00:05:31.124 --> 00:05:32.540
So we've now placed that in there.

00:05:32.540 --> 00:05:34.820
So now what do we need to change?

00:05:34.820 --> 00:05:37.090
We don't want to change
the front of the queue,

00:05:37.090 --> 00:05:40.850
because we want to know what element
we might need to dequeue later.

00:05:40.850 --> 00:05:44.020
So the reason we have front there
is sort of an indicator of what's

00:05:44.020 --> 00:05:46.439
the oldest thing in the array.

00:05:46.439 --> 00:05:49.730
Well the oldest thing in the array-- in
fact, the only thing in the array right

00:05:49.730 --> 00:05:53.540
now-- is 28, which is
at array location 0.

00:05:53.540 --> 00:05:56.160
So we don't want to
change that green number,

00:05:56.160 --> 00:05:57.910
because that's the oldest element.

00:05:57.910 --> 00:06:00.510
Rather, we want to change the size.

00:06:00.510 --> 00:06:04.110
So in this case, we'll
increment size to 1.

00:06:04.110 --> 00:06:08.430
>> Now a general sort of idea of where the
next element is going to go in a queue

00:06:08.430 --> 00:06:12.310
is to add those two numbers
together, front and size,

00:06:12.310 --> 00:06:16.390
and that'll tell you where the next
element in the queue is going to go.

00:06:16.390 --> 00:06:18.130
So now let's enqueue another number.

00:06:18.130 --> 00:06:20.250
Let's enqueue 33.

00:06:20.250 --> 00:06:24.480
So 33 is going to go into
array location 0 plus 1.

00:06:24.480 --> 00:06:26.840
So in this case, it's going
to go into array location 1,

00:06:26.840 --> 00:06:29.500
and now the size of our queue is 2.

00:06:29.500 --> 00:06:31.840
>> Again, we're not changing
the front of our queue,

00:06:31.840 --> 00:06:34.730
because 28 is still the
oldest element, and we

00:06:34.730 --> 00:06:38.220
want to-- when we eventually get
to dequeuing, removing elements

00:06:38.220 --> 00:06:43.300
from this queue, we want to know
where the oldest element is.

00:06:43.300 --> 00:06:48.620
And so we always need to maintain
some indicator of where that is.

00:06:48.620 --> 00:06:50.410
So that's what the 0 is there for.

00:06:50.410 --> 00:06:52.910
That's what front is there for.

00:06:52.910 --> 00:06:55.022
>> Let's in enqueue one more element, 19.

00:06:55.022 --> 00:06:56.980
I'm sure you can guess
where 19 is going to go.

00:06:56.980 --> 00:06:59.860
It's going to go into
array location number 2.

00:06:59.860 --> 00:07:01.570
That's 0 plus 2.

00:07:01.570 --> 00:07:03.199
And now the size of our queue is 3.

00:07:03.199 --> 00:07:04.240
We have 3 elements in it.

00:07:04.240 --> 00:07:08.490
So if we were to, and we're not going
to right now, enqueue another element,

00:07:08.490 --> 00:07:11.370
it would go into array location
number 3, and the size of our queue

00:07:11.370 --> 00:07:13.160
would be 4.

00:07:13.160 --> 00:07:15.279
So we've enqueued several elements now.

00:07:15.279 --> 00:07:16.570
Now let's start to remove them.

00:07:16.570 --> 00:07:19.450
Let's dequeue them from the queue.

00:07:19.450 --> 00:07:23.340
>> So similar to pop, which is sort
of the analog of this for stacks,

00:07:23.340 --> 00:07:26.180
dequeue needs to accept a
pointer to the queue-- again,

00:07:26.180 --> 00:07:28.140
unless it's globally declared.

00:07:28.140 --> 00:07:31.610
Now we want to change the location
of the front of the queue.

00:07:31.610 --> 00:07:35.050
This is where it sort of comes
into play, that front variable,

00:07:35.050 --> 00:07:37.310
because once we remove
an element, we want

00:07:37.310 --> 00:07:40.720
to move it to the next oldest element.

00:07:40.720 --> 00:07:44.180
>> Then we want to decrease
the size of the queue,

00:07:44.180 --> 00:07:47.130
and then we want to return the value
that was removed from the queue.

00:07:47.130 --> 00:07:48.921
Again, we don't want to just discard it.

00:07:48.921 --> 00:07:51.170
We presumably are extracting
it from the queue-- we're

00:07:51.170 --> 00:07:54.170
dequeuing it because we care about it.

00:07:54.170 --> 00:08:01.080
So we want this function to return
a data element of type value.

00:08:01.080 --> 00:08:04.360
Again, in this case, value is integer.

00:08:04.360 --> 00:08:05.670
>> So now let's dequeue something.

00:08:05.670 --> 00:08:09.310
Let's remove an element from the queue.

00:08:09.310 --> 00:08:15.970
If we say int x equals &q, ampersand q--
again that's a pointer to this q data

00:08:15.970 --> 00:08:20.177
structure-- what element
is going to be dequeued?

00:08:23.840 --> 00:08:29.480
In this case, because it is a first
in, first out data structure, FIFO,

00:08:29.480 --> 00:08:33.690
the first thing we put into this
queue was 28, and so in this case,

00:08:33.690 --> 00:08:37.245
we're going to take 28 out of
the queue, not 19, which is what

00:08:37.245 --> 00:08:38.870
we would have done if this was a stack.

00:08:38.870 --> 00:08:42.220
We're going to take 28 out of the queue.

00:08:42.220 --> 00:08:44.960
>> Similar to what we did with
a stack, we're not actually

00:08:44.960 --> 00:08:47.345
going to delete 28
from the queue itself,

00:08:47.345 --> 00:08:49.470
we're just going to kind
of pretend it isn't there.

00:08:49.470 --> 00:08:51.678
So it's going to stay there
in memory, but we're just

00:08:51.678 --> 00:08:57.820
going to kind of ignore it by moving
the other two fields of our q data

00:08:57.820 --> 00:08:58.830
structure.

00:08:58.830 --> 00:09:00.230
We're going to change the front.

00:09:00.230 --> 00:09:04.290
Q.front is now going to
be 1, because that is now

00:09:04.290 --> 00:09:07.740
the oldest element we have in our
queue, because we've already removed 28,

00:09:07.740 --> 00:09:10.460
which was the former oldest element.

00:09:10.460 --> 00:09:13.540
>> And now, we want to change
the size of the queue

00:09:13.540 --> 00:09:15.780
to two elements instead of three.

00:09:15.780 --> 00:09:20.450
Now remember earlier I said when we
want to add elements to the queue,

00:09:20.450 --> 00:09:26.000
we put it in an array location
which is the sum of front and size.

00:09:26.000 --> 00:09:29.050
So in this case, we're still putting
it, the next element in the queue,

00:09:29.050 --> 00:09:33.360
into array location 3, and
we'll see that in a second.

00:09:33.360 --> 00:09:35.730
>> So we've now dequeued our
first element from the queue.

00:09:35.730 --> 00:09:36.480
Let's do it again.

00:09:36.480 --> 00:09:38.696
Let's remove another
element from the queue.

00:09:38.696 --> 00:09:42.400
In the case, the current oldest
element is array location 1.

00:09:42.400 --> 00:09:44.220
That's what q.front tells us.

00:09:44.220 --> 00:09:46.980
That green box tells us that
that's the oldest element.

00:09:46.980 --> 00:09:49.310
And so, x will become 33.

00:09:49.310 --> 00:09:52.130
We'll just kind of forget
that 33 exists in the array,

00:09:52.130 --> 00:09:55.100
and we'll say that now, the
new oldest element in the queue

00:09:55.100 --> 00:09:58.900
is at array location 2, and the size
of the queue, the number of elements

00:09:58.900 --> 00:10:02.152
we have in the queue, is 1.

00:10:02.152 --> 00:10:05.110
Now let's enqueue something, and I
sort of gave this away a second ago,

00:10:05.110 --> 00:10:10.340
but if we want to put 40 into the
queue, where's 40 going to go?

00:10:12.880 --> 00:10:17.730
Well we've been putting it
in q.front plus queue size,

00:10:17.730 --> 00:10:20.850
and so it makes sense to
actually to put 40 here.

00:10:20.850 --> 00:10:22.840
Now notice that at
some point, we're going

00:10:22.840 --> 00:10:27.980
to get to the end of
our array inside of q,

00:10:27.980 --> 00:10:32.010
but that faded out 28 and 33--
they're actually, technically

00:10:32.010 --> 00:10:33.300
open spaces, right?

00:10:33.300 --> 00:10:36.040
And so, we may eventually--
that rule of adding

00:10:36.040 --> 00:10:40.390
those two together-- we may eventually
need to mod by the size of capacity

00:10:40.390 --> 00:10:41.410
so we can wrap around.

00:10:41.410 --> 00:10:43.620
>> So if we get to element
number 10, if we're

00:10:43.620 --> 00:10:48.790
replacing it in element number 10, we'd
actually put it in array location 0.

00:10:48.790 --> 00:10:50.997
And if we were going to
array location-- excuse me,

00:10:50.997 --> 00:10:53.080
if we added them up together,
and we got to number

00:10:53.080 --> 00:10:56.330
11 would be where we would have to put
it, which doesn't exist in this array--

00:10:56.330 --> 00:10:58.200
it would be going out of bounds.

00:10:58.200 --> 00:11:03.367
We could mod by 10 and put
it in array location 1.

00:11:03.367 --> 00:11:04.450
So that's how queues work.

00:11:04.450 --> 00:11:08.540
They're always going to go from left
to right and possibly wrap around.

00:11:08.540 --> 00:11:11.280
And you know that they're
full if size, that red box,

00:11:11.280 --> 00:11:13.710
becomes equal to capacity.

00:11:13.710 --> 00:11:16.720
And so after we've added 40 to the
queue, well what do we need to do?

00:11:16.720 --> 00:11:19.890
Well, the oldest element
in the queue is still 19,

00:11:19.890 --> 00:11:21.990
so we don't want to change
the front of the queue,

00:11:21.990 --> 00:11:23.820
but now we have two
elements in the queue,

00:11:23.820 --> 00:11:28.710
and so we want to increase
our size from 1 to 2.

00:11:28.710 --> 00:11:31.820
>> That's pretty much it with
working with array-based queues,

00:11:31.820 --> 00:11:33.630
and similar to stack,
there is also a way

00:11:33.630 --> 00:11:36.450
to implement a queue as a linked list.

00:11:36.450 --> 00:11:40.150
Now if this data structure type
looks familiar to you, it is.

00:11:40.150 --> 00:11:43.780
It's not a singly linked list,
it's a doubly linked list.

00:11:43.780 --> 00:11:46.790
And now, as an aside, it is
actually possible to implement

00:11:46.790 --> 00:11:50.160
a queue as a singly linked list, but
I think in terms of visualisation,

00:11:50.160 --> 00:11:53.350
it actually might help to view
this as a doubly linked list.

00:11:53.350 --> 00:11:56.850
But it is definitely possible to
do this as a singly linked list.

00:11:56.850 --> 00:12:00.110
>> So let's have a look at
what this might look like.

00:12:00.110 --> 00:12:02.750
If we want to enquue--
so now, again we're

00:12:02.750 --> 00:12:05.360
switching to a linked-list
based model here.

00:12:05.360 --> 00:12:08.420
If we want to enqueue, we want
to add a new element, well

00:12:08.420 --> 00:12:09.730
what do we need to do?

00:12:09.730 --> 00:12:12.770
Well, first of all, because
we're adding to the end

00:12:12.770 --> 00:12:15.520
and removing from the
beginning, we probably

00:12:15.520 --> 00:12:20.050
want to maintain pointers to both the
head and the tail of the linked list?

00:12:20.050 --> 00:12:22.660
Tail being another term for
the end of the linked list,

00:12:22.660 --> 00:12:24.496
the last element in the linked list.

00:12:24.496 --> 00:12:26.620
And these will probably,
again, be beneficial to us

00:12:26.620 --> 00:12:28.477
if they are global variables.

00:12:28.477 --> 00:12:31.060
But now if we want to add a new
element what do we have to do?

00:12:31.060 --> 00:12:35.262
What we just [? malak ?] or dynamically
allocate our new node for ourselves.

00:12:35.262 --> 00:12:38.220
And then, just like when we add any
element to a doubly linked list we,

00:12:38.220 --> 00:12:40.410
just have to sort of--
those last three steps here

00:12:40.410 --> 00:12:43.330
are just all about moving the
pointers in the correct way

00:12:43.330 --> 00:12:46.710
so that the element gets added to
the chain without breaking the chain

00:12:46.710 --> 00:12:49.580
or making some sort of mistake
or having some sort of accident

00:12:49.580 --> 00:12:54.505
happen whereby we accidentally
orphan some elements of our queue.

00:12:54.505 --> 00:12:55.880
Here's what this might look like.

00:12:55.880 --> 00:13:00.980
We want to add the element
10 to the end of this queue.

00:13:00.980 --> 00:13:03.380
So the oldest element here
is represented by head.

00:13:03.380 --> 00:13:06.800
That's the first thing we put
into this hypothetical queue here.

00:13:06.800 --> 00:13:10.430
And tail, 13, is the most
recently added element.

00:13:10.430 --> 00:13:17.030
And so if we want to enqueue 10 into
this queue, we want to put it after 13.

00:13:17.030 --> 00:13:19.860
And so we're going to dynamically
allocate space for a new node

00:13:19.860 --> 00:13:23.280
and check for null to make sure
we don't have a memory failure.

00:13:23.280 --> 00:13:27.040
Then we're going to
place 10 into that node,

00:13:27.040 --> 00:13:30.030
and now we need to be careful
about how we organize pointers

00:13:30.030 --> 00:13:32.180
so we don't break the chain.

00:13:32.180 --> 00:13:38.910
>> We can set 10's previous field
to point back to the old tail,

00:13:38.910 --> 00:13:41.620
and since '10 will be the
new tail at some point

00:13:41.620 --> 00:13:44.459
by the time all of these
chains are connected,

00:13:44.459 --> 00:13:46.250
nothing's going to come
after 10 right now.

00:13:46.250 --> 00:13:49.880
And so 10's next pointer
will point to null,

00:13:49.880 --> 00:13:53.580
and then after we do this, after we've
connected 10 backwards to the chain,

00:13:53.580 --> 00:13:57.780
we can take the old head, or, excuse
me, the old tail of the queue.

00:13:57.780 --> 00:14:02.980
The old end of the queue,
13, and make it point to 10.

00:14:02.980 --> 00:14:08.220
And now, at this point, we have
enqueued the number 10 into this queue.

00:14:08.220 --> 00:14:14.740
All we need to do now is just move the
tail to point to 10 instead of to 13.

00:14:14.740 --> 00:14:17.630
>> Dequeuing is actually
very similar to popping

00:14:17.630 --> 00:14:21.710
from a stack that is
implemented as a linked list

00:14:21.710 --> 00:14:24.040
if you've seen the stacks video.

00:14:24.040 --> 00:14:27.280
All we need to do is start at the
beginning, find the second element,

00:14:27.280 --> 00:14:30.480
free the first element,
and then move the head

00:14:30.480 --> 00:14:32.930
to point to the second element.

00:14:32.930 --> 00:14:37.920
Probably better to visualize it
just to be extra clear about it.

00:14:37.920 --> 00:14:39.230
So here's our queue again.

00:14:39.230 --> 00:14:42.600
12 is the oldest element
in our queue, the head.

00:14:42.600 --> 00:14:46.210
10 is the newest element
in our queue, our tail.

00:14:46.210 --> 00:14:49.310
>> And so when we want
to dequeue an element,

00:14:49.310 --> 00:14:52.202
we want to remove the oldest element.

00:14:52.202 --> 00:14:52.910
So what do we do?

00:14:52.910 --> 00:14:55.243
Well we set a traversal pointer
that starts at the head,

00:14:55.243 --> 00:14:57.840
and we move it so that it
points to the second element

00:14:57.840 --> 00:15:02.290
of this queue-- something by saying trav
equals trav arrow next, for example,

00:15:02.290 --> 00:15:07.170
would move trav there to point to
15, which, after we dequeue 12,

00:15:07.170 --> 00:15:13.030
or after we remove 12, will
become the then-oldest element.

00:15:13.030 --> 00:15:16.360
>> Now we've got a hold on the first
element via the pointer head

00:15:16.360 --> 00:15:19.440
and the second element
via the pointer trav.

00:15:19.440 --> 00:15:25.170
We can now free head, and then we can
say nothing comes before 15 anymore.

00:15:25.170 --> 00:15:29.990
So we can change 15's previous
pointer to point to null,

00:15:29.990 --> 00:15:31.874
and we just move the head over.

00:15:31.874 --> 00:15:32.540
And there we go.

00:15:32.540 --> 00:15:35.840
Now we have successfully
dequeued 12, and now we

00:15:35.840 --> 00:15:39.180
have another queue of 4 elements.

00:15:39.180 --> 00:15:41.700
That's pretty much all
there is to queues,

00:15:41.700 --> 00:15:45.810
both array-based and linked-list based.

00:15:45.810 --> 00:15:46.860
I'm Doug Lloyd.

00:15:46.860 --> 00:15:49.100
This is CS 50.