What I'm going to do now is go over a fixed-sized queue data structure
that's going to serve as a running example for some of this lecture,
and we're also going to keep using for a couple of our exercises for the next several units.
And the way this data structure works is it supports an enqueue operation,
a dequeue operation, an enqueue elements to dequeue and FIFO order.
The FIFO is first in first out--so if we enqueue 7 and then also 8, the first thing that we dequeue.
will be 7 then 8, and if we try to dequeue again--if we try do dequeue an element
with an empty queue, we're going to get some sort of an error.
Okay, so that's all fixed-sized queue. Now let's look at some code.
So in the implementation site--what we have here is a Python object so it's called queue
and the constructor for that object is going to set up the data structure because structure
for that object is going to take a size max argument--that's going to determine the largest
number of objects that can be stored in our queue and it's going to set up the data structure.
So first it's going to make sure that size max is greater than zero.
It's going to save a temporary copy of that, initialize some head and tail pointers,
a size variable which stores the number of objects currently in the queue,
and finally we need to reserve some space for the queque elements themselves.
But you can see here is we're allocating a Python array and so one implementation option
for a queue in Python will be to just use a Python list and that will be basically trivial.
Python list already is pretty much need of a support enqueue and dequeue operations
and the problem with the Python list is they're dynamically allocated,
they are dynamically tight and that makes them not very fast.
And so by allocating a fixed-sized storage region of statically tight memory,
where the "i" here means that our queue is only going to be able to store integers
we can avoid some of Python's dynamic checks that makes the queue slow
and so in some cases, a queue based on a Python list is perfectly fast but on the other hand
in some benchmarking that I did, this statically sized, statically tight queue
is more than 10 times faster than a queue based on a Python list.
So the first method that queue supports is the empty method and this simply returns true if
self.size equals zero--so of course the empty queue is the one that currently contains zero elements.
Very similarly, the full queue method returns true if the current size of the queue
is equal to the maximum size of the queue.
So now let's look at a couple of routines that are slightly trickier.
The enqueue method is going to take an argument x.
X is an integer that we want to try add to the queue.
The first thing this method is going to do is check if the current size of the queue
is the maximum size--if so the queue is full, then we're going to return false.
If we passed this test, of course, the queue is not full and we have room.
So the next thing we're going to do is put the argument data item
into the queue at the location pointed to by the tail.
And so now let me show you a little bit of about how our representation works.
So for demonstration purposes, we're going to look at a 3-element queue
and initially it's going to have a head and a tail according to the first queue element--
that is the queue element with index zero and also its size is going to be zero.
To enqueue an item, the first check will be useful--no it's not because its size is zero.
We go ahead and put the item--let's say it's the number 7 in the queue element pointed to by the tail
We're never going to increment the tail, and now the last thing we have to do to enqueue
an element is increase the size of the queue to be 1.
Okay, now let's go look back at the code.
Seeing here at the code, we can see that we put the element in the queue,
we increased the size of the queue, we moved the tail to point to the next element
and the only thing that's left the only bit of logic that's sort of tricky here is
if the tail of the queue point passed the end of the queue--that is to say if it's equal to the max
and so remember what the zero index array, the maximum way in is going to be one pass
at the end of the queue--we're going to reset the tail to point at the zero element of the queue--
that is to stay at the beginning.
Now the dequeue operation is very similar--first if the size of the queue is zero then the queue
is empty, we're not going to be able to dequeue an item.
And so what we're going to do in this case is return Python to none type.
So none of the special data types supported by Python we can often use to indicate
that we don't have anything--we don't have any actual value.
So if we pass that test, then there is something to return.
So what we're going to do is store the item from the head of the queue in a temporary variable.
So x is going to get 7. We're going to decrement the size of the queue.
We're going to move the tail point out to point the next element and then using logic very similar
to the tail pointer in the enqueue function, we're going to wrap the head pointer around
if it's gone passed the end of the queue.
So let's go back to the drawing and look out and see how this plays out.
So we're going to return 7, decrement the size, and make the head element
point to the next element of the list, and we're not going to bother erasing the 7 we returned
but we're going to have to make sure that our queue logic never returns this dead element.
Oh! So let's take a very quick quiz just to make sure that you understood all of that.