队列的链式存储--- 2021.10.27

上一讲链接：

队列的基本概念— 2021.10.8

队列的链式存储：

什么叫队列的链式存储呢？我们在上一讲都知道队列的结构特点，那么我们可不可以通过链表来实现队列，从而实现了队列的链式存储。

那么接下来我们一起来探讨吧！！！

那我们现在先思考一个问题：链表的头节点是做队头还是做队尾？

由于队列具备先进先出的特性，所以我们在插入数据和删除数据时总是会从队头出，从队尾入。所以链表的头节点做队头比较合适。

接下来就开始根据代码具体分析：

//初始化队列
LinkQueue init_LinkQueue()
{
	struct LQueue * myQueue = malloc(sizeof(struct LQueue));
	if (myQueue == NULL)
	{
		return NULL;
	}

	myQueue->m_Size = 0;
	myQueue->pHeader.next = NULL;
	myQueue->pTail = &myQueue->pHeader; //尾节点开始指向的就是头节点
	return myQueue;
}
//入队
void push_LinkQueue(LinkQueue queue, void * data)
{
	//等价于 尾插
	if (queue == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	struct LQueue * myQueue = queue;
	struct QueueNode * myNode = data; 
	
	//更改指针指向
	myQueue->pTail->next = myNode;
	myNode->next = NULL;
	//更新尾节点
	myQueue->pTail = myNode;

	//更新队列大小
	myQueue->m_Size++;
}
//出队
void pop_LinkQueue(LinkQueue queue)
{
	//等价于 头删 

	if (queue == NULL)
	{
		return;
	}
	struct LQueue * myQueue = queue;

	if (myQueue->m_Size == 0)
	{
		return;
	}

	if (myQueue->m_Size == 1)
	{
		myQueue->pHeader.next = NULL;
		myQueue->pTail = &myQueue->pHeader; //维护尾节点指针
		myQueue->m_Size = 0;
		return;
	}

	//记录第一个节点
	struct QueueNode * pFirst = myQueue->pHeader.next;
	myQueue->pHeader.next = pFirst->next;
	//更新队列大小
	myQueue->m_Size--;
}
//返回队头
void * front_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return NULL;
	}
	struct LQueue * myQueue = queue;

	return myQueue->pHeader.next;
}
//返回队尾
void * back_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return NULL;
	}
	struct LQueue * myQueue = queue;

	return myQueue->pTail;
}
//返回队列大小
int size_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return -1;
	}
	struct LQueue * myQueue = queue;

	return myQueue->m_Size;
}
//判断队列是否为空
int isEmpty_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return -1;
	}
	struct LQueue * myQueue = queue;

	if (myQueue->m_Size == 0)
	{
		return 1;
	}

	return 0;
}
//销毁队列
void destroy_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return;
	}
	free(queue);
	queue = NULL;
}

我们还是按照老样子，对上述代码进行逐句分析：

LinkQueue init_LinkQueue()
{
	struct LQueue * myQueue = malloc(sizeof(struct LQueue));
	if (myQueue == NULL)
	{
		return NULL;
	}

	myQueue->m_Size = 0;
	myQueue->pHeader.next = NULL;
	myQueue->pTail = &myQueue->pHeader; //尾节点开始指向的就是头节点
	return myQueue;
}

对该段代码解释如下：
首先我们需要在堆区中申请一段内存空间用来存放队列，即malloc函数。其中LQueue是我们自己定义好的队列结构体，其中的成员变量有头节点，队列的大小，还有记录尾节点的指针（因为我们插入数据时要进行尾插操作），具体代码如下：

struct LQueue
{
	struct QueueNode pHeader; //头节点
	int m_Size; //队列的大小
	struct QueueNode * pTail; //记录尾节点的指针
};

成功建立好队列之后，为了算法的严谨，需要对判断是否申请成功内存空间，如果为空，则自动退出该函数，不再往下进行。
由于该函数为初始化队列函数，所以需要如上述代码一样，设置队列的大小为0，设置头节点的指针域为空，设置尾节点的指
向为头节点，因为队列此时只有一个头节点。

void push_LinkQueue(LinkQueue queue, void * data)
{
	//等价于 尾插
	if (queue == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	struct LQueue * myQueue = queue;
	struct QueueNode * myNode = data; 
	
	//更改指针指向
	myQueue->pTail->next = myNode;
	myNode->next = NULL;
	//更新尾节点
	myQueue->pTail = myNode;

	//更新队列大小
	myQueue->m_Size++;
}

对该段代码解释如下：
成功初始化队列之后，我们需要进行入队操作，即向队列中插入数据。

首先为了算法的严谨，我们需要对传入该函数的入口参数进行校验，如果为空，则自动退出该函数，如果不为空，则继续执行。

同理，我们需要创建一个指针来指向该入口参数queue，创建一个指针来指向待插入的数据data。

然后此时我们需要更改指针的指向来使得该数据成功插入。经过初始化的队列，只有一个头节点，并且尾节点指向了头节点，所以我们需要先将尾节点的指针域指向待插入数据data，即myNode。然后将myNode的指针域指向空即可。然后尾节点还是指向头节点的状态，所以我们需要更新尾节点的指向，将尾节点的指向到myNode即可，此时队列中存在一个头节点和一个插入的新节点。

最后队列大小累加即可。

void pop_LinkQueue(LinkQueue queue)
{
	//等价于 头删 

	if (queue == NULL)
	{
		return;
	}
	struct LQueue * myQueue = queue;

	if (myQueue->m_Size == 0)
	{
		return;
	}

	if (myQueue->m_Size == 1)
	{
		myQueue->pHeader.next = NULL;
		myQueue->pTail = &myQueue->pHeader; //维护尾节点指针
		myQueue->m_Size = 0;
		return;
	}

	//记录第一个节点
	struct QueueNode * pFirst = myQueue->pHeader.next;

	myQueue->pHeader.next = pFirst->next;

	//更新队列大小
	myQueue->m_Size--;

}

对该段代码解释如下：
跟入队同理，出队相对于对该队列中的节点进行头删。

首先为了算法的严谨，我们需要对传入该函数的入口参数进行校验，如果为空，则自动退出该函数，如果不为空，则继续执行。

同时我们还需要考虑一种情况，即此时如果队列中的大小为0，我们就没有必要进行出队操作了，提前退出即可。

如果队列中的情况为只有一个头节点和一个节点呢？我们需要将这个情况特别处理，即我们需要将头节点的指针域指向空，然后将尾节点指向头节点，更新队列的大小即可。

如果队列中节点数量大于一时，则我们需要先通过创建一个指针pFirst提前保存下第一个节点的位置，因为我们要进行头删。然后将头节点的指针域重新指向pFirst的指针域即可，即删除了第一个节点。

然后更新队列大小即可。

void * front_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return NULL;
	}
	struct LQueue * myQueue = queue;

	return myQueue->pHeader.next;

}

对该段代码解释如下：
首先为了算法的严谨，我们需要对传入该函数的入口参数进行校验，如果为空，则自动退出该函数，如果不为空，则继续执行。

通过一个指针来成功访问传入进来的结构体成员。

由于该函数的作用为返回队头，即返回头节点的指针域即可。

void * back_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return NULL;
	}
	struct LQueue * myQueue = queue;

	return myQueue->pTail;

}

对该段代码解释如下：
首先为了算法的严谨，我们需要对传入该函数的入口参数进行校验，如果为空，则自动退出该函数，如果不为空，则继续执行。

通过一个指针来成功访问传入进来的结构体成员。

由于该函数的作用为返回队尾，即返回结构体成员即可。

int size_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return -1;
	}
	struct LQueue * myQueue = queue;

	return myQueue->m_Size;

}

对该段代码解释如下：
首先为了算法的严谨，我们需要对传入该函数的入口参数进行校验，如果为空，则自动退出该函数，如果不为空，则继续执行。

通过一个指针来成功访问传入进来的结构体成员。

由于该函数的作用为返回队列大小，即返回结构体成员即可。

int isEmpty_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return -1;
	}
	struct LQueue * myQueue = queue;

	if (myQueue->m_Size == 0)
	{
		return 1;
	}

	return 0;
}

对该段代码解释如下：
首先为了算法的严谨，我们需要对传入该函数的入口参数进行校验，如果为空，则自动退出该函数，如果不为空，则继续执行。

通过一个指针来成功访问传入进来的结构体成员。

如果队列大小为0，则返回1，如果上述条件都不符合，则返回0。

void destroy_LinkQueue(LinkQueue queue)
{
	if (queue == NULL)
	{
		return;
	}
	free(queue);
	queue = NULL;
}

对该段代码解释如下：
首先为了算法的严谨，我们需要对传入该函数的入口参数进行校验，如果为空，则自动退出该函数，如果不为空，则继续执行。

释放掉该创建好的内存空间，然后置空即可。

结束语

如果觉得这篇文章还不错的话，记得点赞 ，支持下！！！