template typename class Node template typename friend class Queue temp

template <typename T> class Node
{
	template <typename>
	friend class Queue;

	template <typename>
	friend class Stack;

protected:
	Node<T>* next;
	Node<T>* back;
	T element;
public:
	Node(Node<T>* = 0, Node<T>* = 0, T = 0);
	Node(const Node<T>&);
};

template <typename T>
class Queue
{
protected:
	Node<T>* head;
	Node<T>* tale;
	int lenght;
public:
	Queue(unsigned int = 0);
	T pop();
	void put(T);
	int getLen();
	void add(unsigned int, T);
	void del(unsigned int);
	void swap(unsigned int, unsigned int);
	T& operator [](unsigned int);
	bool isEmpty();
	Node<T>* getElementByIndex(unsigned int);
	bool containsLastNode();
};

template <typename T>
class Stack : public Queue<T>
{
public:
	Stack(unsigned int = 0);
	T pop();
};

template <typename T>
Node<T>::Node(Node<T>* ptr_back, Node<T>* ptr_next, T value)
:next(ptr_next), back(ptr_back), element(value)
{}

template <typename T>
Node<T>::Node(const Node<T>& node) :
next(node.next), back(node.back), element(node.element)
{}

template <typename T>
Queue<T>::Queue(unsigned int size) : head(0), tale(0), lenght(0)
{
	for (unsigned int i = 0; i<size; i++)
	{
		this->put(T());
	}
}

template <typename T>
void Queue<T>::put(T value)
{
	if (isEmpty())
	{
		tale = new Node<T>(0, 0, value);
		head = tale;
	}
	else
	{
		tale->next = new Node<T>(tale, 0, value);
		tale = tale->next;
	}

	lenght++;
}

template <typename T>
T Queue<T>::pop()
{
	T temp;

	if (containsLastNode())
	{
		temp = head->element;
		delete head;
		tale = 0;
		head = 0;
	}
	else if (isEmpty())
	{
		throw "List is empty";
	}
	else
	{
		temp = head->element;
		(head->next)->back = 0;
		Node<T>* tmp = head->next;
		delete head;
		head = tmp;
	}

	lenght--;
	return temp;
}

template <typename T>
Node<T>* Queue<T>::getElementByIndex(unsigned int i)
{
	if (i <= lenght)
	{
		Node<T>* tmp = head;
		for (; i>0; i--)
		{
			tmp = tmp->next;
		}
		return tmp;
	}
	else
	{
		throw "Bad index!";
	}
}

template <typename T>
T& Queue<T>::operator [](unsigned int i)
{
	return getElementByIndex(i)->element;
}

template <typename T>
void Queue<T>::add(unsigned int index, T el)
{
	Node<T>* tmp = getElementByIndex(index);
	if (tmp == head)
	{
		Node<T>* new_node = new Node<T>(0, tmp, el);
		tmp->back = new_node;
		head = new_node;
	}
	else if (tmp == tale)
	{
		Node<T>* new_node = new Node<T>(tmp, 0, el);
		tmp->next = new_node;
		tale = new_node;
	}
	else
	{
		Node<T>* next_node = tmp->next;
		Node<T>* new_node = new Node<T>(tmp, next_node, el);
		next_node->back = new_node;
		tmp->next = new_node;
	}

	lenght++;
}

template <typename T>
void Queue<T>::del(unsigned int i)
{
	Node<T>* tmp = getElementByIndex(i);
	if (tmp == head)
	{
		tmp->next->back = 0;
		head = tmp->next;
	}
	else if (tmp == tale)
	{
		tmp->back->next = 0;
		tale = tmp->back;
	}
	else
	{
		Node<T>* back_node = tmp->back;
		Node<T>* next_node = tmp->next;
		back_node->next = next_node;
		next_node->back = back_node;
	}
	delete tmp;
	lenght--;
}

template <typename T>
void Queue<T>::swap(unsigned int i, unsigned int j)
{
	T tmp = (*this)[i];
	(*this)[i] = (*this)[j];
	(*this)[j] = tmp;
}

template <typename T>
int Queue<T>::getLen()
{
	return lenght;
}

template <typename T>
bool Queue<T>::containsLastNode()
{
	return tale == head && !isEmpty();
}

template <typename T>
bool Queue<T>::isEmpty()
{
	return head == 0 && tale == 0;
}

template <typename T>
Stack<T>::Stack(unsigned int size) : Queue<T>(size){}

template <typename T>
T Stack<T>::pop()
{
	T temp;

	if (this->containsLastNode())
	{
		temp = this->tale->element;
		delete this->tale;
		this->tale = 0;
		this->head = 0;
	}
	else if (this->isEmpty())
	{
		throw "List is empty";
	}
	else
	{
		temp = this->tale->element;
		(this->tale->back)->next = 0;
		Node<T>* tmp = this->tale->back;
		delete this->tale;
		this->tale = tmp;
	}

	this->lenght--;
	return temp;
}