/*
队列的线性表示--循环队列 
*/ 
#include<stdio.h>
#define MAXQSIZE 100

/*
定义顺序队列 
*/
typedef struct{
	int *base;//分配存储空间 
	int front;//队头指针 
	int rear;//队尾指针 
}SqQueue;

//初始化循环队列 
/*
算法思想：
循环队列的初始化就是动态分配一个预定义大小的数组空间，base指向数组的基地址，
队头指针和队尾指针都置为0，表是队列为空。 
*/
int InitQueue(SqQueue &Q){
	Q.base=new int[MAXQSIZE];//分配存储空间
	if(!Q.base) return 0;//存储空间分配失败 
	Q.front=Q.rear=0;
	return 1;
}

/*
求队列的长度 
算法思想：
循环队列的长度的计算方法是:尾指针和头指针的差值再加上MAXSIZE然后和MAXQSIZE取模 
*/
int QueueLength(SqQueue Q){
	return ((Q.rear-Q.front)+MAXQSIZE)%MAXQSIZE;
}

/*
入队操作：将元素e入队Q 
算法思想： 1.首先判断队列是否已满，若满，则返回；
			2.若队列不满，将e入队，队尾指针加1 
*/
int EnQueue(SqQueue &Q,int e){
	//首先判断队列是否已满
	if((Q.rear+1)%MAXQSIZE==Q.front){
		return 0;
	} 
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXQSIZE;
	return 1;
}

/*
出队操作：
 思想：
 1.首先判断队列是否为空，若空，返回0；
 2.若不为空，则将元素出队，修改对头指针。 
*/
int DeQueue(SqQueue &Q,int &e){
	if(Q.front==Q.rear){
		return 0;
	}
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXQSIZE;
	return 1;
}


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

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