#include <iostream>

using namespace std;

template <class sClass>
class Element
{
public:
	sClass obj;
	int priority;
	Element<sClass> *next;
public:
	Element()
	{
		next = NULL;
	}
	Element(sClass o, int k)
	{
		obj = o;
		priority = k;
	}
	sClass GetObj()
	{
		return obj;
	}
	int GetPriority()
	{
		return priority;
	}
};

template<class someClass>
class Queue
{
private:
	int size;
	Element<someClass> *elem;
	Element<someClass> *here, *prev;
public:
	Queue()
	{
		size = 0;
		here = NULL;
		elem = NULL;
	}
	int Size()
	{
		return size;
	}
	void push_back(someClass obj, int k)
	{
		Element<someClass> *newObj = new Element<someClass>(obj, k);
		if (size != 0)
		{
			elem = here;
			prev = here;
			for (int i = 0; i < size; i++)
			{
				if (i == 2)
					elem = here->next;
				else if (i > 2)
					elem = elem->next;
				if (prev->GetPriority() < k)
				{
					if (i == 0)
					{
						newObj->next = here;
						here = newObj;
						break;
					}
					newObj->next = elem->next;
					elem->next = newObj;
					break;
				}
				if (i + 1 == size && size != 0)
				{
					prev->next = newObj;
					break;
				}
				if (i + 1 != size)
					prev = prev->next;
			}
		}
		else
		{
			here = newObj;
		}
		size++;
		elem = NULL;
		prev = NULL;
		cout << obj << " pushed" << endl;
	}
	void pop()
	{
		if (size != 0)
		{
			elem = here;
			cout << here->GetObj() << " popped" << endl;
			if (size == 1)
			{
				here = NULL;
			}
			else
			{
				here = here->next;
			}
			delete elem;
			elem = NULL;
			size--;
		}
		else
			cout << "Queue is empty" << endl;
	}
	void thoose()
	{
		if (size != 0)
			cout << here->GetObj() << endl;
		else
			cout << "There are no elements" << endl;
	}
};

int main()
{
	Queue<int> qu;
	qu.push_back(3, 2);
	qu.push_back(5, 1);
	qu.push_back(2, 3);
	qu.push_back(4, 2);
	qu.push_back(6, 1);
	qu.push_back(1, 4);
	for (int i = 0; i < 8; i++)
            qu.pop();

	system("pause");
	return 0;
}