#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#define TRUE 1

#define FALSE 0

#define NULL 0

#define OK 1

#define OVERFLOW 0

#define ERROR 0

typedef int QElemType;

typedef int Status;

typedef struct QNode

{

 QElemType data;

 struct QNode *next;

}QNode,*QueuePtr;

typedef struct

{

 QueuePtr front;

 QueuePtr rear;

}LinkQueue;

/*---------基本操作的函数原型说明---------

Status InitQueue(LinkQueue &Q)//1.构建一个空队列Q

Status DestroyQueue(LinkQueue &Q)//2.销毁队列Q，Q不再存在

Status ClearQueue(LinkQueue &Q)//3.将Q清空

Status QueueEmpty(LinkQueue &Q)//4.若队列Q为空队列，则返回TRUE,否则返回FALSE

int QueueLength(LinkQueue Q)//5.求队列的长度

Status GetHead(LinkQueue Q,QElemType &e)//6.若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR

Status EnQueue(LinkQueue &Q,QElemType e)//7.插入元素e为新的队尾元素

Status DeQueue(LinkQueue &Q,QElemType &e)//8.若队列不空，则删除Q的队头元素，用e返回，并返回OK；否则返回ERROR

Status QueueTraverse(LinkQueue Q,visit())//9.从队头到队尾依次对Q中的每一个元素调用函数visit()。一旦visit失败，则操作失败

*/

//---------基本操作的算法描述---------

Status InitQueue(LinkQueue &Q)//1.构建一个空队列Q

{

 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

 if(!Q.front) exit(OVERFLOW);//分配空间失败，则强制停止程序，并返回OVERFLOW

 Q.front->next=NULL;

 return OK;

}

Status DestroyQueue(LinkQueue &Q)//2.销毁队列Q，Q不再存在

{

 while(Q.front)

 {

  Q.rear=Q.front->next;//Q.rear指向Q.front的下一个节点

  free(Q.front);//释放Q.front所指的节点

  Q.front=Q.rear;//Q.front指向Q.rear的下一个节点

 }

 return OK;

}

/*

Status ClearQueue(LinkQueue &Q)//3.将Q清空

{

 DestroyQueue(&Q);

 InitQueue(&Q);

}

*/

Status ClearQueue(LinkQueue &Q)//3.将Q清空

{

 if(Q.front->next== NULL)

  return OK;

 QueuePtr s = Q.front->next,p;

 while(s)

 {

  p=s->next;

  free(s);

  s = p;

 }

 Q.rear = NULL;

 Q.front ->next = Q.rear ;

 return OK;

}

Status QueueEmpty(LinkQueue &Q)//4.若队列Q为空队列，则返回TRUE,否则返回FALSE

{

 if(Q.front== Q.rear) return TRUE;

 else return FALSE;

}

int QueueLength(LinkQueue Q)//5.求队列的长度

{

 int i=0;

 QueuePtr p=Q.front;

 while(Q.rear!=p)

 {

  i++;

  p=p->next;

 }

 return i;

}

Status GetHead(LinkQueue Q,QElemType &e)//6.若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR

{

 QueuePtr p=Q.front;//p指向队头指针

 if(Q.front==Q.rear)  return ERROR;

 e=p->next->data;

 return OK;

}

Status EnQueue(LinkQueue &Q,QElemType e)//7.插入元素e为新的队尾元素

{

 QueuePtr p;

 p=(QueuePtr)malloc(sizeof(QNode));//动态生成新结

 if(!p)exit(OVERFLOW);

 p->data=e;

 p->next=NULL;

 p->data=e;//将e的值赋给新结点

 p->next=NULL;//新结点的指针为空

 Q.rear->next=p;//原队尾结点的指针域为指向新结点

 Q.rear=p;//尾指针指向新结点

 return OK;

}

Status DeQueue(LinkQueue &Q,QElemType &e)//8.若队列不空，则删除Q的队头元素，用e返回，并返回OK；否则返回ERROR

{

 QueuePtr p=Q.front->next;

 if(Q.front==Q.rear)  return ERROR;

 e=p->data;

 Q.front->next=p->next;

 if(Q.rear==p) Q.rear=Q.front;

 free(p);

 return OK;

}

Status QueueTraverse(LinkQueue Q,void(*visit)(QElemType))//9.从队头到队尾依次对Q中的每一个元素调用函数visit()。一旦visit失败，则操作失败

{

 QueuePtr p=Q.front->next;

 while(p)

 {

  visit(p->data);//对p所指元素调用visit()

  p=p->next;

 }

 printf("\n");

 return OK;

}

void visit(QElemType e)

{

 printf("%  d",e);

}

void main()

{

 int n,a,i,k;

 QElemType d;

 LinkQueue q;

 InitQueue(q);//构造一个空栈

 printf("输入队列的元素个数：");

 scanf("%d",&n);

 printf("输入队列元素为：");

 for(i=0;i<n;i++)

 {

  scanf("%d",&a);

  EnQueue(q,a);

 }

 printf("队列的元素为：");

 QueueTraverse(q,visit);

 printf("此时队列的长度为：L=%d\n",QueueLength(q));

 k=QueueEmpty(q);

 {

  if(k)  printf("判断队列是否为空：队列为空\n");

  else printf("判断队列是否为空：队列不空\n");

 }

 GetHead(q,d);

 printf("队头元素为：d=%d\n",d);

 printf("删除队头元素：%d\n",d);

 DeQueue(q,d);

 GetHead(q,d);

 printf("删除后新的队头元素为：d=%d\n",d);

 printf("删除队头元素后队列的长度为：L=%d\n",QueueLength(q));

 ClearQueue(q);//清空队列

 printf("清空队列后q.front=%u,q.rear=%u,q.front->next=%u\n",q.front,q.rear,q.front->next);

 printf("清空队列后队列的长度为：L=%d\n",QueueLength(q));

 DestroyQueue(q);

 printf("销毁队列后,q.front=%u,q.rear=%u\n",q.front,q.rear);

 printf("销毁队列后队列的长度为：L=%d\n",QueueLength(q));

}