Hello again! In this video, we are going to look at the queue class in the C++ library.
We probably know about queues in the real world.
So here is a queue of people.
The person at the front is the first person to arrive and the person at the back is the latest person
to arrive.
Presumably, they are all waiting to be processed in some way: to be allowed into the venue, or to buy
their ticket, or to collect something.
So these are going to be processed, one person at a time.
The first person will leave the queue, and then the person behind them will then become the first person,
at the front of the queue.
And if any more people arrive, there will be at the back of the queue.
In computer science, there is a data structure called a queue, which is based on similar principles.
The elements in a queue are stored in the order in which they were inserted into the queue, with the first
element at the front, and the most recent element at the back.
As the program processes the queue, the element at the front is removed, and then the element which was
behind it now becomes the front element.
Then that one is processed and removed, and the next one becomes the front, and so on.
Elements can only be removed from the front of the queue. And they can only be removed in the same
order in which they were added.
So a queue data structure looks a bit like this. So we have some elements here.
The one at the front of the queue is the first one which was inserted and the one at the back is the
latest arrival.
If we add another element, then that goes on the back of the queue.
And if we remove an element, that comes off the front of the queue, and then this now becomes the front.
C++ has an implementation of the queue in the library.
The first element which is added to the queue is always the first element to be removed.
So this is an example of a FIFO structure, standing for "First In, First Out". (Not to be confused with FIFA,
which is the International Football Association!)
A queue is usually implemented as a deque, and you might want to think about why that is.
Although it can be implemented as a vector or a list. And the reason for using a queue is that there
are a lot of operations at the front of the container, and that is something that deques are good at.
The interface for a queue is rather limited.
We can use push() or pop(), to add or remove elements. When we use push(), the element goes on the back of
the queue. When we use pop(), the element comes off the front of the queue.
We can also access the front and back elements.
We can find out if the queue is empty, or how many elements there are.
And many of the typical container operations are not supported.
For example, there are no iterators for queues.
So let's look at how to use a queue structure.
We include the queue header. We create a queue object, and then we call push() to insert some elements into
the queue.
So 4 is the first.
So that is going to be the front.
Then 3, 5, and 1 is the last.
So 1 will be the back of the queue.
We have this function for printing out some information.
We cannot print out all the elements, because queues do not support iterators.
But we can print out the front and back elements and also some information about the number of elements
in the queue.
Then we call push() to add another element.
So this will go to the back of the queue. And then we call pop() to remove an element.
So this will remove the element which was at the front of the queue.
So there we are. We have a queue of four elements, with 4 at the front and 1 at the back.
Then when we add the element, the queue now has five elements.
And this new element is the one at the back.
And after removing the front element, the new front element is 3.
And then when we remove the front element, we remove this element 4, and 3 now becomes the front
of the queue.
So what sort of application would use a queue?
Queues are mainly useful if you want somewhere where you can keep data temporarily, and keep that data
in the order in which it arrived.
So, for example, in networking programs, you can have some packets which arrive. For a lot of
protocols,
these assume that the packets are going to be processed in sequence.
So you need to keep these packets in order.
But it may be that the processor is not ready.
Or perhaps it is more efficient to process a lot of elements in bulk, rather than as they come in. Or if you are writing
an inventory system for perishable goods.
So if you have a warehouse which is storing fish, or orange juice, or something which has a fairly short
life, you do not want stock hanging around for longer than necessary.
So you try to make sure that the oldest goods get shipped first, while they are still saleable.
So queues are useful for processing events in the order in which they occur, or processing data in the
order in which it arrives.
We can only access the front element OR the back element, that should be. If you want to be able to
access other elements in the queue, then you could use a vector.
But then you need to manage the ordering yourself.
Or you could use a map, with the arrival order as the key, and the data as the value.
And in that case, the map will order it automatically in arrival time.
A queue does things strictly in order. First come, first served. And sometimes that is not always helpful
in the real world.
For example, if you have a queue of patients who are awaiting treatment, and somebody comes in who needs
an emergency operation, that person needs to get their operation before the other patients get seen
by the doctor.
Or if you have an aeroplane which arrives and misses the take off, then it may need to be moved in
front of aircraft which arrived later.
OK, so that is it for this video.
I will see you next time, but until then, keep coding!