C++ Templates and Stack

C++ Templates

A template can be understood with the example of a factory that bakes biscuits. The factory may use flour, corn or starch as ingredients of the product. But the process of baking biscuits is the same whatever ingredients it uses.

Same is the case for template in C++, instead we make two classes FloatStack() and CharStack() for operands and operators respectively (consult Stack Using Linked List blog to understand the situation) that have same implementation, and write the code twice. We’ll make the template to avoid duplication of code.

template <class T>
class Stack { 
    public:
    Stack(); 
    int empty(void); // 1=true, 0=false
    int push(T &); // 1=successful,0=stack overflow
    T pop(void);
    T peek(void);
    ~Stack();
    
    private:
    int top;
    T* nodes;
};

Function Call Stack

This is another example of stack (we’ve discuss the first use of stack in Evaluating Postfix Expression). We know how functions work. We pass arguments to the function, function works on those values, and returns a value to the calling function.

We declare some variables inside the function. These variables get destroy when the function ends.

The compiler puts the entries on the stack in the way that first of all i.e. on the top (i.e. first entry in the stack) is the return address of the function where the control will go back after executing the function.

After it, the next entries on the stack are the arguments of the function. The compiler pushes the last argument of the call list on the stack. Thus the last argument of the call list goes to the bottom of the stack after the return address.

This is followed by the second last argument of the call list to be pushed on the stack. In this way, the first argument of the call list becomes the first element on the stack. See the following image:

Internal Memory Organization of a Process

You’ve opened lot of programs on your computer. Let’s assume, one of them is Excel. Excel’s software operation organizes the processes into memory as shown in the image.

Stack Layout during a Function Call

Here “sp” stands for “stack pointer”.

So, when function “F” calls the function “G”:

• At most left, first, we insert the parameters passed to function “F” inside the stack. Next, we follow these with the function “F”’s local variables and finally insert the memory address to return back after the function “F” finishes. Just before making the call to function “G”, we insert the parameters being passed to function “G” into the stack.
• In the middle, there is layout of the stack on the right side after the call to the function G. Clearly, the function G inserts its local variables into the stack after its parameters and the return address. If a function has no local variables, it inserts (pushes) the return address onto the stack.
• At most right, when function “G” finishes its execution, local variables of function “G” are no more in the stack.

When making a function call, the called function pushes all its local variables and parameters onto the stack and destroys them after the completion of its execution.

Reference: CS301 Handouts (page 72 to 83)