A stack is data structure that deals with
data in a "Last In First Out" manner. This just means when you try to retrieve an
element from the stack, it will give you the element that was most recently given to it. But what is the stack used for, and why is
it so important? The most common real-world comparison of a
stack is just a stack of papers on a desk. When you add paper to the stack, it gets placed
on top of all the other papers, and if you want to pick up a piece of paper, you can
only grab the one that's on top. These are the two basic operations of a stack:
PUSH, adding to the stack, and POP or PULL, removing from the stack. And that's about it. The concept of a stack is very simple, but
just how much it helps with data and execution management far exceeds its simplicity. This is what makes the stack so great. If this was all you knew, you might be a little
confused. If the system you are using allows you to
store data anywhere in memory, where ever you'd like, why would you ever use the stack? The ability to access data in the stack seems
pretty limited, and it just seems like a nusance. Well, the stack wasn't meant to be used for
most data management, but what was built for, it does really well. Before we go into depth about what it was
used for, we should describe how it was implemented. First off, the stack is located somewhere
in main memory. It doesn't exist as its own special entity--all
of the data stored in the stack is in memory somewhere, so it can just be accessed just
like any other value in memory. So even though we said before that you can
only access the value on top of the stack, that just refers to the PUSH and POP operations. POP will remove the top-most element from
the stack, and PUSH places a new element above the current top-most element. All of the elements can be read or written
to at any time, but the size of the stack will not change unless a PUSH or POP occurs. The main register that dictates how large
the stack is at any one point is called the Stack Pointer. The stack pointer holds the memory address
that acts as the border between values that are part of the stack and those that are not. There are actually two ways the stack pointer
can be interpreted. It can hold the memory address of the current
top-most element on the stack. This is called the full stack convention. Likewise, it can hold the memory address of
the first byte not included in the stack. This is called the empty stack convention. These two different conventions work perfectly
fine, they just act slightly different when a PUSH and POP operation happens, and it is
important to know which is being used. In the full stack convention, the stack pointer
moves before PUSHing and after POPing, while in the empty stack convention it moves after
PUSHing and before POPing. Most systems use the empty stack convention,
so that is what will be used in this video. As far as how the bytes in the stack correspond
to bytes in main memory, there are again two different ways of doing it. In an ascending stack, the stack pointer is
increased when elements are PUSHed to it, and decreased when elements are POPed from
it. In a desending stack, the exact opposite is
the case. The stack pointer is decreased when elements
are PUSHed, and increased when elements are POPed. Again, most systems use a descending stack,
so that will be illustrated here. Now with all of this knowledge, let's revisit
the PUSH and POP operations. We'll suppose the stack pointer is already
at some address, let's say $01D0. This is a descending stack, so we know data
in memory locations higher than this are part of the stack, and memory locations lower than
this are considered empty. It also uses the empty stack convention, so
we know that the memory address $01D0 is empty, and that the data in $01D1 is the top-most
element. Let's PUSH the byte #$62 onto the stack. First the value #$62 will be placed in memory
referenced by the stack pointer, $01D0. Then, the stack pointer is decremented by
one. So it becomes $01CF. If we wanted to POP that byte back off of
the stack, we just do the same thing, but in reverse. First the stack pointer is incremented by
one, so it becomes $01D0. Then the value #$62 is read into a processor
register. Note that the value in memory doesn't actually
get erased or modified, only the stack pointer is modified during a POP operation. The memory address is still considered empty
however, since it will get overwritten by another byte that is PUSHed onto the stack. Now since this is all just memory, we can
read and modify anything we want if we choose. We don't have to use the PUSH and POP operations
to do everything. The stack pointer is just another processor
register, so we can use the memory address it references as an argument into another
instruction. So if we wanted to read the third-highest
element in the stack, we can just take the value of the stack pointer, add 3, and then
read the memory address referenced by this new value. This has its uses. In fact, let's look at all the uses for the
stack now. A very simple way of effectively using the
stack is to hold temporary values when you have a lot of data to work with. Many older systems only had a handful of registers
that you could actually perform math on, and if you needed more than that, you had to temporarily
store your intermediate values back in memory somewhere. With the stack you just have to PUSH values
you don't need yet, and POP them back later. No need to keep track of which memory addresses
hold which temporary values. In this example, we added #$10 to the value
in memory at $15DD, but preserved its original value. Of course, this only works if you are storing
relatively few elements, or you have to plan in advance what order to PUSH your values,
since you will only be able to retrieve them in reverse order. An extension of this idea is called register
preservation. Say you have a value in a register that you
need for later, but you need to make a subroutine call. If you want to be absolutely sure that you
still have this value after the routine call, you should PUSH the value before the call,
and POP it back afterwards. This way you still have the value you wanted
even if the code in the subroutine clobbers the register in question. This is called Caller Preservation, since
it's the caller of the subroutine that saves the registers. There is also the opposite case. If you are creating a subroutine and you want
to make sure that any registers that the caller may want saved are preserved, you can PUSH
them at the start of the routine and POP them back at the end. This is called Callee Preservation, since
it's the the creator of the subroutine that saves the registers. Usually certain registers are designated to
be caller preserved, and some callee preserved according to some convention. Now we move on to the biggest use of the stack--stack
frames. Most assembly instruction sets have some sort
of routine CALL and RETURN operations. This allows a chunk of code, a function, routine,
subroutine, to be run multiple times from multiple places. This way the code doesn't have to duplicated
over and over every time you need to use it. Now the CALL instruction encodes information
about where the subroutine is located in memory (in this example, $AC19), but how does the
RETURN instruction know where to return to? It can't encode this information itself, since
the subroutine can be called from multiple places in the code. The answer is that the CALL operation will
PUSH the location of the next instruction to the stack, so that the RETURN instruction
can then POP it back off and jump to that location. So in this example, the address $ADBA is PUSHed
to the stack, which is the location of the instruction directly after the CALL instruction. The bytes that hold the return addresses are
the backbones of the stack frames. Each stack frame will contain its return address
and other data elements that got PUSHed to the stack during that frame's execution. When a subroutine is called, the current frame
is suspended, and a new frame is created on top of it. Nesting many subroutines within one another
will result in more stack frames, and therefore a taller stack. One example where stack frames help structure
things better is parameter passing. A parameter or argument is just a value that
a subroutine needs in order to function properly. If the subroutine parameters are PUSHed to
the stack before the routine is called, it can then expect to find these parameters in
the frame directly underneath the current frame. In this example, the parameters #$31 and #$02
are in the stack underneath the routine's return address. Remember, the stack is all located in memory,
so any element can be accessed at any time. In order for the subroutine to access its
parameters properly during any point in execution, the memory should be accessed relative to
the stack pointer. This ensures that no matter what the size
of the stack is at the time of the function call, the parameters will still be located
correctly. These parameter values can also be modified
while they are in the stack, to create what are called out parameters. This is useful if the routine needs to output
a bunch of values at once, and can't store them all in registers at the same time. There is one final thing to mention about
stacks, and that is what happens when the value of the stack pointer goes outside its
intended range. Remember that the stack pointer just points
to somewhere in memory that marks the boundary between free memory and values in the stack. If it is known that the code being executed
isn't going to make the stack grow very high, only a small portion of memory may actually
be allocated to the stack. The stack pointer should never point anywhere
outside of this specified range; if it does, there are going to be problems. When the stack becomes larger than its maximum
intended size, that is, a value is PUSHed to the stack when it is completely full, this
is called a stack overflow. If there is anything stored in the memory
adjacent to the stack, it will be clobbered by the value that just got PUSHed. This can also occur by nesting too many subroutine
CALLs--the return addresses that get PUSHed to the stack will be the culprit this time. Similarly, if the stack size becomes negative,
that is, a value is POPed from the stack when it is completely empty, this is called a stack
underflow. This is just as problematic, as the memory
adjacent to the stack will be clobbered upon the next PUSH operation. This can also occur when the RETURN operation
is executed, since it expects a return address to be POPed off of the stack. If you would like to support the channel,
RGME is on Patreon at patreon.com/rgmechex. If you can't support, don't worry! Just subscribing on YouTube or even sharing
the channel with others is more than enough. Actually, watching until the very end is even
better yet! Thank you for watching.
