class Stack
{
	struct Element
	{
		int inf;
		Element *next;
		Element(int x, Element *p) :inf(x), next(p)
		{

		}
	};
	Element *head; //указатель на вершину стека
public:
	Stack() :head(0) //конструктор стека
	{}
	bool Empty()
	{
		return head == 0;

	}
	int Pop()
	{
		if (Empty())
		{
			return 0;

		}
		Element *r = head;
		int i = r->inf;
		head = r->next;
		delete r;
		return i;
	}
	void Push(int data) {
		head = new Element(data, head);
	}
};
class QueueException : public exception
{
public:
	QueueException(const string & message = "") :exception(message.c_str())
	{}
};

template <class Item>
class Queue
{
	struct Melement
	{
		Item inf;
		Melement *next;
		Melement(Item x) :inf(x), next(0)
		{}

	};
	Melement *head, *tail; //указатели на начало и конец очереди
public:
	Queue() :head(0), tail(0)
	{}
	bool Empty()
	{
		return head == 0;
	}
	Item Get()
	{
		if (Empty())
		{
			throw QueueException("QueueExceprion: get - queue empty");
		}
		else //иначе извлекаем элемент из головы очереди
		{
			Melement *t = head;
			Item i = t->inf;
			head = t->next;
			if (head == NULL)
			{
				tail = NULL;
			}
			delete t;
			return i;
		}

	}
	void Put(Item data)
	{
		Melement *t = tail; //устанавливаем вспомогательный указатель
						   // на последний элемент очереди
		tail = new Melement(data); //формируется новый элемень, на
								  //который будет указывать tail
		if (!head)               //если до этого очередь была пуста, то новый
		{
			head = tail;
		}
		else
		{
			t->next = tail;
		}
	}

};