#include<iostream>
#include<cstdlib>
#define MAXSIZE 100
using namespace std;

typedef struct Node
{
struct Node *Next;   //队列元素的节点连接 
int Element;
}MyNode;

typedef struct Queue
{
Node *Front;          //Front和Rear连接着各自应有的节点 
Node *Rear; 
int Items;            //队列元素的个数，用于判断是否空队列，满队列 
}*PtrToQueue; 

typedef PtrToQueue MyQueue;

MyQueue Create(void);  //创建一个队列 
void EnQueue(int X,MyQueue Q); //入队 
void DeQueue(MyQueue Q);       //出队 
int IsFull(MyQueue Q);         //判断是否满队 
int IsEmpty(MyQueue Q);        //判断是否为空队列 
void GetQueueFront(MyQueue Q); //获得队头元素，当然，也可以获得队尾元素，这里交给你写了 

int main() //测试 
{
MyQueue Q=Create();
EnQueue(100,Q); 
DeQueue(Q);      
return 0;
}


MyQueue Create(void)
{
MyNode *NewNode;
MyQueue Q;
Q=(MyQueue)malloc(sizeof(struct Queue));  //为MyQueue类型的Q开辟内存 
if(Q==NULL)
   cout <<"空间不足! " <<endl ;
Q->Front=(MyNode *)malloc(sizeof(MyNode)); //为Q的头节点开辟内存 
if(Q->Front==NULL)
   cout <<"空间不足! " <<endl ;
Q->Rear=(MyNode *)malloc(sizeof(MyNode));//为Q的尾节点开辟内存
if(Q->Rear==NULL)
   cout <<"空间不足! " <<endl ;
Q->Front=Q->Rear;   //一开始，头结点就是尾节点 
Q->Items=0;         //队列元素为0 
int a[8]={13,15,17,21,18,38,28,31};
for(int i=0;i<8;i++)
{
NewNode=(MyNode *)malloc(sizeof(MyNode));
   if(NewNode==NULL)
       cout <<"空间不足! " <<endl ;
   NewNode->Element=a[i];  //赋值 
NewNode->Next=NULL;     //新开辟的节点总是尾节点 
if(Q->Items==0)         //如果入的是空队，先入头节点 
{
Q->Front=NewNode; //队头等于NewNode 
Q->Rear=NewNode;  //队尾也是NewNode 
cout <<Q->Front->Element <<"已入列 " <<endl ;
Q->Items++; //入队后元素个数+1 
}
else          //如果入的不是空队 
{
   Q->Rear->Next=NewNode;  //从队尾进去 
   Q->Rear=Q->Rear->Next;  //NewNode成为新的队尾元素 
   cout <<Q->Rear->Element <<"已入列 " <<endl ;
   Q->Items++;  //元素个数+1 
}
}
return Q;
}

void EnQueue(int X,MyQueue Q)
{
if(IsFull(Q))
   cout <<"队列已满不能插入! " <<endl ;
MyNode *NewNode;
NewNode=(MyNode *)malloc(sizeof(MyNode));
if(NewNode==NULL)
   cout <<"空间不足! " <<endl ;
NewNode->Element=X;
NewNode->Next=NULL;
if(Q->Items==0)         //如果入的是空队，先入头节点 
{
Q->Front=NewNode; //队头等于NewNode 
Q->Rear=NewNode;  //队尾也是NewNode 
cout <<Q->Front->Element <<"已入列 " <<endl ;
Q->Items++; //入队后元素个数+1 
}
else          //如果入的不是空队 
{
   Q->Rear->Next=NewNode;  //从队尾进去 
   Q->Rear=Q->Rear->Next;  //NewNode成为新的队尾元素 
   cout <<Q->Rear->Element <<"已入列 " <<endl ;
   Q->Items++;  //元素个数+1 
}
cout <<"入队后 " ; 
GetQueueFront(Q);
}

void DeQueue(MyQueue Q)
{
if(IsEmpty(Q))
   cout <<"空队列 !" <<endl ;
else
{
MyNode *Deletion; 
   Deletion=Q->Front;  //Deletion是方便释放头节点的内存 
   Q->Front=Q->Front->Next;  //队头的下一个元素成为新的队头 
   delete Deletion;          //释放
   Q->Items--;               //出队后，元素个数-1 
   if(Q->Items==0)
   Q->Rear=NULL;
   cout <<"出队后 " ; 
   GetQueueFront(Q);
}
}

int IsFull(MyQueue Q)
{
return Q->Items==MAXSIZE;        //MAXSIZE根据需求定义，如果元素个数为MAXSIZE就返回1，否则返回0 
}

int IsEmpty(MyQueue Q)
{
return Q->Items==0;  //如果队列元素为0则返回1，否则返回0 
}

void GetQueueFront(MyQueue Q)
{
if(IsEmpty(Q))
   cout <<"空队列 !" <<endl ;
else
   cout <<Q->Front->Element <<"为队头 " <<endl <<endl ; //输出队头元素 
}