目录
1.链队
使用链表表示的队列称为链队。
链队需要两个分别指向队头和队尾的指针（头指针和尾指针）才能唯一的确定。为了进行操作的方便我们可以为链队设置头指针，用于入队和出队操作。
相对于顺序队列来说，链队的入队不需要考虑是否申请的空间是否会满的问题，而且在判断队列为的问题上也比较的方便，不需要太多的操作就可以判断，也不用太多的方法考虑。
注：空的链队的头指针和尾指针都指向头节点。
刚开始的时候头指针和尾指针指向的是同一个节点（头节点）。
这是入队一些节点之后的情况，其实和单链表是差不多的，只是在删除和插入方面有限制。
2.链队的相关操作
（1）数据结构的定义
#include<stdlib.h>
#include<stdio.h>
#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）测试
