#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int DataType;
typedef struct node{ 	//队列的链式结点 
	DataType data;
	struct node *next;
}LinkNode;
typedef struct{		//队列的队头和队尾指针 
	LinkNode *front,*rear;  //front永远指向头结点，rear永远指向队尾结点 
}LinkQueue;

/*
	链式队列不存在"溢出"现象
	链式队列初始状态 ：Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	链式队列为空：Q.front==Q.rear; 
*/

//				带头结点的链式队列
//初始化链式队列 
void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));  //创建一个头结点
	Q.front->next=NULL; 
} 
//队列判空 
bool isEmpty(LinkQueue Q){
	if(Q.front==Q.rear){
		return true;
	}else{
		return false;
	}
}
//入队
void EnQueue(LinkQueue &Q,DataType x){
	LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));  //创建新节点
	s->data=x;s->next=NULL;  //队尾添加节点 
	Q.rear->next=s;
	Q.rear=s;  
} 
//出队
bool DeQueue(LinkQueue &Q,DataType &x){
	if(Q.front==Q.rear){   //队列为空 
		return false;  
	}
	LinkNode *s=Q.front->next;  //删除队头结点 
	x=s->data;
	Q.front->next=s->next;
	
	if(s==Q.rear){   //只有一个数据节点时 
		Q.rear=Q.front;
	}
	free(s);
	return true;
} 


int main(int argc,char** argv){
	LinkQueue Q;
	InitQueue(Q);
	EnQueue(Q,100);
	int x;
	DeQueue(Q,x);
	cout<<x<<endl;
	if(isEmpty(Q)){
		cout<<"Kong1"<<endl;
	}
	return 0; 
}