#include <stdio.h>
#include <conio.h>

struct Node
{
	int data;
	Node* next;
	Node( int d )
	{
		data = d;
		next = NULL;
	}
};

class LinkedList
{
public:

	Node* h;
	LinkedList()
	{
		h = new Node( 0 );
	}

	void insertLast( int data )
	{
		Node* it = h;
		while( it->next != NULL )
			it = it->next;
		it->next = new Node( data );
		h->data++;
	}

	void printAll()
	{
		if(h->data == 0 )
		{
			printf("**EMPTY**");
			return;
		}
		Node* it = h;
		while( it->next != NULL )
		{
			printf(" %d ", it->next->data);
			it = it->next;
		}
		printf("\n");
	}

	Node* removeLast()
	{
		if(h->data == 0 )
		{
			//printf("\nerror: empty list\n");
			return NULL;
		}
		Node* it = h;
		while( it->next->next != NULL)
			it = it->next;
		int tmp = it->next->data;
		delete it->next;
		it->next = NULL;
		h->data--;
		return new Node(tmp);
	}

	Node* remove( int data )
	{
		if(h->data == 0 )
		{
			//printf("\nerror: empty list");
			return NULL;
		}
		Node* it = h;
		while( it->next != NULL )
		{
			if(it->next->data == data )
				break;
			it = it->next;
		}
		if(it->next == NULL )	//means that the it reached the end of the list without finding the data
		{
			//printf("\nerror: item not found !\n");
			return NULL;
		}

		Node* t = it->next->next;
		int tmp = it->next->data;
		delete it->next;
		it->next = t;
		h->data--;
		return new Node( tmp );
	}
};

class Stack
{
public:
	LinkedList b;

	void push( int data )
	{
		b.insertLast( data );
	}

	Node* pop()
	{
		if( b.removeLast() == NULL)
		{
			printf("\nStack underflow !\n");
			return NULL;
		}
	}

	void displayStack()
	{
		b.printAll();
	}
};

void main()
{
	Stack s;
	s.push( 5 );
	s.push( 6 );
	s.push( 7 );
	s.displayStack();
	s.pop();
	s.displayStack();
	s.pop();
	s.displayStack();
    s.pop();
	s.displayStack();
	s.pop();	//will cause stack underflow
	s.push(10);
	s.displayStack();
	getch();
}