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

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

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

The stack frames have another important responsibility. Most functions have local variables—parameters and any local variables the function declares. Non-static local variables need to exist while a function is executing. They need to remain active if the function makes calls to other functions. But when a called function returns to its caller, the called function’s non-static local variables need to “go away.” The called function’s stack frame is a perfect place to reserve the memory for the called function’s non-static local variables. That stack frame exists as long as the called function is active. When that function returns—and no longer needs its non-static local variables—its stack frame is popped from the stack, and those non-static 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 function-call stack. If more function calls occur than can have their activation records stored on the function-call stack, a fatal error known as stack overflow occurs.3

Now let’s consider how the call stack supports the operation of a square function called by main (lines 9–13 of Fig. 6.12).

First, the operating system calls main—this pushes an activation record onto the stack (shown in Fig. 6.13). The activation record 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 (i.e., a, which is initialized to 10).

Function main—before returning to the operating system—now calls function square in line 12 of Fig. 6.12. This causes a stack frame for square (lines 16–18) to be pushed onto the function-call stack (Fig. 6.14). 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 (i.e., x).

After square calculates the square of its argument, it needs to return to main—and no longer needs the memory for its variable x. 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 6.15 shows the function-call stack after square’s activation record has been popped.

Function main now displays the result of calling square (Fig. 6.12, line 12). 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. 6.13)—at this point, main’s local variable (i.e., a) 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 15, Standard Library Containers and Iterators, and Chapter 19, Custom Templatized Data Structures.