In this video, we'll learn about the queue.
The queue is a first-in, first-out data structure.
Like the stack, the queue is an adapter class because it's implemented in terms
of already existing STL containers.
Since operations on the queue happen on both ends, the front and
the back, we can easily implement a queue based on any container
that has a front and the back.
These are the list and the deque.
So, the queue methods use delegation, and call the methods
of the underlying container.
Like stacks, queues have wide applications in computer science.
And the STL provides a simple concise implementation.
You can think of a queue as a waiting line, elements enter on one
end and are removed from the other.
As with stacks, iterators really don't make sense with queues
and they're not supported.
So, we can't use the STL algorithms either.
In order to use the queue containers, we must include the queue header file.
Like the stack, the queue provides a handful of methods that have
very well-defined behavior.
The push method inserts an element at the back of the queue.
The pop method removes an element from the front of the queue.
The front and back methods access the front and back elements of the
queue, but does not remove them.
Finally, we have the empty and size methods that we've seen
with the other containers.
Since the queue is an adapter class, we can choose what
underlying container will be used.
Same thing we did with the stack.
In the first example, I'm providing no information about
the underlying container, so the STL will use a deque by default.
You can see in the next two examples that I'm explicitly
stating which underlying container to use as the template parameter.
Now let's see how the push method works.
Suppose we have a queue of integers named q and it's empty.
When we push 10 onto the queue, we add 10 to the back of the queue.
In this case, the queue was empty.
So, 10 is both the back and the front element in the queue.
Then when we push 20, we push it at the back of the queue.
So, now 10 is at the front of the queue and 20 is at the back of the queue.
You can see the front of the queue is the shaded box in the diagrams.
The back of the queue is the other end.
We then push 30 at the back of the queue.
Once we have a queue that contains elements, we can access the
elements at the front and at the back without removing them
with the front and back methods.
In this example, q.front will display 10, and q.back will display 30.
Now when we pop elements from the queue, they're removed from the front.
The first q.pop removes the 10 from the front of the queue, and now 20
becomes the new front of the queue.
The second q.pop removes the 20 from the front of the queue, and now 30
becomes the new front of the queue.
If we call the size method for the queue here, we'll display 1 since
there's one element in the queue.
As you can see the queue is really a very simple data structure
but like the stack, it's used extensively in computer science
to solve many types of problems.
So, let's head over to the ide.
And we'll see some q examples.
Okay, so I'm back in the ide.
I'm in the section 20 workspace.
And I'm in the queue project.
And just like the stack, the queue is really, really, simple.
So, let's go over some of these examples.
First thing you'll see is I've already got the run over here on the right and
I'll discuss that in just a second.
First thing you'll see is I've got this template function that
displays the queue very similar to what we did with the stack.
In this case, I'm passing by value because I don't want a
reference to the real queue.
And I don't want to destroy it.
So, this is going to make a copy of the cube that's passed in, and
that's the one I'm going to process.
So, how do I display this?
Well, while the queue is not empty, I'm going to get
the element from the front.
Remember with the queue, we push on the back, and we pop from the front.
So, this is first-in, first-out.
Alright, so it's like a waiting line.
Someone gets in at the back of the line, they come off
in the front of the line.
So, I'm getting the element from the front.
I'm removing it from the queue.
I'm displaying it.
That's it, really, really, simple.
Okay, so let's talk about main again.
There's only one test here right in my main.
First thing I'm doing is I'm creating a queue right here
and it's a queue of integers.
Again this could be just about any type and I'm pushing
1,2,3,4 and 5 onto the queue.
Now remember I'm pushing at the back, so when I push 1.
I'm pushing it at the back.
Then 2, then 3, then 4, then 5.
I display the queue. And this is what I'm getting right here.
Now what's the front, what's the back?
Let's be sure that we understand what's going on here.
We can say q.front, q.back, and you can see that the front
here is the one, makes sense.
It's the first one that I pushed on.
First customer in line is the first customer out of the line.
So, that's the front, the back is the 5.
Now I want to push a 100 onto the back of the queue,
and display the queue again.
And you can see the output right here, you can see the 100 here
is at the back of the queue.
I want to pop two elements from the front of the queue.
So, what happens is the 1 and the 2 get removed from
the front, and they're gone.
So, now what's left is 3,4, 5, and a 100.
Three is at the front, 100 is at the back.
If I want to remove everything from the queue, I need to use
some sort of loop like this.
We can't use iterators with the queues.
So, while the queue is not empty, pop the front element out of there.
And when I'm done, it'll be empty, and I display the queue.
And I will get an empty queue just like you see right there.
When I display the size of that queue, I'm right here.
It's down line 42, I will get a zero because it's empty right now.
And let me just clear this and I'll scroll up.
And there's a few more lines, not too many.
So, we're right here, we're on line 44.
I've got an empty queue at this point, I just printed out the size right here.
So, I'm going to push 10, 100 and then a 1000 onto the
queue, and display the queue.
There you go. You can see 10 is at the front, 1000 is at the back.
And you can see that that being displayed right here.
10 is at the front, 1000 is at the back.
Now I have access to the front and the back.
The front method and the back method return references.
So, if I wanted to change the front or change the back, I can.
So, in this case, I'm setting whatever element it is at the
front to 5 and at the back to 5000.
You can see them change right there.
Right, they were 10, now it's 5 was the 1000, now it's 5000.
And you can see again that the front of the queue is the 5 and
the back of the queue is the 5000.
So, that's it in a nutshell, that's the queue.
So, remember this is first-in, first-out as opposed to the stack
which was the last-in, first-out.
And there's uses for all of these first-in, first-out
queues are used all the time for scheduling, job scheduling, task
scheduling, and operating systems.
Stacks are used a lot in compiling.
They're used a lot to solve problems where you have to calculate
expressions, and you have to figure out how many parentheses are there?
Do they balance and things like that?
Okay, so, that's it.
In the next video, what we'll do is we'll do a challenge that's
going to use stacks and queues.
And remember that palindrome example, we did a while back with the deque.
We're going to do the same thing except we're going to use a
stack and a queue to solve it.