Stack template class in C++

Today let us write a template class Stack. Stack is a data structure of LIFO - last in first out. But of course, STL (standard template library) has a stack class in it and you can use it.

But still let us write our own Stack.

Stack needs the following methods - push, pop, empty and peek or top. push method add a value to the top of the stack. Pop removes a value from the top of the stack. empty finds out whether the stack is empty. peek returns the value from top of the stack without actually removing it.

Did you know that function call in most of these languages make use of Stack data structure for managing call frames. That is the reason, a return will return from the most recently called function.

Anyways. How do we implement the stack. We can use a vector or a deque from STL. If we want to use basic data types, we can use an array or our own linked list. Array will be limited by size of the array. So linked list?

template <class T>
struct node
{
    T num;
    struct node *next;
};

template <class T>
class Stack
{
       node <T>*topnode;
public:
      Stack();
      bool empty();
      void push(T data);
      T pop();
      T & top();
};

Why templates? Because our class becomes flexible and can be used for most data types.

We have self referential structure node with data and link to the next node. Data is a template variable. So it can be int, float, string etc.

Next we have class Stack which has one data parameter topnode or top of the stack. And we must have constructor and the four methods.

Constructor should initialize topofstack or topnode to 0. If you have written a similar program in C, you would have set it to NULL pointer. C++ prefers plain 0 for pointer rather than predefined constant 0. You know that NULL is nothing but a pointer with 0 value.

template <class T>
Stack<T>::Stack()
{
    topnode = 0;/*initialize*/
}

For push function, we have to create a new node using dynamic memory allocation. and place this node on top of stack. You should perform these operation in push operation.

• create a new node 
• newnode->next = topnode
• topnode = newnode

template<class T>
void Stack<T>::push(T data)
{
     node <T>*newnode = new node<T>;
     newnode->num = data;
     if(topnode){
         newnode->next = topnode;
     }else{
         newnode->next = 0;
     }
     topnode = newnode;
}

Similarly in pop operation, we have to perform

• copy topnode to temp
• topnode = topnode->next 
• copy value in temp to num
• delete temp
• return num

template<class T>
T Stack<T>::pop( )
{
    if(!empty())
        {
            node<T> * temp = topnode;
            topnode = topnode->next;
            T num = temp->num;
            delete temp;
            return num;
    }
    else
        {
             return (T)0;
        }
}

Empty is a simple function, you will just check if topnode is 0. If it is zero Stack is empty

template <class T>
bool Stack<T>::empty()
{
    return topnode==0;
}

But since all these functions are part of template class, they all must have template header before them.

Remember: For a template class, the class definition and also function definitions must be in header file.

Complete Program

Stack.h

template <class T>
struct node
{
    T num;
    struct node *next;
};

template <class T>
class Stack
{
       node <T>*topnode;
public:
      Stack();
      bool empty();
      void push(T data);
      T pop();
      T & top();
};


template <class T>
Stack<T>::Stack()
{
    topnode = 0;/*initialize*/
}
template <class T>
bool Stack<T>::empty()
{
    return topnode==0;
}

template<class T>
void Stack<T>::push(T data)
{
     node <T>*newnode = new node<T>;
     newnode->num = data;
     if(topnode){
         newnode->next = topnode;
     }else{
         newnode->next = 0;
     }
     topnode = newnode;
}

template<class T>
T Stack<T>::pop( )
{
    if(!empty())
        {
            node<T> * temp = topnode;
            topnode = topnode->next;
            T num = temp->num;
            delete temp;
            return num;
    }
    else
        {
             return (T)0;
        }
}

template<class T>
T& Stack<T>::top( )
{
    if(!empty())
        {                        
            T num = topnode->num;             
            return num;
        }
    else
        {
             return (T)0;
        }
}

main.cpp
#include <iostream>
#include"Stack.h"
using namespace std;
int main(int argc, char **argv)
{
 Stack<int> s1;
    for(int i=0;i<10;i++)
    {
        int m;
        cin>>m;
        s1.push(m);
    }
    while(!s1.empty())
    {
        int a;
        a = s1.pop();
        cout<<"Popped value is "<<a<<"\n";
    }
    Stack<char> s2;
    s2.push('c');
    s2.push('+');
    s2.push('+');
    
     while(!s2.empty())
    {
        char a;
        a = s2.pop();
        cout<< a<<"\n";
    }
}