以链表为基础实现链式队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了以链表为基础实现链式队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构

链式队列

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

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 <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//指的是链式队列中的元素的数据类型，用户可以根据需要进行修改
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 Queue\n");
		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("%d\n",LQueue_Dequeue(Head));
    printf("%d\n",LQueue_Dequeue(Head));
    printf("\n");

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


	return 0;
}

4.结果验证：

以链表为基础实现链式队列文章来源地址https://www.toymoban.com/news/detail-859145.html