本文涉及完整代码及测试代码均已提交至Gitee，大家可以点击链接参考。

鄙人乃一介初学者，文中及代码中难免出错，恳请同志们雅正！

我们在之前使用顺序结构的存储方式实现了队列，其中因为要解决时间复杂性还使用了循环队列来实现。既然队列是一个线性表，那么使用链式结构同样可以实现队列。接下来我们看看如何实现链式队列。

?链式队列结构定义

既然是链表，那么肯定和我们之前使用链表时的定义一样，应该定义一个结构体来表示一个结点，其中含有数据域和指针域。

除了结点模型，在链式队列的实现中我们还要考虑队头指针和队尾指针，在这里我们又定义了一个结构体，这个结构体中的成员变量是两个之前定义的结点的指针，其中一个指向头结点，代表队列头。另一个指向尾结点，代表队列尾。

队列结构定义：

typedef int data_t;


//链表中的结点类型定义
typedef struct Node
{
	data_t data;//一个结点的数据域
	struct Node* next;//一个结点的指针域
}node, * ptrnode;

//队列的定义，这个结构体中存储了指向队列头和队列尾的结点指针
typedef struct linkqueue
{
	ptrnode front;//指向队列头结点的结点指针
	ptrnode rear;//指向队列尾结点的结点指针
}linkqueue;

有了队列结构的定义，下面我们来实现以下一些基本的队列操作：

1. 创建并初始化队列
2. 入队
3. 出队
4. 遍历打印链式队列中的元素
5. 判断队空
6. 计算队列中的数据个数
7. 动态内存释放

⭐1.创建并初始化队列

既然我们有两个结构体，其中一个表示结点，另一个表示队列。所以我们需要开辟两次动态内存。第一次为表示队列的结构体开辟一块动态内存，来管理维护队列头和队列尾两个指针。第二次为结点开辟一块空间，来管理维护头结点。

当开辟好后应该对其进行初始化。其中头结点的数据域置0，指针域置空NULL。而队列的队头和队尾，因为此时是个空队列，因此二者应该指向同一个位置，也就是头结点的位置。
下面来看代码：

//1. 创建并初始化队列
/***
**** @return     队列指针
**** @para       no
****/
linkqueue* queue_init()
{
	//申请内存管理队列结构体：
	linkqueue* lq = (linkqueue*)malloc(sizeof(linkqueue));
	if (lq == NULL)
	{
		perror("\nqueue malloc failed");
		return NULL;
	}

	//申请内存来管理结点：
	ptrnode p = (ptrnode)malloc(sizeof(node));
	if (p == NULL)
	{
		perror("\nnode malloc failed");
		free(lq);
		lq = NULL;
		return NULL;
	}

	//数据初始化：
	//刚开始队列头和队列尾相等，都指向头结点p
	p->data = 0;
	p->next = NULL;
	lq->front = lq->rear = p;
	return lq;
}

⭐2.入队

有了一个崭新的队列，我们需要向里面存储数据。和以前一样，函数的参数部分仍然时一个队列指针，一个数据。但是该如何向队列中加入一个新数据呢？
我们知道队列入队只能从队尾进入。此时，我们的队列中有一个不具实际存储意义的头结点，那么想要入队，就必须新建一个结点并将其链接在在头结点后面。然后让队尾指针后移一位，指向新加入的这个结点。注意，这个新结点的数据域就是我们想要放的数据，指针域应该置空。如果不只有头结点，那么这个新结点直接链接在队尾指向的结点之后即可。然后再让队尾指针后移指向新加入的结点。

下面来看代码：

//2. 入队
/***
**** @return     0: success    -1:failed
**** @para       lq:  pointer to link queue     val:  data  
****/
int queue_enter(linkqueue* lq , data_t val)
{
	//判断队列存不存在：
	if (lq == NULL)
	{
		printf("\nqueue is NULL\n");
		return -1;
	}

	//新建一个结点：
	ptrnode p = (ptrnode)malloc(sizeof(node));
	if (p == NULL)
	{
		printf("queue_enter : new node malloc failed\n");
		return -1;
	}
	p->data = val;
	p->next = NULL;

	//将新结点p链接在上一个结点之后
	lq->rear->next = p;//链接结点
	lq->rear = p;//后移队尾
	return 0;
}

⭐3.出队

队列的删除，永远是从队头删除。所以我们可以直接把队头指向的那个结点给free掉，free之前，让队头指向下一个结点即可。如上图，如果我们要删除a0，那么我们将头结点删除掉，直接让front指向a0，但此时，a0已经成为了头结点，其中的数据a0没有了意义，也就相当于把a0这个结点给删除了。
这个函数可以返回被删除的元素，这里因为a0表面被删除了，实际上没被删除，所以就可以直接返回lq->front->data。请看代码：

//3. 出队
/***
**** @return     -1:failed    other:data  deleted
**** @para       lq:  pointer to link queue     
****/
data_t queue_delete(linkqueue* lq)
{
	//判断队列存不存在:
	if (lq == NULL)
	{
		printf("\nqueue is NULL\n");
		return -1;
	}
	//判断队列空不空:
	if (lq->front == lq->rear)
	{
		printf("\nqueue is empty\n");
		return -1;
	}

	ptrnode p = lq->front;
	lq->front = p->next;
	free(p);
	p = NULL;
	return lq->front->data;
}

⭐4.遍历打印链式队列中的元素

要遍历元素，我们就跳过头结点，从头结点之后的一个结点开始，直到队尾。因为头结点是队列队头指向的位置，所以应该是lq->front->next开始。遍历，直到找到队尾。

//4. 遍历打印链式队列中的元素
/***
**** @return     void
**** @para       lq:  pointer to link queue  
****/
void queue_show(linkqueue* lq)
{
	//判断队列存不存在：
	if (lq == NULL)
	{
		printf("\nqueue is NULL\n");
		return ;
	}

	if (lq->front == lq->rear)
	{
		printf("\nqueue is empty\n");
		return;
	}

	ptrnode p = lq->front->next;
	printf("\ndata in queue: ");
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	return;
}

⭐5.判断队空

队头队尾位置相同即为空：

//5. 判断队空
/***
**** @return     0:empty    1:not empty
**** @para       lq:  pointer to link queue
****/
int queue_empty(linkqueue* lq)
{
	return (lq->front == lq->rear) ? 0 : 1;
}

⭐6.计算队列中的数据个数

从队头之后的结点开始算起，直到尾结点。

//6. 计算队列中的数据个数
/***
**** @return     -1:error    other:count of queue
**** @para       lq:  pointer to link queue
****/
int queue_size(linkqueue* lq)
{
	int cnt = 0;
	//判断队列存不存在：
	if (lq == NULL)
	{
		printf("\nqueue is NULL\n");
		return -1;
	}
	//判断队列空不空
	if (lq->front == lq->rear)
	{
		return cnt;
	}
	ptrnode p = lq->front->next;
	while (p)
	{
		cnt++;
		p = p->next;
	}
	return cnt;
}

⭐7.动态内存释放

和以前的链表的释放一样，也是从头结点开始一个一个结点地释放。但是释放完结点后，还需要将队列申请的空间释放掉。

//7. 动态内存释放
linkqueue* queue_free(linkqueue* lq)
{
	//判断队列存不存在：
	if (lq == NULL)
	{
		printf("\nqueue is NULL\n");
		return -1;
	}
	ptrnode p = lq->front;
	while (p)
	{
		lq->front = lq->front->next;
		printf("\nfree : %d", p->data);
		free(p);
		p = lq->front;
	}
	printf("\nfree queue\n");
	free(lq);
	lq = NULL;
	return NULL;
}

?各操作测试代码及结果

我们在main函数中调用各个功能函数，来完成对它们的测试。

代码：

#include "linkqueue.h"


int main()
{
	int input = 0;

	//初始化函数测试：
	linkqueue* lqueue = queue_init();

	//利用循环向队列中存入数据，队列入队函数测试：
	//当输入-1就停止，也就是说输入-1前的那个数字将是队列的最后一个数据
	while (1)
	{
		printf("input:");
		int scanfret = scanf("%d", &input);
		if (input == -1)
			break;
		queue_enter(lqueue, input);
	}

	//打印队列看一下存的和我们输入的一样不一样，，队列遍历打印函数测试：
	queue_show(lqueue);

	//计算队列中数据个数，队列计数函数测试：
	printf("data count: %d ", queue_size(lqueue));

	//删除两个队列中的数，出队函数测试：
	printf("\ndata deleted: %d ", queue_delete(lqueue));
	printf("\ndata deleted: %d ", queue_delete(lqueue));

	//再次打印，看看出队两个数据后的队列：
	queue_show(lqueue);

	//释放内存，可以观察释放的内容：
	lqueue = queue_free(lqueue);
	return 0;
}

测试结果：

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)的， 不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时 间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。