链队列采用带头结点的链表，队头指针始终指向头结点，队尾指针始终指向最后一个元素

 

当队列为空时：队头指针和队尾指针均指向头结点

链队列不会满！！！

 

 

链队列的定义：

1.定义一种结点结构体：指针域指向下一个结点，数据域存储数据

2.定义链队列结构体：分别存储两个结点指针，队头指针和队尾指针

typedef char DataType;typedef struct Node{	DataType data;	struct Node* next;}LinkQueueNode;typedef struct Queue{	LinkQueueNode *front;	LinkQueueNode *rear;}LinkQueue;

　　

 

链队列的初始化

队头指针和队尾指针相等且均为空

bool InitQueue(LinkQueue* Q){	Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));	if(Q->front!=NULL)		{			Q->front->next=NULL;			Q->rear=Q->front;			return true;		}	else	{		return false;	}}

　　

入队：

记得队尾的元素的next域为空

bool EnterQueue(LinkQueue* Q,DataType x){	LinkQueueNode *p;	p=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));	if(p!=NULL)		{			p->data=x;			Q->rear->next=p;			p->next=NULL;//注意要赋空 			Q->rear=p;			return true;			}	else	return false;}

　　出对

1.删除操作之间要判断是否为空

2.要根据删除操作之后是否为空来决定队尾指针是否等于队头指针

bool DelteQueue(LinkQueue* Q,DataType* x){	LinkQueueNode* p;	//记住：删除操作之前要记得判断是否为空 	if(Q->front==Q->rear)		return false;	else		{			p=Q->front->next;			*x=p->data;			Q->front->next=p->next;			if(p==Q->rear)				Q->rear=Q->front; 				free(p);			return true;		}}

　　

可以这样理解：1.判断是否为空

　　　　　　　2.使p=front-》next

　　　　　　　3.赋值给x

　　　　　　　4.使p出对:

Q->front->next=p->next; 　　　　　　　

 

　　　　　　　5.判断p出对之后是否为空

　　　　　　　　　　若为空：队尾指针等于队头指针

　　　　　　　　　　若不为空：不做处理

　　　　　　6.释放p