In this video, we'll learn about our first STL adapter container, the stack.
The stack is a last-in, first-out data structure.
It's an adapter because it's implemented in terms of already
existing STL containers.
Since all operations on a stack happen on only one end, the top.
We can easily implement a stack based on any container that has a back.
These are vector, list, and deque.
So, the way that the stack methods work is they use delegation.
And they call the back, push back, and pop back methods
of the underlying container.
Stacks have wide applications in computer science, and the STL provides
a simple concise implementation.
You can think of a stack as a stack of books or a stack of plates.
If we stack plates one on top of the other, we can't pull out a
plate from the middle or from the bottom, instead we add plates at the
top and remove them from the top.
Since stacks are limited to insertions and deletions only one end.
Iterators really don't make sense and they're not supported.
So, we can't use stacks with STL algorithms.
In order to use the stack container, we have to include the stack header file.
The stack provides a handful of methods that have well-defined behavior.
The push method inserts an element at the top of the stack.
The pop method removes an element from the top of the stack.
The top method accesses the top element of the stack but it doesn't remove it.
Finally, we have the empty and size methods that we've already
seen in the other STL containers.
Since the stack is an adapter class, we can choose what
underlying container will be used when we create our stack objects.
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 three examples that I'm explicitly
stating which underlying container to use in the template parameter.
So, let's see how the push method works.
Suppose we have a stack of integers named ‘s’ and it's empty.
When we push 10 onto the stack, we add 10 at the top of the stack.
You can see the top of the stack is the shaded box in the diagrams.
We then push 20, now 20 becomes the top of the stack.
Finally, we push 30 and the 30 becomes the new top of the stack.
Once we have a stack that contains elements, we can access
the element at the top of the stack with the top method.
This returns a reference to the element at the top.
It does not remove it.
In this example, s.top returns 30, which we display.
Now, if we pop the stack, the element at the top is removed.
In this case, the 30 and now the 20 becomes the new top of the stack.
If I pop the stack again, the 20 is removed, and now the 10
is the new top of the stack.
If we call the size method for s here, it will display 1 since there's
just one element left in the stack.
As you can see the stack api is very straightforward.
But a stack is extremely useful, and it's used in computer science
to solve many types of problems.
Let's head over to the ide, we'll see some stack examples.
Okay, so I'm back in the ide.
I'm in the section 20 workspace in the stack project.
This is a really simple example.
There's not really a lot we can do with a stack.
Push, pop and top, that's about it.
So, let's go over a few examples here.
I'm including stack right here.
So, I'm going to use it. I'm also including vector list, just I'm going to show you how you can
create those stacks based on vector and the list underlying container.
So, that's the only reason I'm including them.
I'm really not using it.
I just wanted to show you how you would declare it here.
But let's talk about this template function.
This is the one that's going to display a stack.
We can't use iterators with stacks, so there's no real
way to display a stack easily.
The only way to display a stack is to let's say, we've got a
stack here with the 10 and a 20, and I want to display it.
I need to get the top display it, pop it, get the top, display it, pop it.
So, it's a destructive process.
Because of that I'm passing in this stack by value.
I don't want to upset the stack that's being passed into me at all.
I don't want to modify it at all.
So, that's making a copy, and what I'm doing over here is
I'm destroying that copy which is fine.
Once I finish this function, the stack that's being passed into
me has not been modified at all.
And you can see the code, it's pretty straightforward.
This is a template function.
There's the type right here.
We're using integer stacks in this example.
And while the stack is not empty, I'm getting the top element of the stack.
Then I'm deleting it from the stack, and then I'm displaying it.
That's it. So, that's just going to display my stack, and you can see the
output over here and I'll go over that in just a second.
Alright, so let me scroll up.
And there's no tests here.
It's just domain which is pretty straightforward.
Let's go over these examples here.
Here, I'm creating a stack of integers.
I call it ‘s’, that's the one.
We're going to use in these examples.
But I can also create s1, s2, and s3, that are stacks of integers
but the underlying container would be a vector, a list, or
a deque, whatever you choose.
On line 25 here, you can see that I'm just not providing anything in
which case it defaults to a deque.
Alright, so let's push some values on the stack, and pop them off, and
play around with it a little bit.
Let me just scroll up just a little bit right about there.
Okay, so I've got that stack s that I've already defined.
And what I want to do is I want to use a range base for loop that's
going to loop over this range right here, 1, 2, 3, 4, 5, and it's going to
push those numbers onto that stack s.
Remember, let's assume that this is my stack right here.
The numbers are being pushed this way and then popped off.
So, first, I'm going to push 1, and then 2, and then
3, and then 4, and then 5.
So, that's the situation right now.
Then I'm going to call display.
Remember, display's going to make a copy of this stack,
it's not going to mess with this one.
And what it's going to do is it's going to pop the elements off the stack.
So, it's going to pop off the 5, the 4, the 3, the 2, and the 1.
Remember, everything happens up here at the top.
So, it's going to display exactly what I just said.
5,4,3,2,1, you can see 5 was the top of the stack in that copy.
Now if I pop two elements off of this stack, the 5 and the 4.
I'm sorry, I missed one step right here, let's back up to that.
In this case, I'm pushing 100 onto the stack, so I'm pushing 100 onto here.
And then I'm displaying that stack again.
And now, you can see that the 100 is there.
The 100 is now at the top of the stack.
Now I'm popping off two elements off the stack, the 100 and the 5
are being popped off the stack.
So, the top of my stack now is the 4.
And when I display my stack right here on line 39, you can
see it's displaying 4,3,2 and 1.
In this code here on line 41, I'm just looping while the stack is not empty.
So, as long as the stack is not empty, I'm deleting stuff in it.
This is how we can clear a stack.
There is no dot clear method for a stack.
So, this is how you would clear it.
You would just have to pop everything off of it.
Then when we display the stack here on line 43, we get the empty stack
which is exactly what we expected.
What's the size of that stack?
It better be zero.
Alright, because it's empty and that's exactly what it is, right here, zero.
And the last thing I wanted to show you is suppose, I push 10 onto the stack.
Remember that stack is gone.
It's empty now.
So, let's say I wanted to push 10 onto the stack just like I did right here.
And then I display the stack.
I get back at 10.
Top returns a reference to the top of the stack.
The top of the stack right now is the 10.
It's a reference, so I can modify it.
I could say s.top is 100.
So, I can change that top to 100 now.
So, when I display the stack, you can see it's displaying 100 right here.
Okay, I think that's about it.
That's really all there is to a stack.
It's a very, very, specific data structure that we're going to use.
When you use it, all you care about is pushing, popping, top
checking to see if it's empty.
That's it.
You're not concerned with anything else.
Those are the only methods that are important and those are
only methods you actually want.
If you've got a stack that gives you a bunch of other methods,
it's not really a stack, and then, you know, be careful.
Because you don't want to have a stack of integers, let's say 10, 20, and 30.
And that whatever thing you're using that you think might be a
stack is letting you have access to these guys that's not a stack.
Stack everything happens right up here at the top.
Sometimes, you'll see these data structures defined by programmers
that have pushes, and pops, and insert stack, and all kinds of things.
And it's not really a stack, it's just a mess.
Okay, in this case, this is a true stack.
It supports exactly what a stack is supposed to support.
Alright, in the next video, we'll talk about the queue
which is a waiting line.
And of course, here you can see that the last one in was the first one out.
That's why the stack is called a LIFO data structure.
The queue is called a FIFO data structure.
So, the first one in is the first one out like a waiting line or
a waiting queue, And that's what we'll talk about in the next video.