Hello again! In this video, we are going to look at the stack data structure. This works rather like
a pile of plates, so let's remind ourselves what that looks like.
We're going to specify that we can only add or remove one plate at a time from this pile.
If we want to remove a plate, we have to take this one off the top.
And then the one below that now becomes the top of the pile.
And if we take that one off, the one below becomes the top and so on.
If we add some more plates, we have to add them one at a time, at the top.
So we add a new plate here. And that now becomes the top of the pile. And we can add another plate on
top of that, and so on.
So the plate at the top is always the last one which was added to the pile, and the plate at the bottom
is always the first one which was added to the pile.
When we take a plate from the top of the pile, it will always be the last one which was added.
In the stack data structure, the elements are stored in the order in which they were added to the stack.
When we add a new element to this attack, it is inserted at the top. And we can only access the top
element of the stack.
To process the stack, we need to get the top element and remove it. So the element which was
below that now becomes the top element. Then we can access that. And so on.
The elements are removed in the reverse order they were added.
So the last element which was added is always the first one to be removed. And this is known as a
"LIFO" structure. Short for "Last In, First Out".
So it works something like this. So imagine we have a data structure with three elements.
We added 1, then 2 and then 5. So 5 is currently the top element.
If we add another element, it's going to go above 5.
Like that.
So we now have 3 as the top element.
If we come along and remove the top element, then this 3 will be removed.
And then 5 is going to be the top again.
So it will look like that.
C++ has a stack class in the library.
It is implemented using a deque, for the same reason that the queue uses a deque.
The interface is very similar to priority queue.
We can use push() and pop() to add and remove elements, at the top of the stack only. top() will return the element
from the top of the stack, but leave it there.
So this is like top() in the priority queue.
We can inspect the value, but not modify it, because it is returned as a reference to const. And there
are also empty() and size() member functions.
So let's try this out.
We include the header, and then we can create a stack object.
We call push() to insert some elements.
So 1 is the first element, then 2.
So 2 will go above 1. And then 5.
So 5 will go above 2. And 5 is currently the top of the stack.
We have this function for printing out some information about the stack.
Then, when we add a new element, this will go on the top of the stack.
So if we call top(), we will now get 3 as the top of the stack.
And for removing an element, this will take the top element off.
So this will remove the element with value 3, and we go back to having 5 at the top.
So there we are, we start off with our three elements with five at the top.
Then we add 3, and that goes to the top. And then we remove this top element, and we go back to
the stack that we had before.
Stacks are actually very useful in computing.
They're used by the C++ runtime for managing local variables,
as we all know. Compilers also use them for breaking down expressions into sub-expressions.
You can use them for checking for unbalanced parentheses in source code.
Every time you encounter an open bracket, you push it onto your stack.
And when you meet a closing bracket, then you pop it off the stack.
And if you get some stack error, or you get to the end of the file and you have some elements left,
then you know that the brackets are not balanced correctly.
You can also use it for implementing undo functionality. So every time the user edits the text, or your
program changes something, you can push the old state onto the stack. And then you can just pop it off
to get back to where it was.
And also for browser history, when you're on the web. Every time you go to a new URL, you can
push it onto a stack.
OK, so that is it for this video.
I will see you next time, but until then, keep coding!