使用C语言实现链队（带头结点和不带头结点）

目录

1.链队

2.链队的相关操作

（1）数据结构的定义

（2）初始化

（3）判空和入队操作

（4）出队操作

（5）获取队头节点

（6）主函数

（7）测试

---

1.链队

使用链表表示的队列称为链队。

链队需要两个分别指向队头和队尾的指针（头指针和尾指针）才能唯一的确定。为了进行操作的方便我们可以为链队设置头指针，用于入队和出队操作。

相对于顺序队列来说，链队的入队不需要考虑是否申请的空间是否会满的问题，而且在判断队列为的问题上也比较的方便，不需要太多的操作就可以判断，也不用太多的方法考虑。

注：空的链队的头指针和尾指针都指向头节点。

刚开始的时候头指针和尾指针指向的是同一个节点（头节点）。

这是入队一些节点之后的情况，其实和单链表是差不多的，只是在删除和插入方面有限制。

使用C语言实现单链表（带头结点）

使用C语言实现单链表（不带头结点）

使用C语言实现循环单链表（带头结点）

2.链队的相关操作

（1）数据结构的定义

#include
#include
 
#define MAXSIZE 10
 
typedef int ElemType;
 
typedef struct LinkNode {
	ElemType data;
	struct LinkNode*next;
}LinkNode;
 
typedef struct{
	LinkNode*front,*rear;
}LinkQueue;

（2）初始化

带头结点：

//初始化 
void InitLinkQueue(LinkQueue&q){
	q.front=q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	q.rear=q.front;
	q.rear->next=NULL; 
}
 
//销毁链队
void DestryLinkQueue(LinkQueue&q){
	while(q.front!=q.rear){
		LinkNode*p=q.front->next;
		if(q.front->next==q.rear){
			q.rear=q.front;
		}
		q.front->next=p->next;
		free(p);
	}
	free(q.front);
	free(q.rear);
	printf("销毁成功!\n");
} 
 
void MenuSqQueue(){
	printf("--------------1.入队操作---------\n");
	printf("--------------2.出队操作---------\n");
	printf("--------------3.获取队头元素-----\n");
	printf("--------------4.重新初始化-------\n");
	printf("--------------5.退出操作---------\n");
}

不带头结点：

//初始化 
void InitLinkQueue(LinkQueue&q){
	q.rear=q.front=NULL; 
}
//销毁链队
void DestryLinkQueue(LinkQueue&q){
	while(q.front!=NULL){
		LinkNode*p=q.front;
		if(q.front==q.rear&&q.front!=NULL){
			q.rear=q.front;
		}
		q.front=p->next;
		free(p);
	}
	printf("销毁成功!\n");
} 

注：注意不带头结点和带头结点的销毁操作处理。

（3）判空和入队操作

带头结点：

//判空
bool isEmpty(LinkQueue&q){
	if(q.front==q.rear){
		return true;
	}else{
		return false;
	}
} 
 
//入队操作
void EnQueue(LinkQueue&q,ElemType e){
	LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=e;
	s->next=q.rear->next;
	q.rear->next=s;
	q.rear=s;
	printf("入队成功!\n");
} 

不带头结点：

//入队操作
void EnQueue(LinkQueue&q,ElemType e){
	LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=e;
	s->next=NULL;
	if(q.front==NULL){
		q.front=s;
		q.rear=s;
	}else{
		q.rear->next=s;
		q.rear=s; 
	}
	printf("入队成功!\n");
} 

注：当队列中没有节点的时候，需要进行特殊的处理。

（4）出队操作

带头结点：

//出队操作
void DeQueue(LinkQueue&q,ElemType &e,int&mask){
	if(isEmpty(q)){
		printf("队列为空!\n");
		mask=0;
		return;
	}
	LinkNode*p=q.front->next;
	e=p->data;
	mask=1;
	//如果是最后一个节点需要特殊处理
	if(q.front->next==q.rear){
		q.rear=q.front;
	}
	q.front->next=p->next;
	free(p);
	printf("出队成功!\n");
}

注：虽然设置了头结点，但是也需要对其最后一个节点进行特殊的处理。

不带头结点：

//出队
void DeQueue(LinkQueue&q,ElemType&e,int&mask){
	if(q.front==NULL){
		printf("空队列!\n");
		mask=0;
		return;
	}
	LinkNode*p=q.front;
	e=p->data;
	mask=1;
	q.front=p->next;
	if(q.rear==p){
		q.rear=NULL;
		q.front=NULL;
	}
	free(p);
	printf("出队成功!\n");
} 

注：对于不带头结点的出队操作主要注意的是只有一个节点的时候，那么需要对其进行特殊的处理。

（5）获取队头节点

带头结点：

//获取队头元素
void GetQueueHead(LinkQueue&q,ElemType &e,int&mask){
	if(isEmpty(q)){
		printf("队列为空!\n");
		mask=0;
		return;
	}
	e=q.front->next->data;
	mask=1;
} 

不带头结点：

//获取队头元素
void GetQueueHead(LinkQueue&q,ElemType &e,int&mask){
	if(q.front==NULL){
		printf("队列为空!\n");
		mask=0;
		return;
	}
	e=q.front->data;
	mask=1;
}

（6）主函数

int main(){
	LinkQueue q;
	ElemType e;
	int flag=0;
	InitLinkQueue(q);
	int mask=1;
	while(1){
		MenuSqQueue();
		printf("请输入操作: ");
		scanf("%d",&flag);
		switch(flag){
			case 1:
				printf("请输入元素(-1_end): ");
				scanf("%d",&e);
				while(e!=-1){
					EnQueue(q,e);
					printf("请输入元素(-1_end): ");
					scanf("%d",&e);
				}
				break;
			case 2:
				DeQueue(q,e,mask);
				if(mask!=0){
					printf("出队元素 = %d\n",e);
				}
				break;
			case 3:
				GetQueueHead(q,e,mask);
				if(mask!=0){
					printf("获取元素 = %d\n",e);
				}
				break;
			case 4:
				InitLinkQueue(q);
				printf("初始化成功!\n");
				break;
			default:
				DestryLinkQueue(q);
				printf("操作结束!\n"); 
		}
		if(flag==5){
			break;
		}
	}
	
	return 0;
}

（7）测试