數據結構（C實現）------- 鏈隊列

數據結構（C實現）------- 鏈隊列

鏈隊列，即隊列的鏈式存儲結構，它是僅在表頭刪除和表尾插入的單鏈表，因此一個鏈隊列需要設置兩個分別指示隊頭元素和隊尾元素的指針，為了操作方便，給鏈隊列添加一個頭結點，並令隊頭指針指向頭結點，由此，空的鏈隊列的判斷條件就是隊頭指針和隊尾指針均指向頭結點。

鏈隊列的類型描述：

//鏈隊列類型描述
typedef int QElemType;
typedef struct node{
	QElemType data;
	struct node *next;
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front; //隊頭指針
	QueuePtr rear;  //隊尾指針
}LinkQueue;

基本操作：

　　1. 鏈隊列的初始化(帶頭結點)Init_LinkQueue(LinkQueue *Q)

//鏈隊列的初始化(帶頭結點)
void Init_LinkQueue(LinkQueue *Q){
    QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
    if(!head)
		exit(OVERFLOW);
    head->next = NULL;
	Q->front = Q->rear = head;
}

　　2. 銷毀鏈隊列Destroy_LinkQueue(LinkQueue *Q)

//銷毀鏈隊列
void Destroy_LinkQueue(LinkQueue *Q){
	//從頭結點開始釋放鏈隊列中所有的結點
	while(Q->front){
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
}

　　3. 清空鏈隊列Clear_LinkQueue(LinkQueue *Q)

//清空鏈隊列
void Clear_LinkQueue(LinkQueue *Q){
	Destroy_LinkQueue(Q);
	Init_LinkQueue(Q);
}

4. 判斷鏈隊列是否為空IsEmpty_LinkQueue(LinkQueue *Q)

//判斷鏈隊列是否為空
int IsEmpty_LinkQueue(LinkQueue *Q){
	return Q->front == Q->rear;

}

5. 求鏈隊列的長度GetLength_LinkQueue(LinkQueue *Q)

//求鏈隊列的長度
int GetLength_LinkQueue(LinkQueue *Q){
	int count = 0;
	//指向存放數據的第一個結點
	QueuePtr p = Q->front->next;
	while(p){
		count++;
		p = p->next;
	}
	return count;
}

6. 取得鏈隊列的頭部元素GetHead_LinkQueue(LinkQueue *Q,QElemType *x)

//取得鏈隊列的頭部元素
void GetHead_LinkQueue(LinkQueue *Q,QElemType *x){
	if(IsEmpty_LinkQueue(Q)){
		printf("鏈隊列為空!\n");
		exit(0);
	}
	else{
		*x = Q->front->next->data;
	}
}

7. 取得鏈隊尾的頭部元素GetRear_LinkQueue(LinkQueue *Q,QElemType *x)

//取得鏈隊尾的頭部元素
void GetRear_LinkQueue(LinkQueue *Q,QElemType *x){
	if(IsEmpty_LinkQueue(Q)){
		printf("鏈隊列為空!\n");
		exit(0);
	}
	else{
		*x = Q->rear->data;
	}
}

8. 入鏈隊列En_LinkQueue(LinkQueue *Q,QElemType x)

//入鏈隊列
void En_LinkQueue(LinkQueue *Q,QElemType x){
	QueuePtr q = (QueuePtr)malloc(sizeof(QNode));
	if(!q)
		exit(OVERFLOW);
	q->data = x;
	q->next = NULL;
	Q->rear->next = q;
	Q->rear = q;
}

9. 出鏈隊列De_LinkQueue(LinkQueue *Q,QElemType *x)

//出鏈隊列
void De_LinkQueue(LinkQueue *Q,QElemType *x){
	QueuePtr q;
	if(IsEmpty_LinkQueue(Q)){
		printf("鏈隊列為空!\n");
		exit(0);
	}
	else{
		*x = Q->front->next->data;
		q = Q->front->next;
		*x = q->data;
		Q->front->next = q->next;
		//刪除元素後隊列為空
		if(q->next == NULL)
			Q->rear = Q->front;
		free(q);
	}
}

10. 輸出鏈隊列Print_LinkQueue(LinkQueue *Q)

//輸出鏈隊列
void Print_LinkQueue(LinkQueue *Q){
	//p指向頭結點的下一個結點，即存放數據的第一個結點
	QueuePtr p = Q->front->next;
	if(IsEmpty_LinkQueue(Q)){
		printf("鏈隊列為空!\n");
		exit(0);
	}
	else{
		while(p){
			printf("%d\t",p->data);
			p = p->next;
		}
	printf("\n");
	} 
}