/*
==========================================================================================
				队列的基本操作
		By~fanxingzju		2014.04.17
1.构造一个空队列Q
2.销毁队列Q，Q不再存在
3.将Q清为空队列
4.若队列Q为空，则返回true，否则换回false
5.用length返回队列Q的元素个数
6.若队列不为空，则用elem返回队列Q的队头元素，并返回true；否则换回false
7.插入元素elem为队列Q的新的队尾元素
8.若队列不为空，则删除Q的队头元素，用elem返回其值，并返回true，否则返回false
==========================================================================================
*/
#include <stdio.h>
#include <stdlib.h>

typedef int QElement;

typedef struct QNode
{
	QElement data;
	struct QNode *next;
}QNode;

typedef struct
{
	QNode *front;
	QNode *rear;
}LinkQueue;

//1.构造一个空队列Q
bool InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = new QNode;
	if (!Q.front)
	{
		printf("InitQueue()函数执行，内存分配失败\n");
		system("pause");
		exit(-1);
	}
	Q.front->next = NULL;
	printf("InitQueue()函数执行，队列初始化成功\n");
	return true;
}

//2.销毁队列Q，Q不再存在
bool DestoryQueue(LinkQueue &Q)
{
	while(Q.front)
	{
		Q.rear = Q.front->next;
		delete Q.front;
		Q.front = Q.rear;
	}
	printf("DestoryQueue()函数执行，队列销毁成功\n");
	return true;
}

//3.将Q清为空队列
bool ClearQueue(LinkQueue &Q)
{
	QNode *temp = Q.front->next;
	while(!temp)
	{
		QNode *ttemp = temp->next;
		temp = temp->next;
		delete ttemp;
	}
	Q.front->next = NULL;
	Q.rear = Q.front;
	printf("ClearQueue()函数执行，清空队列成功\n");
	return true;
}

//4.若队列Q为空，则返回true，否则换回false
bool EmptyQueue(LinkQueue Q)
{
	if (Q.front == Q.rear)
	{
		printf("EmptyQueue()函数执行，队列为空\n");
		return true;
	}
	printf("EmptyQueue()函数执行，队列非空\n");
	return false;
}

//5.用length返回队列Q的元素个数
bool LengthQueue(LinkQueue Q,int &length)
{
	length = 0;
	QNode *temp = Q.front;
	while(temp != Q.rear)
	{
		++length;
		temp = temp->next;
	}
	printf("LengthQueue()函数执行，队列的长度为 %d \n",length);
	return true;
}

//6.若队列不为空，则用elem返回队列Q的队头元素，并返回true；否则换回false
bool GetHeadQueue(LinkQueue Q,QElement &elem)
{
	if (Q.front == Q.rear)
	{
		printf("GetHeadQueue()函数执行，队列为空，获取头元素失败\n");
		return false;
	}
	elem = Q.front->next->data;
	printf("GetHeadQueue()函数执行，队列的头元素为 %d \n",elem);
	return true;
}

//7.插入元素elem为队列Q的新的队尾元素
bool InsertQueue(LinkQueue &Q,QElement elem)
{
	QNode *temp;
	temp = new QNode;
	if (!temp)
	{
		printf("InsertQueue()函数执行，内存分配失败\n");
		exit(-1);
	}
	temp->data = elem;
	temp->next = NULL;
	Q.rear->next = temp;
	Q.rear = temp;
	printf("InsertQueue()函数执行，元素 %d 插入成功\n",elem);
	return true;
}

//8.若队列不为空，则删除Q的队头元素，用elem返回其值，并返回true，否则返回false
bool DeleteQueue(LinkQueue &Q,QElement &elem)
{
	if (Q.front == Q.rear)
	{
		printf("DeleteQueue()函数执行，目标队列为空，删除头元素失败\n");
		return false;
	}

	QNode *temp = Q.front->next;
	elem = temp->data;
	Q.front->next = temp->next;
	if (Q.rear == temp)
	{
		Q.rear = Q.front;
	}
	delete temp;
	printf("DeleteQueue()函数执行，头元素 %d 删除成功\n",elem);
	return true;
}

int main()
{
	LinkQueue Q;
	int length;
	QElement temp;

	InitQueue(Q);
	for (int i = 0; i != 10; ++i)
	{
		LengthQueue(Q,length);
		InsertQueue(Q,i);
	}
	EmptyQueue(Q);
	ClearQueue(Q);
	EmptyQueue(Q);

	for(int i = 9; i != 1; --i)
	{
		InsertQueue(Q,i);
	}
	
	LengthQueue(Q,length);

	while(DeleteQueue(Q,temp))
	{
		GetHeadQueue(Q,temp);
	}

	EmptyQueue(Q);

	DestoryQueue(Q);

	system("pause");
	return 0;
}