/* Ylopoihsh stoibas me apla syndedemenh lista */

#include <iostream>
#include <new>
#include <exception>

using namespace std;

class stackEmptyException: public exception
{
  	virtual const char* what() const throw(){
		return "Stack is empty";
	}

};

template <class T>
struct listNode{
	T data;
	struct listNode * next;
};

template <class T>
class ListStack{
  private:
	int length; /* To plh8os twn stoixeion pou periexei h stoiba */
	listNode<T> * topNode; /* Deikths sto koryfaio stoixeio ths stoibas */
	

  public:
	ListStack(){
		length = 0;
		topNode = NULL;
	}

	~ListStack(){
		while(length > 0){
			pop();
		}
	}

	int getLength(){
		return length;
	}

	bool isEmpty (){
		return (topNode == NULL);
	}

	T top(){
		if(topNode == NULL){
			throw new stackEmptyException();
		}

		return topNode->data;
	}

	T pop(){
		if(topNode == NULL){
			throw new stackEmptyException();
		}

		T ret = topNode->data;

		length--;
		if(length == 0){
			delete topNode;
			topNode = NULL;
		}
		else{
			listNode<T> * del = topNode;
			topNode = topNode->next;
			delete del;
		}

		return ret;				
	}

	void push (T data){
		listNode<T> * newNode = new listNode<T>;
		newNode->data = data;

		newNode->next = topNode;
		topNode = newNode;

		length++;
		return;
	}
};