#include<stdio.h>
#include<stdlib.h>

typedef char DataType;

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

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



void InitQueue(LinkQueue *Q);
int QueueNotEmpty(LinkQueue Q);
void EnQueue(LinkQueue *Q,DataType x);
void DeQueue(LinkQueue *Q,DataType *x);
void GetHead(LinkQueue Q,DataType *x);
int QueueLength(LinkQueue Q);
void DestoryQueue(LinkQueue *Q);
void Visit(DataType x);
void QueueTraverse(LinkQueue Q);


void InitQueue(LinkQueue *Q)
{
	Q->front=NULL;
	Q->rear=NULL;
}

int QueueNotEmpty(LinkQueue Q)
{
	if(Q.front==NULL)                            /*可以寫作：Q.front==NULL&&Q.rear==NULL，但不能寫作：(Q.front==Q.rear)==NULL*/
		return 0;                                    /*判斷隊列為空，只要Q.front==NULL即可，不需要考慮Q.rear*/
	else return 1;
}

void EnQueue(LinkQueue *Q,DataType x)
{
	QNode *p;                                                 /*原錯寫成LinkQueue *p！！！注意LinkQueue 和QNode 分別表示的含義！！！*/
	p=(QNode *)malloc(sizeof(QNode));
	if(p==0)
	{printf("Wrong in EnQueue()!\n");exit(0);}
	p->data=x;
	p->next=NULL;
	if(!QueueNotEmpty(*Q))
	{printf("QueueNotEmpty=%d\n",QueueNotEmpty(*Q));Q->rear=Q->front=p;}
	else
	{
		Q->rear->next=p;
		Q->rear=p;
	}
}		

void DeQueue(LinkQueue *Q,DataType *x)
{
	QNode *p;
	if(!QueueNotEmpty(*Q))
	{
		printf("The queue is empty!(at DeQueue())!\n");exit(0);
	}
	else if(Q->front==Q->rear)
	{
		*x=Q->front->data;                      /*原錯寫成Q-front.data！！！注意：Q->front也是指針！！！*/
		Q->front=Q->rear=NULL;
	}
	else
	{
		*x=Q->front->data;
		p=Q->front;
		Q->front=Q->front->next;
		free(p);
	}
}

void GetHead(LinkQueue Q,DataType *x)
{
	if(!QueueNotEmpty(Q))
	{
		printf("The queue is empty!(at GetHead())!\n");exit(0);
	}
	else *x=Q.front->data;
}	

int QueueLength(LinkQueue Q)
{
	QNode *p;
	int i=1;
	p=Q.front;
	if(!QueueNotEmpty(Q))
		return 0;
	else
	while(p!=Q.rear)
	{
		p=p->next;
		i++;
	}
	return i;
}
		
void DestoryQueue(LinkQueue *Q)
{
	QNode *p;
	p=Q->front;
	while(QueueNotEmpty(*Q))
	{
		p=Q->front;
		Q->front=Q->front->next;
		free(p);
	}
}

void Visit(DataType x)
{
	printf("%c  ",x);
}

void QueueTraverse(LinkQueue Q)
{
	QNode *q;
	q=Q.front;
	while(q!=NULL)
	{
		Visit(q->data);
		q=q->next;
	}
	printf("\n");
}
	

void main()
{
	LinkQueue myqueue;
	char a[7]={'a','c','d','e','r','t','v'};
	int i;DataType x;
	InitQueue(&myqueue);                          /*！！！原忘記對鏈表隊列進行初始化！！！導致myqueue.front和myqueue.rear都沒有初始值*/
	for(i=0;i<7;i++)
	EnQueue(&myqueue,a[i]);
	printf("The original queue is:\n");
	QueueTraverse(myqueue);
	GetHead(myqueue,&x);
	printf("The head element is:%c\n",x);
	
	DeQueue(&myqueue,&x);
	DeQueue(&myqueue,&x);
	printf("Now,the numble of the elements in the queue is:%d.\n",QueueLength(myqueue));
	printf("The queue is:\n");
	QueueTraverse(myqueue);
	
	DestoryQueue(&myqueue);
}