数据结构

链式队列

以链表为基础实现链式队列

1.思路：

如果打算以链表作为基础来实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。

2.图示：

3.代码：

/*****************************************************************************************************************
*	
*	file name	:	LinkedQueue.c
*	author	 	:	cnzycwp@126.com
*	data  	 	:	2024/04/26
*	function	:	以链表为基础实现链式队列的接口程序
*	note	 	:	None
* 	
*  	CopyRight (c)	2024	cnzycwp@126.com 	All Right Reseverd
*
* ****************************************************************************************************************/

#include 
#include 
#include 

//指的是链式队列中的元素的数据类型，用户可以根据需要进行修改
typedef int  DataType_t;

//构造记录链式队列LinkedQueue的结点,链表中所有结点的数据类型应该是相同的
typedef struct LinkedQueue
{
	
    DataType_t  		 data;    //结点的数据域
	struct LinkedQueue	*next;    //结点的指针域	

}LQueue_t;

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Create
*	function	:	创建一个空链式队列，空链式队列应该有一个队列头结点，对链式队列进行初始化
*	argument	:	None
*	retval		:	LQueue_t
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//创建一个空链式队列，空链式队列应该有一个队列头结点，对链式队列进行初始化
LQueue_t * LQueue_Create(void)
{
	//1.创建一个队列头结点并对队列头结点申请内存
	LQueue_t *Head = (LQueue_t *)calloc(1,sizeof(LQueue_t));
	if (NULL == Head)
	{
		perror("Calloc memory for HeadQueue is Failed");
		exit(-1);
	}

	//2.对队列头结点进行初始化，队列头结点是不存储有效内容的！！！
	Head->next = NULL;

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

/*****************************************************************************************************************
*	
*	func name	:	LQueue_NewNode
*	function	:	创建新的队列结点，并对新队列结点进行初始化
*	argument	:	
*					@data
*	retval		:	LQueue_t
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//创建新的队列结点，并对新队列结点进行初始化
LQueue_t * LQueue_NewNode(DataType_t data)
{
	//1.创建一个新队列结点并对新队列结点申请内存
	LQueue_t *New = (LQueue_t *)calloc(1,sizeof(LQueue_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNodeQueue is Failed");
		return NULL;
	}

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

	return New;
}

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Enqueue
*	function	:	对链式队列进行尾部插入操作，称为入队
*	argument	:	
*					@data
*					@Head
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//入队（尾插）
bool LQueue_Enqueue(LQueue_t *Head,DataType_t data)
{
	//1.创建新的结点，并对新结点进行初始化
	LQueue_t *New = LQueue_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node for Queuen");
		return false;
	}
	//2.判断链表是否为空，如果为空，则直接插入即可
	if (NULL == Head->next)
	{
		Head->next = New;
		return true;
	}

	//3.如果链表为非空，则把新结点插入到链表的尾部
    while (Head->next)
    {
        Head = Head->next;
    }
    Head->next = New;			//把尾结点的next指针指向新节点

	return true;
}

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Dequeue
*	function	:	对链式队列进行头部删除操作，称为出队
*	argument	:	
*					@Head
*	retval		:	DataType_t
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//出队（头删）
DataType_t LQueue_Dequeue(LQueue_t *Head)
{
    DataType_t temp = 0;

    //1.判断当前链式队列是否为空，为空则直接退出
	if (Head->next == NULL)
	{
		printf("current linkedqueue is empty!n");
		return -1;
	}

    //2.如果当前链式队列为非空，则删除当前链式队列的头结点
    LQueue_t *Phead = Head->next;       //备份头结点地址

    Head->next = Head->next->next;      //把头结点的next指针指向首结点的直接后继

    Phead->next = NULL;                 //把首结点的next指针指向NULL

    temp = Phead->data;                 //出队首结点的数据域

    return temp;
}

/*****************************************************************************************************************
*	
*	func name	:	LQueue_Print
*	function	:	遍历链式队列的元素
*	argument	:	
*					@Head
*	retval		:	void
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	data  	 	:	2024/04/26
* 	
*
* ****************************************************************************************************************/
//遍历链式队列的元素
void LQueue_Print(LQueue_t *Head)
{
	//对链式队列的头文件的地址进行备份
	LQueue_t *Phead = Head;
	
	//判断头结点的next指针是否指向NULL，若next指针指向NULL则退出
	while(Phead->next)
	{
		//把队列头结点的直接后继作为新的队列头结点
		Phead = Phead->next;

		//输出队列现在头结点的数据域
		printf("%d->",Phead->data);
	}

}


int main(int argc, char const *argv[])
{
	LQueue_t *Head = LQueue_Create();

    //入队
    LQueue_Enqueue(Head,1);
    LQueue_Enqueue(Head,20);
    LQueue_Enqueue(Head,3);
    LQueue_Enqueue(Head,5);
    LQueue_Enqueue(Head,85);
    LQueue_Print(Head);
    printf("n");
	printf("n");

    //出队
    printf("%dn",LQueue_Dequeue(Head));
    printf("%dn",LQueue_Dequeue(Head));
    printf("n");

    //遍历
    LQueue_Print(Head);
    printf("n");


	return 0;
}

4.结果验证：