#include <cstdlib>
#include <iostream>
template <class TData> class cLL
{
protected:
	struct sNode
	{
		sNode *Prev;
		TData Data;
		sNode *Next;
		sNode(sNode *inPrev,TData inData,sNode *inNext)
		{
			Prev = inPrev;
			Data = inData;
			Next = inNext;
		}
		sNode()
		{
			Prev = NULL;
			Next = NULL;
		};
		~sNode(){}
	};
	sNode *Head;
	sNode *Tail;
public:
	cLL <TData>()
	{
		Head = Tail = NULL;
	};
	virtual ~cLL <TData>(){};
	//void virtual Push(const TData Data);
	TData Pop()
	{
		TData result;
		sNode *tmpOldHead;
		try
		{
			if(Head != NULL)
			{
				result = Head->Data;
				tmpOldHead = Head;
				Head = Head->Next;
				delete tmpOldHead;
				return result;
			}
			throw "Tried to pop an empty linked list!";
		}
		catch (char *errmsg)
			cout << "Exception Raised: " << errmsg << '\n';
	};
	TData Poke()
	{
		try
		{
			if(Head != NULL)
			{
				return Head->Data;
			}
			throw "Tried to poke an empty linked list!";
		}
		catch(char *errmsg)
			cout << "Exception Raised: " << errmsg << '\n';
	};
	void PrintList()
	{
		sNode *CurrentNode = Head;
		while(CurrentNode != NULL)
		{
			std::cout << CurrentNode->Data << "\n";
			CurrentNode = CurrentNode->Next;
		}
	};
};

template <class TData> class cStack : public cLL
{
public:
	cStack <TData>(){};
	~cStack <TData>(){};
	void Push(const TData Data)
	{
		sNode *tmpOldHead;
		if(Head == NULL)
		{
			Head = new sNode(NULL,Data,NULL);
			Tail = Head;
		}
		else
		{
			tmpOldHead = Head;
			Head = new sNode(NULL,Data,tmpOldHead);
			tmpOldHead->Prev = Head;
		}
	};
};
template <class TData> class cQueue : public cLL
{
public:
	cQueue <TData>(){};
	~cQueue <TData>(){};
	TData Pop();
	TData Poke();
	void PrintList();
	void Push(const TData Data)
	{
		sNode *tmpOldHead;
		if(Tail == NULL)
		{
			Tail = new sNode(NULL,Data,NULL);
			Head = Tail;
		}
		else
		{
			tmpOldHead = Tail;
			Tail = new sNode(tmpOldHead,Data,NULL);
			tmpOldHead->Prev = Tail;
		}
	};
};