We have already discussed the call stack and how it is used to organize the memory used by function calls in a program. When a function is called, a new frame is created on the call stack to hold its local variables and parameters. This frame is removed when the function returns, freeing up the memory it used.
In computer science, the stack is a data structure that stores a collection of elements, with two main operations: “push”, which adds an element to the top of the stack, and “pop”, which removes the top element (the most recently added). A stack works like a stack of plates: when you need a plate, you likely just grab the top plate in a stack in your cupboard. After washing a plate, you put it back at the top of the stack.
This behavior is sometimes called LIFO (last-in, first-out), and it describes how the call stack operates. As each function is called its stack frame is placed on the top of the stack. When the function returns, the top stack frame is removed.
The call stack is often organized so that the “bottom” of the stack is the highest memory address and the “top” of the stack is the lowest memory address. This means that as new frames are added to the stack, they are placed at lower memory addresses. You can see this in codelens simulations—it shows the most recently added stack frames at the bottom of the display:
Each time main called bar, a stack frame is added below main. Despite where it is visually, we would say that “bar is on the top of the stack”. When bar in turn calls foo, a new stack frame is added below bar. Again, we would say that “foo is on the top of the stack”. When foo returns, its stack frame is removed, and we would say that “bar is on the top of the stack” again. main is on the bottom of the stack throughout the run of the program because it was the first function.
Even when a stack starts at the highest point and builds down, we still refer to the most recently added item as the “top” of the stack and the oldest item as the “bottom” of the stack.
Another way to think about it: main is always the “bottom” of the stack. Items are stacked so they build in one direction and that is the “top” of the stack.
In C++ the call stack is managed automatically by the compiler and runtime system. When a function is compiled, in addition to compiling the function’s code, the compiler generates code to create a new stack frame with space for its local variables and parameters. It also generates code at the end of the function to clean up the stack frame.
Assume that, like Codelens illustrations, the “bottom” of the stack is the highest memory address and the “top” of the stack is the lowest memory address.
