Stack implementation using linked list representation in C++

Stack is an important data structure, which works on the principle of Last-In-First-Out(LIFO). It is used in memory modules for storing local variables and implementing recursive calls. It is also used in implementing Lexical analyzers(compilers) to check for syntactical errors. Besides this it can be used for inter-conversion of mathematical expressions(in-fix, post-fix and pre-fix notations).

The image shown here represents a Stack of books.[courtesy internet]

 

Stack uses a pointer called Stack pointer, which always points to the top-most item. It uses operations like PUSH and POP, Push stores an item on top of the stack using stack pointer where as Pop removes a top item. When the stack is Empty, It is called stack under flow condition and If the stack is full it is called stack overflow condition.

Here a Linked List is been used to create stack. The start address of the List(head) represents stack pointer. If the head value is NULL, Stack is Empty, and if the dynamically memory-allocating function(here new operator) return NULL, let's consider it as stack overflow condition.

By implementing algorithms for adding a node at front of the list and deleting a front node, push and pop operations are defined, respectively.  The following code snippet illustrates a generic stack implemented using Linked List

template<class T>
class Stack
{
    struct node
    {
        T data;
        node *link;
    };

    node *head;
    public :
    Stack()             // Constructor
    {
        head=NULL;      // Initializing head to NULL Empty Stack
    }

    void push(T x);
    T  pop();
    int isEmpty();
};

template<class T>
void Stack<T> :: push(T x) // Adding a node at front
{
    node *nn;
    nn = new node;
    nn->data = x;
    nn->link = head;
    head = nn;

}
template<class T>
T Stack<T> :: pop()      // Deleting a front node
{
    T x;
    node *temp = head;
    head = head->link;
    x = temp->data;
    delete temp;
    return x;
}
template<class T>
int Stack<T> :: isEmpty()
{
    if(head == NULL)
        return 1;
    else
        return 0;

}

Stay connected ,In the next post , the application of this Stack will be demonstrated for Evaluation of post-fix expression and conversion of infix expression to post-fix expression.
Your inputs are welcome.