One of the most important mechanisms for computer science students to understand is the method-call stack (sometimes referred to as the program-execution stack). This data structure—working “behind the scenes”—supports the method call/return mechanism. It also supports the creation, maintenance and destruction of each called method’s local variables. As we’ll see in Figs. 7.11–7.13, last-in, first-out (LIFO) behavior is exactly what a method needs in order to return to the method that called it.

As each method is called, it may, in turn, call other methods, which may, in turn, call other methods—all before any of the methods return. Each method eventually must return control to the method that called it. So, somehow, the system must keep track of the return addresses that each method needs in order to return control to the method that called it. The method-call stack is the perfect data structure for handling this information. Each time a method calls another method, an entry is pushed onto the stack. This entry, called a stack frame or an activation record, contains the return address that the called method needs in order to return to the calling method. It also contains some additional information we’ll soon discuss. If the called method returns instead of calling another method before returning, the stack frame for the method call is popped, and control transfers to the return address in the popped stack frame. The same techniques apply when a method accesses a property or when a property calls a method.

The beauty of the call stack is that each called method always finds the information it needs to return to its caller at the top of the call stack. And, if a method makes a call to another method, a stack frame for the new method call is simply pushed onto the call stack. Thus, the return address required by the newly called method to return to its caller is now located at the top of the stack.

The stack frames have another important responsibility. Most methods have local variables—parameters and any local variables the method declares. Local variables need to exist while a method is executing. They need to remain active if the method makes calls to other methods. But when a called method returns to its caller, the called method’s local variables need to “go away.” The called method’s stack frame is a perfect place to reserve the memory for the called method’s local variables. That stack frame exists as long as the called method is active. When that method returns—and no longer needs its local variables—its stack frame is popped from the stack, and those local variables no longer exist.

Of course, the amount of memory in a computer is finite, so only a certain amount of memory can be used to store activation records on the method-call stack. If more method calls occur than can have their activation records stored on the method-call stack, a fatal error known as stack overflow occurs2—typically caused by infinite recursion (Section 7.16).

Now let’s consider how the call stack supports the operation of a Square method (lines 15–18 of Fig. 7.10) called by Main (lines 8–12).

First, the operating system calls Main—this pushes an activation record onto the stack (Fig. 7.11). This tells Main how to return to the operating system (i.e., transfer to return address R1) and contains the space for Main’s local variable x, which is initialized to 10.

Method Main—before returning to the operating system—calls method Square in line 11 of Fig. 7.10. This causes a stack frame for Square (lines 15–18) to be pushed onto the method-call stack (Fig. 7.12). This stack frame contains the return address that Square needs to return to Main (i.e., R2) and the memory for Square’s local variable y.

After Square performs its calculation, it needs to return to Main—and no longer needs the memory for y. So Square’s stack frame is popped from the stack—giving Square the return location in Main (i.e., R2) and losing Square’s local variable (Step 3). Figure 7.13 shows the method-call stack after Square’s activation record has been popped.

Method Main now displays the result of calling Square (Fig. 7.10, line 11). Reaching the closing right brace of Main causes its stack frame to be popped from the stack, giving Main the address it needs to return to the operating system (i.e., R1 in Fig. 7.11)—at this point, Main’s local variable x no longer exists.

You’ve now seen how valuable the stack data structure is in implementing a key mechanism that supports program execution. Data structures have many important applications in computer science. We discuss stacks, queues, lists, trees and other data structures in Chapter 19, Custom Linked Data Structures, and Chapter 21, Generic Collections; Functional Programming with LINQ/PLINQ.