OK.
So this lecture is going to be pretty short.
I just need to introduce a couple of data structures for the next section, and that is going to be
stacks and Qs, and we are just going to be using the standard template library and versions of these.
So we will just be including those libraries for stacks and queue.
We're not going to create our own data structures, kind of how we did with link lists and things like
that.
But I just want to introduce them.
I'm going to do this theoretical video, which would be really short.
And then I'll do a quick little implementation and it'll be one file, you know, and something really
basic just to show how they work and how the functions work with them.
So, yeah, let's go ahead and get started.
So first off, we're going to talk about a stack.
A stack is what you consider a last in, first out or abbreviated like this LIFO data structure.
So basically, the last thing that was added is going to be the first one that we have access to to
take out.
That's kind of like the order in which things happen.
So we've talked about stacks a little bit when we are talking about recursion, that stack we were talking
about was actually a stack in memory.
So we have the, you know, the call stack in memory.
When we had recursive calls which were like stack frames, the function, the function calls or stack
frames in memory that we're kind of stacking up.
It's pretty much the same thing that we're talking about now, but you can just imagine it like a standard
data structure similar to like a vector when you push back to a vector.
We also have a stack that we're just going to use, like an STL stack data structure, and you have
these three operations down here.
So you see this include stack right here.
That's something we'll have to do to use that steel container and then pushing into the stack is basically
adding something on top.
So like this, we push something and you can imagine this kind of like a stack of plates.
I think I use that analogy before, like pancakes or something like that.
We basically start at the bottom and we just stack things on top of each other, hence the name stack.
And then when you take something off this, you know, out of these three of the most basic operations,
most fundamental operations that we're using on this pop is where you will take something off the top.
So you can imagine that you only have access to the top of this data structure and given time, and
you can either push something or pop something off.
So we have the push and then we have the pop, which we take that top element off of the stack, and
then we also have this third thing that just lets us refer to and grab like the top element.
So top let us refer to the top element and be able to see what the thing is at the top of the stack.
So that is how Stack works.
Very simple, you know, things just stack on top of each other and you basically have access to the
top element here.
So if you wanted to take everything out, you'd have to start with that pop and pop from the top back
to the bottom.
OK, so with that, let's look at the queue.
The queue is the obvious, first in, first out data structure.
So very similar to like I mean, you can basically implement this with a vector as well, so very similar
to the vector, you know how you push back to a vector.
And then you might like loop through it going from the first to the last or something like that, you
might like reference to the first item and then loop through till the end of the vector until you get
to the end.
That would be kind of like the same ideas as a cue.
But there actually is a cutaneous structure that would be including and it is like a cue in real life.
If you think of like a cue as in people waiting for, you know, a teller at a bank or something like
that.
You know, people are waiting in line.
And it's kind of like a first come, first serve.
So the first thing to arrive is like the first thing to, you know, go out, so get served and and
leave.
So that would be, you know, like the last the.
The oldest thing is the first out.
Basically, you know, the person that's been there the longest.
And so we have, you know, a similar thing.
We're going to include Q and it's already in the structure, which is nice.
A lot of the things that we've been doing so far.
There's like, you know, a list data structure that's included in the standard template library, I
believe, but we've been kind of making our own things.
You know, just like the stack, we're going to actually use something that's already been implemented.
And so we have these three big operations here as well.
You know, there I think there's other functions that you can use from the queue, but these are the
three main ones I'm going over, so we have a push which push us to the back pop, which pops the front
and we have a get front.
So kind of similar to the to the stack, except we're building it out the opposite direction.
So if you imagine the stack kind of turned sideways, like flopped on its side.
Like, I'm going back here, so if you took like this whole thing and rotated it, so these bars were
pointing up, then we would kind of be building from right to left like stacking stuff out this way.
But the Q is the opposite, it's going to build out from left to right.
If we're thinking of those being on the same, like playing there.
OK, so I'm just using like faces for people, if you're imagining those people waiting in line at like
a bank or something like that.
So this would be us pushing something to the queue.
And then we push something else, and I have a Green Line, you know, just referring to the front.
And so we push again, we push again, we push again.
And push again, so it builds out from left to right there, and the front is the thing that can potentially
be the first out, that is the Green Line.
So we're referring to the person that's been there the longest over here.
So now if we do pop in, we're referring to that first person.
It'll pop different, so we pop that person at the next one and the next one, the next one.
And now we're just on our last person.
So hopefully that explains it pretty simple data structures here.
I'm just giving this brief explanation of them so we can use them in the next section, which is going
to be about graph algorithms.
So well, we're going to need to use Qs and Stack, so I want to make sure that they're understood before
we get into those algorithms.
All right.
So with that, I'll see you in the next video to this be a quick implementation of these nine implementation,
but just using them in a small see purpose program.