自定义单链表队列的基本接口函数（非循环队列）

单链表构建队列的接口函数

/*******************************************************************
*

• 文件名称 : 单链表构建队列的接口函数
• 文件作者 : [email protected]
• 创建日期 : 2024/04/26
• 文件功能 : 对单链表循环队列的增删改查功能的定义
• 注意事项 : None
• CopyRight (c) 2024 [email protected] All Right Reseverd
• *****************************************************************/

本函数中涉及到的标准C库

#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>

单链表队列中的结点有效数据类型，用户可以根据需要进行修改

typedef int DataType_t;

构造链表队列的结点,链表队列中所有结点的数据类型应该是相同的

typedef struct QueueLikedList
{
	DataType_t data;			 // 结点的数据域
	struct QueueLikedList *next; // 结点的指针域
} QueueLList_t;

构造链表队列管理结点，记录队列的队首及队尾,单独定义可节省空间

typedef struct QueueMnager
{
	struct QueueLikedList *Front; // 管理体的队首指针 指向的类型应该是链表队列的结点
	struct QueueLikedList *Rear;  // 管理体的队尾指针  指向的类型应该是链表队列的结点
} QueueMnager_t;

创建单链表空队列

/*******************************************************************
 *
 *	函数名称:	CirQueueLList_Create
 *	函数功能:   创建单链表空队列
 * 	函数参数:	none
 *	返回结果:
 *				@Head	空队列的管理结构体地址
 *	注意事项:   None
 *	函数作者:   [email protected]
 *	创建日期:   2024/04/26
 *	修改历史:
 *	函数版本:	V1.0
 * *****************************************************************/
// 创建一个空链表队列，空链表队列应该有一个头结点，对链表队列进行初始化
QueueMnager_t *CirQueueLList_Create(void)
{
	// 1.创建一个头结点并对头结点申请内存
	QueueMnager_t *Head = (QueueMnager_t *)calloc(1, sizeof(QueueMnager_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	// 2.对头结点进行初始化
	Head->Front = NULL; // 队首指针指向NULL
	Head->Rear = NULL;	// 队尾指针指向NULL

	// 3.把头结点的地址返回即可
	return Head;
}

创建单链表新结点

/*******************************************************************
 *
 *	函数名称:	QueueLList_NewNode
 *	函数功能:   创建单链表新结点
 * 	函数参数:
 * 				@data	新结点数据域的数据
 *	返回结果:
 *				@New	新结点的地址
 *	注意事项:   None
 *	函数作者:   [email protected]
 *	创建日期:   2024/04/26
 *	修改历史:
 *	函数版本:	V1.0
 * *****************************************************************/
// 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
QueueLList_t *QueueLList_NewNode(DataType_t data)
{
	// 1.创建一个新结点并对新结点申请内存
	QueueLList_t *New = (QueueLList_t *)calloc(1, sizeof(QueueLList_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	// 2.对新结点的数据域和指针域进行初始化
	New->data = data;
	New->next = NULL;

	return New;
}

判断队列是否为空

/*******************************************************************
 *
 *	函数名称:	QueueLList_IsEmpty
 *	函数功能:   判断队列是否为空
 * 	函数参数:
 * 				@Head	队列管理结构体的地址
 *	返回结果:
 *				@bool	为空返回ture，非空返回false
 *	注意事项:   None
 *	函数作者:   [email protected]
 *	创建日期:   2024/04/26
 *	修改历史:
 *	函数版本:	V1.0
 * *****************************************************************/
// 判断链表队列是否为空
bool QueueLList_IsEmpty(QueueMnager_t *Head)
{
	// 当管理结构体中的队首队尾指针都指向NULL时  表示队列中没有结点
	return (NULL == Head->Front && NULL == Head->Rear) ? true : false;
}

入队 向链表队列的尾部进行插入操作

/*******************************************************************
 *
 *	函数名称:	QueueLList_Enqueue
 *	函数功能:   入队	向链表队列的尾部进行插入操作
 * 	函数参数:
 * 				@Head	队列管理结构体的地址
 * 				@data	入队结点数据域的值
 *	返回结果:
 *				@Head	返回入队操作后管理结构体的地址
 *	注意事项:   None
 *	函数作者:   [email protected]
 *	创建日期:   2024/04/26
 *	修改历史:
 *	函数版本:	V1.0
 * *****************************************************************/
// 入队	向链表队列的尾部进行插入操作
QueueMnager_t *QueueLList_Enqueue(QueueMnager_t *Head, DataType_t data)
{
	// 创建新结点接收入队数据
	QueueLList_t *New = QueueLList_NewNode(data);

	// 判断队列是否为空 	为空时队列的队首队尾应当都指向新结点
	if (QueueLList_IsEmpty(Head))
	{
		Head->Front = New;
		Head->Rear = New;
	}
	else
	{
		Head->Rear->next = New; // 队列非空时 队尾指针指向的结点中的next指针应指向新结点
		Head->Rear = New;		// 队尾指针应指向新结点
	}
	return Head;
}

出队

向链表队列的头部进行删除操作
将出队结点数据域的数据储存到变量val中,通常出队操作时涉及到数据输出，所以需要传入主函数的变量地址，防止出队数据在函数调用结束后丢失

/*******************************************************************
 *
 *	函数名称:	QueueLList_Dequeue
 *	函数功能:   出队	对链表队列的头部进行删除操作
 * 	函数参数:
 * 				@Head	队列管理结构体的地址
 * 				@val	出队数据存入的地址
 *	返回结果:
 *				@bool	返回出队是否成功
 *	注意事项:   None
 *	函数作者:   [email protected]
 *	创建日期:   2024/04/26
 *	修改历史:
 *	函数版本:	V1.0
 * *****************************************************************/
// 出队	对链表队列的头部进行删除操作	将出队结点数据域的数据储存到变量val中
bool QueueLList_Dequeue(QueueMnager_t *Head, DataType_t *val)
{
	if (QueueLList_IsEmpty(Head))
	{
		printf("Queue Linked List is Empty!");
		return false;
	}
	else
	{
		QueueLList_t *temp = Head->Front; // 定义指针记录原队首的地址
		*val = Head->Front->data;		  // 将原队首数据域中的值存入变量val中
		Head->Front = Head->Front->next;  // 将队首指针指向队首的下一个结点
		temp->next = NULL;				  // 将原队首中的next指针指向NULL
		free(temp);						  // 释放原队首结点的内存
	}
	return true;
}

主函数中测试

int main(int argc, char const *argv[])
{
	// 创建一个新队列
	QueueMnager_t *Queue = CirQueueLList_Create();

	// 数据入队10	15	20
	QueueLList_Enqueue(Queue, 10);
	QueueLList_Enqueue(Queue, 15);
	QueueLList_Enqueue(Queue, 20);

	DataType_t temp;
	// 出队10	15	20
	QueueLList_Dequeue(Queue, &temp);
	printf("%d\n", temp);
	QueueLList_Dequeue(Queue, &temp);
	printf("%d\n", temp);
	QueueLList_Dequeue(Queue, &temp);
	printf("%d\n", temp);

	return 0;
}

测试结果

总结

队列遵循“先进先出”的规则，在实际编程中可以用多种方法实现，如顺序表，栈，单链表，双链表等等，这些数据结构可能有多种数据输入及输出的方式，所以在构造队列时，一定要注意队列的规则