데이터 구조 (대기 열): 양 끝 대기 열

/*
	*    (  ):    
	*      ,      
	*Date:2017/4/16
	*/
#include 
#include 
#define ElemType char
#define InitSize 100

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode;

typedef struct{
	LNode *front,*rear;
	int length;
}LinkQueue;

void initQueue(LinkQueue &Q);	//     
bool emptyQueue(LinkQueue Q);	//    
void EnQueueFront(LinkQueue &Q,ElemType e);	//    
void EnQueueBack(LinkQueue &Q,ElemType e);	//    
void DeQueueFront(LinkQueue &Q,ElemType &e);	//    
void DeQueueBack(LinkQueue &Q,ElemType &e);	//    
void getHeadFront(LinkQueue Q,ElemType &e);	//         
void getHeadBack(LinkQueue Q,ElemType &e);	//         
void printQueue(LinkQueue Q);	//    
void clearQueue(LinkQueue &Q);	//    

void initQueue(LinkQueue &Q){
	ElemType e;
	Q.front = Q.rear = (LNode *)malloc(sizeof(LNode));	//Q.front      
	Q.rear->next = NULL;
	Q.length = 0;
	while(scanf("%c",&e) != EOF && e != '
'){
		if(Q.length < InitSize){
			LNode *p = (LNode *)malloc(sizeof(LNode));
			p->data = e;
			p->next = NULL;
			Q.rear->next = p;
			Q.rear = p;
			Q.length++;
		}
	}
}

bool emptyQueue(LinkQueue Q){
	if(Q.front == Q.rear){
		return true;
	}else{
		return false;
	}
}

void EnQueueFront(LinkQueue &Q,ElemType e){
	if(Q.length < InitSize){
		LNode *p = (LNode *)malloc(sizeof(LNode));
		p->data = e;
		p->next = Q.front->next;
		Q.front->next = p;
		Q.length++;
	}
}

void EnQueueBack(LinkQueue &Q,ElemType e){
	if(Q.length < InitSize){
		LNode *p = (LNode *)malloc(sizeof(LNode));
		p->data = e;
		p->next = NULL;
		Q.rear->next = p;
		Q.rear = p;
		Q.length++;
	}
}

void DeQueueFront(LinkQueue &Q,ElemType &e){
	if(!emptyQueue(Q)){
		LNode *p;
		e = Q.front->next->data;
		p = Q.front->next;
		Q.front->next = p->next;
		free(p);
		Q.length--;
	}
}

void DeQueueBack(LinkQueue &Q,ElemType &e){
	if(!emptyQueue(Q)){
		LNode *p = Q.front;
		e = Q.rear->data;
		while(p->next != Q.rear){
			p = p->next;
		}
		p->next = NULL;
		free(Q.rear);
		Q.rear = p;
		Q.length--;
	}
}

void getHeadFront(LinkQueue Q,ElemType &e){
	if(!emptyQueue(Q))
		e = Q.front->next->data;
}

void getHeadBack(LinkQueue Q,ElemType &e){
	if(!emptyQueue(Q))
		e = Q.rear->data;
}

void printQueue(LinkQueue Q){
	LNode *p = Q.front->next;
	while(p != NULL){
		printf("%c",p->data);
		p = p->next;
	}
	printf("
");
}

void clearQueue(LinkQueue &Q){
	LNode * p = Q.front;
	while(Q.front != Q.rear){
		Q.front = p->next;
		free(p);
		p = Q.front;
	}
	free(Q.rear);
	printf("      
");
}

int main(){
	freopen("in.txt","r",stdin);
	LinkQueue Q;
	ElemType e;
	
	initQueue(Q);
	printQueue(Q);
	
	EnQueueFront(Q,'F');
	printf("EnQueueFront(&Q,'F'):
");
	printQueue(Q);

	EnQueueBack(Q,'B');
	printf("EnQueueBack(&Q,'B'):
");
	printQueue(Q);

	DeQueueFront(Q,e);
	printf("DeQueueFront(&Q,e):%c
",e);
	printQueue(Q);

	DeQueueBack(Q,e);
	printf("DeQueueBack(&Q,e):%c
",e);
	printQueue(Q);

	getHeadFront(Q,e);
	printf("getHeadFront(Q,e):%c
",e);

	getHeadBack(Q,e);
	printf("getHeadBack(Q,e):%c
",e);

	if(emptyQueue(Q)){
		printf("Q is NULL
");
	}else{
		printf("Q isn't NULL
");
	}
	clearQueue(Q);
	if(emptyQueue(Q)){
		printf("Q is NULL
");
	}else{
		printf("Q isn't NULL
");
	}

	return 0;
}