How To Draw A Stack Diagram

A stack diagram is a way of visually representing the contents of memory at a moment in fourth dimension during the execution of a program. We draw stack diagrams in a consistent mode for the same reason that spoken languages accept rules of syntax and grammar: to ensure that others can read what nosotros have written. This page gives a clarification of how we draw stack diagrams in CS35.

Stack Frames

We begin our word with a simple case of a stack diagram. Below, we have a unproblematic C++ program which statically allocates three variables (ii intsouthward and an int array) and then returns. To the right of that code, we have a corresponding stack diagram. Annotation that, because a stack diagram represents a moment in time, we must determine what moment our diagram is intended to represent. In this tutorial, nosotros will practise so using comments such as // DIAGRAM HERE in this example code.

                              int main() {     int x = 5;     int y;     int a[4];     // DIAGRAM Here     render 0;   }

At the time we accomplish the comment, the main part is running; we therefore have a stack frame (the rectangle) labeled primary. Three variables take been statically allocated in chief, which we represent by drawing the variables and their corresponding spaces in the primary stack frame.

The first variable in the stack frame, x, has been initialized to v in the lawmaking. For this reason, we write a 5 in the box respective to it. The y variable has non been initialized; we represent this by leaving its space blank. Likewise, while nosotros have statically allocated four ints by declaring the array a, we take not however put anything into the array so all of its positions are uninitialized.

Function Calls

When we call a function, that part executes completely and then our programme resumes from where we made the telephone call. Any stack variables that the caller had at the time of the call are preserved; they still accept their onetime values when the phone call is finished. Thus, if our stack diagram represents a moment in time during a call, it must evidence that other functions are waiting for us to return to them (and testify their variables' values). We represent this by creating a stack of frames (rectangles), each containing the variables for that item telephone call.

                              int pow(int base, int exp) {     int acc = i;     for (int i=0;i<exp;i++) {       acc = acc * base;     }     // DIAGRAM Here     return acc;   }    int primary() {     int b = ii;     int eastward = 5;     int answer = pw(b, e);     return 0;   }

In the to a higher place example, the pw part calculates a number raised to a positive integer power. The moment in time we are capturing is within the pow function, so we draw a diagram in which the pow stack frame appears to a higher place the main stack frame: when pow finishes, main will resume running. The parameters and local variables for pow appear inside its frame, separated from the local variables of main.

Of note is the fact that the answer variable in master has not yet been initialized! A variable assignment like int answer = pow(b,due east); must first compute the result of pw(b,e) then assign that result to answer. Since nosotros're still in the center of calling prisoner of war, the value of answer has not yet been decided.

Recursion

When calling a recursive function, each recursive call has its ain variables with their ain values. Nosotros correspond this past showing a unlike stack frame for each recursive phone call. In other words, recursive calls are not special in stack diagrams; nosotros depict them just as we would any other call.

                              #include <iostream>   using namespace std;    int summation(int n) {     if (n<ii) {       // DIAGRAM Here       return n;     } else {       return summation(n-ane) + n;     }   }    int main() {     cout << summation(three) << endl;     return 0;   }

In the above case, the summation routine adds all of the numbers between i and due north and returns the upshot. Information technology does this recursively: summation(three) calls summation(2), for instance. Note how each recursive call has a singled-out stack frame.

Of some interest in this diagram is that the main role has no variables of its ain. Even though the frame is empty, we yet draw it.

Dynamic Allotment

We use the term stack diagram considering the diagram is focused on showing memory from the point of view of the stack. A more accurate term might be memory diagram, however, as nosotros use stack diagrams to show dynamically allocated memory too. In C++, dynamic allocation is accomplished using new (while deallocation occurs with delete and delete[]). We describe dynamically allocated retentivity to the correct of the stack diagram and prove pointers to that retentivity using arrows.

                              #include <iostream>   using namespace std;    int main() {     int* array1 = new int[v];     int* array2 = new int[3];     int* array3 = array1;     array1[0] = 2;     // DIAGRAM Hither     delete[] array1;     delete[] array2;     return 0;   }

Objects

In object-oriented programs, objects are combinations of data and routines which deed on that information. In a stack diagram, we are just concerned with the data contained in the object. We stand for an object in a fashion similar to a stack diagram: a series of variables (the object's fields) in a container. We put the proper name of the object'southward grade on the correct of its box to differentiate between objects and stack frames.

                              #include <iostream>   using namespace std;    grade Point {   public:     int 10;     int y;   };    int master() {     Point* p = new Point();     p->10 = iv;     // DIAGRAM HERE     delete p;     return 0;   }

Dynamically allocated objects (such every bit the Bespeak object above) are drawn in the heap memory to the correct of the stack frames. Pointers to those objects are represented the same as for arrays: using an arrow. Hither, the Point object's 10 field has been initialized but its y field has non.