/*
队列的链式表示 
*/

#include<stdio.h>

/*
定义链式队列的存储结构 
*/ 
typedef struct QNode{
	int data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

/*
初始化链式队列 
思想:构造一个只有一个头结点的空队列，将对头指针和队尾指针都指向该结点；
然后将头指针的指针域置空。 
*/
int InitQueue(LinkQueue &Q){
	Q.front=Q.rear=new QNode;
	if(!Q.front){		//存储分配失败 
		return 0;
	}
	Q.front->next=NULL;
	return 1;
}

/*
链队的入队操作：
思想:1.生成一个新结点，
2.将新结点插入到队尾，修改队尾指针。 
*/ 
int EnQueue(LinkQueue &Q,int e){
	
	struct QNode *p;
	p=new QNode;
	
	if(!p){
		printf("存储分配失败!\n");
		return 0;
	}
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return 1;
}

/*
链队的出队操作:
思想: 1.首先判断链队是否为空；
2。若队列非空，将对头元素出队，然后修改对头指针。 
*/
int DeQueue(LinkQueue &Q,int &e){
	if(Q.front==Q.rear){
		printf("队列为空!\n");
		return 0;
	}
	struct QNode *p;
	p=Q.front->next;//指针p指向对头元素
	e=p->data;
	Q.front->next=p->next;//修改对头指针 
	if(Q.rear==p){	//若出队的是最后一个元素，则队尾指针指向头结点 
		Q.rear=Q.front;
	} 
	delete p;
	return 1;
}

/*
计算链队的长度 
思想:
设置一个指针p,让p指向链队的对头元素，当p非空时，length加1. 
*/
int QueueLength(LinkQueue Q){
	int length=0;
	struct QNode *p;
	p=Q.front->next;
	while(p){
		length++;
		p=p->next;
	}
	return length;
}

/*
遍历链队
思想:1.首先获取链队的长度，
2.当变量i小于队列长度时，循环将队列元素出队，并打印出队的元素。 
*/ 
void TraveQueue(LinkQueue Q){
	int len;
	len=QueueLength(Q);
	for(int i=0;i<len;i++){
		int e;
		DeQueue(Q,e);
		printf("%d ",e);
	}
}

int main(){
	LinkQueue Q;
	
	if(InitQueue(Q)){
		printf("链式队列初始化成功!\n"); 
	}else{
		printf("链式队列初始化失败!\n");
	}
	
	int n;
	printf("请输入入队的元素的个数:");
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int e;
		printf("请输入第%d个元素:",i+1);
		scanf("%d",&e);
		EnQueue(Q,e);
	}
	printf("链队Q的长度:%d\n",QueueLength(Q));
	
	printf("遍历链队:\n");
	TraveQueue(Q);
}