#include<iostream.h>

struct node
{
	int val;
	struct node* pNext;
};

class Queue
{
private:
	struct node* pHead;
	struct node* pTail;

public:
	Queue()
	{
		pHead = NULL;
		pTail = NULL;
	}

	~Queue()
	{
		this->Clear();
	}

	void InQueue(int val)
	{
		if(pHead == NULL)
		{
			pHead = new node;
			pHead->val = val;
			pHead->pNext = NULL;

			pTail = pHead;
			return;
		}

		struct node* pNew = new node;
		pNew->val = val;
		pNew->pNext = NULL;

		pTail->pNext = pNew;
		pTail = pTail->pNext;

	}

	int OutQueue()
	{
		if(pHead == NULL)//隊列為空，出隊失敗
			return -1;

		int val = pHead->val;
		struct node* pTemp = pHead;
		pHead = pHead->pNext;
		delete pTemp;

		if(pHead == NULL)//如果只有一個元素，出隊之后為空
			pTail = NULL;

		return val;
	}

	void PrintQueue()
	{
		struct node* pTemp = pHead;
		while(pTemp!=NULL)
		{
			cout<<pTemp->val<<"  ";
			pTemp = pTemp->pNext;
		}

		cout<<endl;
	}

	void sort()
	{
		int k;
		struct node* p;
		int n = GetNodeCnt();

		for(int i=0;i<n-1;i++)
		{
			p = pHead;
			for(int j=0;j<n-1-i;j++)
			{
				if(p->val > p->pNext->val)
				{
					k = p->val;
					p->val = p->pNext->val;
					p->pNext->val = k;
				}

				p = p->pNext;
			}
		}
	}

	void Clear()
	{
		struct node* pTemp = pHead;
		while(pTemp!=NULL)
		{
			pHead = pHead->pNext;
			delete pTemp;

			pTemp = pHead;
		}
	}

	int GetNodeCnt()
	{
		int cnt =0;
		struct node* pTemp = pHead;
		while(pTemp!=NULL)
		{
			cnt++;
			pTemp = pTemp->pNext;
		}

		return cnt;
	}

};

void main()
{
	Queue q1;
	q1.InQueue(8);
	q1.InQueue(5);
	q1.InQueue(6);
	q1.InQueue(7);
	q1.InQueue(4);

	q1.PrintQueue();

	q1.sort();
	q1.PrintQueue();

	q1.Clear();

	q1.PrintQueue();



}