Program for Stack using Linkedlist in C++ and Implementation

Stack is an abstract data type and a data structure which follows "Last In First Out" Principle . In my previous tutorials I discussed about stack and implementation of the stack using arrays . We have also seen the advantages of stack Data Structure . In this post I will be discussing about Implementation of Stack using Linked List and program for it . Linked list is also a data structure which is has more advantages over stacks and queues when it comes to memory . If you don't have any idea about linkedlist I would suggest to read the tutorial for Linkedlist .

Why to Implement stack using Linkedlist rather than arrays  ?

In my previous post about stack implementation using array , the size of the array need to be fixed to store the values in the stack . If the stack is full we cannot insert an additional element into the array . It gives an overflow exception. But in linkedlist we can increases size at runtime by creating a new node . So it is better to implement stack data structure using Linkedlist data structure . 
The following are the operations to implement stack :
1. Insertion
2. Deletion 
3. Display elements .

1. Insertion : 

Insertion operation refers to Inserting an element into stack . We create a new node  and insert an element into the stack . To follow the stack principle " Last in first  out " . A node need to be created from the end of the Linkedlist and element need to be inserted into the node from the end of the linkedlist . 

2. Deletion :

Deletion operation is to delete an element or node from the Linkedlist . Deletion can be done by deleting the top most element from the stack as the Last element inserted is the first element that needs to be deleted as per stack principle . So the recently inserted element i.e top element must be deleted from the Linked list to perform as Stack deletion . 

3. Display :

Display helps in displaying the elements of the Stack . Display function is similar to displaying elements in Linkedlist . 

Program for Stack using Linkedlist :

Linked stack class :

template <class T>
class linkedstack : private chain<T>
{
public :
    bool isempty() const
    {
        return chain<T>::isempty();
    }
    bool isfull() const;
    T top() const
    {
        if(isempty()) throw OutOfBounds();
        T x;
        Find(1,x);
        return x;
    }
    linkedstack<T>& add(const T &x)
    {
        insert(0,x);
        return *this;
    }
    linkedlist<T>& Delete(T &x)
    {
        chain<T>::Delete(1,x);
        return *this;
    }
};
template<class T>
bool linkedstack<T>::isfull() const
{
    try
    {
        chainnode<T> *p=new chainnode<T>;
        delete p;
        return false;
    }
    catch(NoMem)
    {
        return true;
    }
}

Implementing Stack as Base class :

template<class T>
class node
{
    friend linkedstack<T>;
private :
    T data;
    node<T> *link;
};
template<class T>
class linkedstack
{
public :
    linkedstack()
    {
        top=0;
    }
    ~linkedstack();
    bool isempty() const
    {
        return top==0;
    }
    bool isfull() const;
    T top() const;
    linkedstack<T>& add(const T &x);
    linkedstack<T>& Delete(T &x);
private :
    node<T> *top;
};

Destructor ,Isfull ,Top Functions :

template<class T>
linkedstack<T>::linkedstack()
{
    node<T> *next;
    while(top)
    {
        next=top->link;
        delete top;
        top=next;
    }
}
template<class T>
bool linkedstack<T>::isfull() const
{
    try
    {
        node<T> *p=new node<T>;
        delete p;
        return false;
    }
    catch(NoMem)
    {
        return true;
    }
}
template<class T>
T linkedstack<T>::top() const
{
    if(isempty()) throw OutOfBounds();
    return top->data;
}

Adding To a Linkedstack - Insertion :

template<class T>
linkedstack<T>& linkedstack<T>::add(const T &x)
{
    node<T> *p=new node<T>;
    p->data=x;
    top=p;
    return *this;
}

Deleting From a Linkedstack - Deletion :

template<class T>
linkedstack<T>& linkedstack<T>::Delete(T &x)
{
    if(isempty()) throw OutOfBounds();
    x=top->data;
    node<T> *p=top;
    top=top->link;
    delete p;
    return *this;
}

Time complexity of Implementing Stack using linkedlist is :
Constructor : O(1)
Destructor  :O(1)
Insertion , Deletion , Top operations : O(1)
Download Program for stack using linkedlist in c 
Download Program for stack using linkedlist in c++ 

Final Words :

Stack using linkedlist code is implemented in c++ with object oriented programming .
If you find anything difficult please comment below . Also share your ideas , logics through comments .