//Stack class implemented as a linked list

//Stack class implemented as a linked list. Each element
// in the list is a struct consisting of an element el, and a
// pointer to the next struct (node) in the list.
//The constructor stack() initialises top of the stack to point to NULL.
//The operations on the stack include:
// Push(int X) which adds a new element to the top of the stack
// Pop() which removes the top element
// Top() which returns the top element
// IsEmpty() tests to see if the list is empty
// MakeEmpty() deletes (pops) all elements from the stack
// The destructor calls MakeEmpty() to empty the stack and free up memory.

class stack{

    public:
            stack( ) {TopOfStack = NULL;} //constructor
            ~stack( ) {MakeEmpty();} // destructor

            void Push(int X); // push element X onto the stack
            void Pop( ); // remove the top element
            int Top( ); // return the top element
            int IsEmpty( ) { return TopOfStack == NULL;}
            void MakeEmpty( );

private:

            struct SNode
            {
                int el;
                SNode* next;
            };

SNode *TopOfStack; // TopOfStack is a pointer to a node (struct)

};

// method Push()
// To implement a Push, create a new node and
// attach it at the top of the stack (a new first element in the list)

void stack :: Push(int X)
{
SNode *tmp = new SNode; // pointer tmp points to the new SNode

    tmp->el = X; // place element X in the el field of SNode
    tmp->next = TopOfStack; // make the next pointer of the new SNode
                                                                      // point to where the TopOfStack points i.e.,
                                                                      // it points to the old first element (old top of stack)
    TopOfStack = tmp; // Point TopOfStack to the new SNode added
}

// method Pop()
// To implement a Pop, advance top of stack to the second item (if there is one).
// Call delete on the old first node to avoid a memory leak

void stack :: Pop( )
{
SNode *tmp = TopOfStack; // pointer tmp points to the Top of the stack

TopOfStack = TopOfStack->next; // point TopOfStack to the second element in the stack
delete tmp; // delete the node pointed to by tmp i.e., the old top of stack.
}

// method Top()
// This method returns the top element on the stack
// It first checks to see if the stack is empty

int stack :: Top( )
{
    if(IsEmpty())
            cout<<"Empty stack\n";
    else
            return TopOfStack->el;
}

// method MakeEmpty()
// This method removes each element (SNode) from the stack
// by calling Pop() within a loop until all elements have been
// popped from the stack.

void stack :: MakeEmpty( )
{
while( !IsEmpty( ) )
Pop();
}