DOUG LLOYD: All right,
so by this point you're
probably pretty familiar
with arrays and linked lists
which is the two primary
data structures we've
talked about for keeping sets of
data of similar data types organized.
>> Now we're going to talk
about a couple of variations
on arrays and linked lists.
In this video we're going
to talk about stacks.
Specifically we're going to talk
about a data structure called a stack.
Recall from previous discussions
about pointers and memory,
that the stack is also the
name for a segment of memory
where statically declared
memory-- memory that you
name, variables that you name, et
cetera and function frames which we also
call stack frames exist.
So this is a stack data structure
not a stack segment of memory.
OK.
>> But what is a stack?
So it's pretty much just a
special kind of structure
that maintains data in an organized way.
And there's two very
common ways to implement
stacks using two data structures
that we're already familiar with,
arrays and linked lists.
What makes a stack special is the
way in which we put information
into the stack, and the way we
remove information from the stack.
In particular with stacks
the rule is only the most
recently added element can be removed.
>> So think about it as if it's a stack.
We're piling information
on top of itself,
and only the thing at the top
of the pile can be removed.
We can't remove the thing underneath
because everything else would
collapse and fall over.
So we really are building a stack that
we then have to remove piece by piece.
Because of this we commonly refer
to a stack as a LIFO structure,
last in, first out.
LIFO, last in, first out.
>> So because of this restriction on
how information can be added to
and removed from a stack, there's really
only two things we can do with a stack.
We can push, which is the
term we use for adding
a new element to the top of the
stack, or if the stack doesn't exist
and we're creating it from scratch,
creating the stack in the first place
would be pushing.
And then pop, that's the sort of CS
term we use to remove the most recently
added element from the top of the stack.
>> So we're going to look at both
implementations, both array based
and linked list based.
And we're going to
start with array based.
So here's the basic idea of what
the array based stack data structure
would look like.
We have a typed definition here.
Inside of that we have two members
or fields of the structure.
We have an array.
And again I'm using the
arbitrary data type value.
>> So this could be any data type,
int char or some other data
type you previously created.
So we have an array of size capacity.
Capacity being a pound defined constant,
perhaps somewhere else in our file.
So notice already with this particular
implementation we are bounding
ourselves as was typically
the case with arrays,
which we cannot dynamically resize,
where there's a certain number
of elements maximum that
we can put in our stack.
In this case it's capacity elements.
>> We also keep track of
the top of the stack.
What element is the most
recently added to the stack?
And so we keep track of that
in a variable called top.
And all of this gets wrapped up together
into a new data type called a stack.
And once we're created
this new data type
we can treat it like
any other data type.
We can declare stack s, just like
we could do int x, or char y.
And when we say stack
s, well what happens
is we get a set of
memory set aside for us.
>> In this case capacity
I've apparently decided
is 10 because I've got a
single variable of type stack
which contains two fields recall.
An array, in this case is going
to be an array of integers
as is the case in most of my examples.
And another integer variable
capable of storing the top,
the most recently added
element to the stack.
So one single stack of what we
just defined looks like this.
It's a box containing
an array of 10 what
will be integers in this case and
another integer variable there in green
to indicate the top of the stack.
>> To set the top of the
stack we just say s.top.
That's how we access a
field of a structure recall.
s.top equals 0 effectively
does this to our stack.
So again we have two operations
that we can perform now.
We can push and we can pop.
Let's start with push.
Again, pushing is adding a new
element to the top of the stack.
>> So what do we need to do in
this array based implementation?
Well in general the
push function is going
to need to accept a
pointer to the stack.
Now take a second and think about it.
Why would we want to accept
a pointer to the stack?
Recall from previous videos on
variable scope and pointers,
what would happen if we just sent
stack, s rather in as a parameter?
What would actually be passed in there?
Remember we're creating a copy
when we pass it to a function
unless we use pointers.
And so this function push needs
to accept a pointer to the stack
so that we're actually changing
the stack we intend to change.
>> The other thing push probably wants to
accept is a data element of type value.
In this case, again, an integer that
we're going to add to the top of stack.
So we've got our two parameters.
What are we going to
now do inside of push?
Well, simply, we're just going to add
that element to the top of the stack
and then change where the top of
the stack is, that s dot top value.
So this is what a function
declaration for push
might look like in an
array-based implementation.
>> Again this isn't a hard and fast rule
that you could change this and have
it vary in different ways.
Perhaps s is declared globally.
And so you don't even need
to pass it is as a parameter.
This is again just a
general case for push.
And there are different
ways to implement it.
But in this case our
push is going to take
two arguments, a pointer to a stack and
a data element of type value, integer
in this case.
>> So we declared s, we
said s.top equals 0.
Now let's push the
number 28 onto the stack.
Well what does that mean?
Well currently the
top of the stack is 0.
And so what's basically
going to happen is
we're going to stick the number
28 into array location 0.
Pretty straightforward, right, that
was the top and now we're good to go.
And then we need to change what
the top of the stack will be.
So that the next time
we push an element in,
we're going to store it in
array location, probably not 0.
We don't want to overwrite
what we just put there.
And so we'll just move the top to 1.
That probably makes sense.
>> Now if we want to put another element
onto the stack, say we want to push 33,
well now we're just going to take 33
and put it at array location number
1, and then change the top of our
stack to be array location number two.
So if the next time we want to
push an element onto the stack,
it'll be put in array location 2.
And let's do that one more time.
We'll push 19 off of the stacks.
We'll put 19 in array location 2
and change the top of our stack
to be array location 3
so if the next time we
need to make a push we're good to go.
>> OK, so that's pushing in a nutshell.
What about popping?
So popping is the sort of
counterpart to pushing.
It's how we remove data from the stack.
And in general pop needs
to do the following.
It needs to accept a pointer to the
stack, again in the general case.
In some other case you might
have declared the stack globally,
in which case you don't need to pass it
in because it already has access to it
as a global variable.
But then what else do we need to do?
Well we were incrementing
the top of the stack in push,
so we're probably going to want
to decrement the top of the stack
in pop, right?
And then of course
we're also going to want
to return the value that we remove.
If we're adding elements, we want
to get elements out later on,
we probably actually
want to store them so we
don't just delete them from the
stack and then do nothing with them.
Generally if we're
pushing and popping here
we want to store this
information in a meaningful way
and so it doesn't make
sense to just discard it.
So this function should
probably return a value to us.
>> So this is what a declaration for pop
might look like there at the top left.
This function returns
data of type value.
Again we've been using
integers throughout.
And it accepts a pointer to a stack as
its sole argument or sole parameter.
So what is pop going to do?
Let's say we want to now
pop an element off of s.
So remember I said that stacks are last
in, first out, LIFO data structures.
Which element is going to
be removed from the stack?
Did you guess 19?
Because you'd be right.
19 was the last element we added to the
stack when we were pushing elements on,
and so it's going to the first
element that gets removed.
It's as if we said 28, and
then we put 33 on top of it,
and we put 19 on top of that.
The only element we can take off is 19.
>> Now in the diagram here what I've done
is sort of deleted 19 from the array.
That's not actually
what we're going to do.
We're just going to kind
of pretend it isn't there.
It's still there in
that memory location,
but we're just going to ignore it
by changing the top of our stack
from being 3 to 2.
So if we were to now push
another element onto the stack,
it would over write 19.
>> But let's not go through the trouble
of deleting 19 from the stack.
We can just pretend it isn't there.
For purposes of the stack it's gone if
we change the top to be 2 instead of 3.
All right, so that was pretty much it.
That's all we need to do
to pop an element off.
Let's do it again.
So I've highlighted it in red here to
indicate we're making another call.
We're going to do the same thing.
>> So what's going to happen?
Well, we're going to store
33 in x and we're going
to change the top of the stack to 1.
So that if we were now to push an
element into the stack which we're
going to do right now,
what's going to happen
is we're going overwrite
array location number 1.
So that 33 that was sort of left
behind that we just pretended
isn't there anymore, we're just going
to clobber it and put 40 there instead.
And then of course,
since we made a push,
we're going to increment the
top of the stack from 1 to 2
so that if we now add
another element it'll
go into array location number two.
>> Now linked lists are another
way to implement stacks.
And if this definition on the
screen here looks familiar to you,
it's because it looks almost
exactly the same, in fact,
it pretty much is exactly the
same as a singly linked list,
if you recall from our discussion of
singly linked lists in another video.
The only restriction here
is for us as programmers,
we're not allowed to
insert or delete randomly
from the singly linked list
which we could previously do.
We can only now insert and delete from
the front or the top of the linked
list.
That's really the only
difference though.
This is otherwise a singly linked list.
It's only the restriction
replacing on ourselves
as programmers that
changes it into a stack.
>> The rule here is to always maintain a
pointer to the head of a linked list.
This is of course a generally
important rule first.
For singly linked list anyway you
only need a pointer to the head
in order to have that
chain be able to refer
to every other element
in the linked list.
But it's particularly
important with a stack.
And so generally you're
going to actually want
this pointer to be a global variable.
It's probably going to
be even easier that way.
So what are the analogs of push and pop?
Right.
So pushing again is adding
a new element to the stack.
In a linked list that
means we're going to have
to create a new node that we're
going to add into the linked list,
and then follow the careful steps
that we've outlined previously
in singly linked lists to add it to
the chain without breaking the chain
and losing or orphaning any
elements of the linked list.
And that's basically what that
little blob of text there summarizes.
And let's take a look
at it as a diagram.
>> So here's our linked list.
It concurrently contains four elements.
And more perfectly here's our
stack containing four elements.
And let's say we now want to
push a new item onto this stack.
And we want to push a new
item whose data value is 12.
Well what are we going to do?
Well first we're going to
malloc space, dynamically
allocate space for a new node.
And of course immediately after
we make a call to malloc we always
make sure to check for null,
because if we got null back
there was some sort of problem.
We don't want to dereference that null
pointer or you will suffer a seg fault.
That's not good.
So we've malloced of the node.
We'll assume we've had success here.
We're going to put 12 into
the data field of that node.
Now do you recall which of our pointers
moves next so we don't break the chain?
We have a couple of options here but
the only one that's going to be safe
is to set news next pointer to
point to the old head of the list
or what will soon be the
old head of the list.
And now that all of our
elements are chained together,
we can just move list to point
to the same place that new does.
And we have now effectively pushed a
new element onto the front of the stack.
>> To pop we just want to
delete that first element.
And so basically what
we have to do here,
well we have to find the second element.
Eventually that will become the new
head after we delete the first one.
So we just need to start from
the beginning, move one forward.
Once we've got a hold on one
forward of where we currently
are we can delete the first one safely
and then we can just move the head
to point to what was the
second term and then now
is the first after that
node has been deleted.
>> So again, taking a look
at it as a diagram we
want to now pop an
element off of this stack.
So what do we do?
Well we're first going to create
a new pointer that's going
to point to the same spot as the head.
We're going to move it one position
forward by saying trav equals
trav next for example, which
would advance the trav pointer one
position forward.
Now that we've got a
hold on the first element
through the pointer called list, and the
second element through a pointer called
trav, we can safely delete that
first element from the stack
without losing the rest
of the chain because we
have a way to refer
to the second element
forward by way of the
pointer called trav.
>> So now we can free that node.
We can free list.
And then all we need to do now is
move list to point to the same place
that trav does, and we're sort of back
where we started before we pushed 12
on in the first place, right.
This is exactly where we were.
We had this four element stack.
We added a fifth.
We pushed a fifth
element on, and then we
popped that most recently
added element back off.
>> That's really pretty much
all there is to stacks.
You can implement them as arrays.
You can implement them as linked lists.
There are, of course, other
ways to implement them as well.
Basically the reason we would use
stacks is to maintain data in such a way
that the most recently added
element is the first thing we're
going to want to get back.
I'm Doug Lloyd, this is cs50.
