梦飞环报

链式队列

2024-04-26 20:35 由 飞子的唠唠叨 发表于 #操作系统

队列

原理介绍：

​ 队列（Queue）和栈类似，相同点是都属于线性结构，不同点是栈遵循“后进先出”原则，而队列遵循“*先进先出*”的原则，也被称为“FIFO”结构，就是“First Input First Output”

​ 数据结构中的队列的两端都允许操作，只不过要求数据只能从队列的一端插入，从队列的另一端删除，可以把队列理解为一根水管，水管有进水口和出水口。一般把允许数据插入的一端称为队尾（Tail或者Rear），一般把允许删除数据的一端称为队头队首（Head或者Front）。

图示一：

图示二：

  • 把允许数据插入的一端称为队尾（允许数据插入到队列的操作称为入队，英文enqueue）

  • 把允许删除数据的一端称为队头（允许数据从队列删除的操作称为出队，英文dequeue）

代码实现“队列”：

循环队列：以数组为基础

​ 如果以数组为基础，一般会把队列设置为循环队列，循环队列也被称为“环形缓冲区”，因为如果队列中的元素出队，则需要把该元素的后继元素整体向前移动，这是时间复杂度为O(n)的操作。如果数据出队之后不去移动后继元素又会导致数组的空间被浪费。

​ 为了解决该问题，可以把队列设置为循环队列，在移动数据的时候只需要移一次即可，所以时间复杂度就是O(1)。如下图所示：

！！！注意：为了区分循环队列空间是否存满，需要预留一个空间用于辨别，即：

队列‘满’：（队尾下标+1）%容量 == 队首下标

队列‘空’： 队尾下标 == 队首下标

当队首和队尾下标均从0开始时，后续进行入队和出队操作时，需要先赋值再改下标

代码实现过程：

​ 为了方便管理循环队列，所以用户可以构造一个结构体类型作为管理结构体，用于存储队列相关的重要信息（容量、队首下标、队尾下标、堆内存首地址）。因为队列可以从两端对数据进行操作，所以需要设置两个变量用于存储下标，来区分队头队尾。

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

//构造记录循环队列CircularQueue各项参数(循环队列的首地址 + 循环队列的容量 + 循环队列队尾下标+队首下标)的结构体
typedef struct CircularQueue
{
	DataType_t * Addr;		//记录循环队列首地址
	unsigned int Size;		//记录循环队列的容量
	int			 Rear;      //循环队列队尾下标	
	int			 Front;     //循环队列队首下标

}CirQueue_t;

  1. 创建空的循环队列，并对管理结构体进行初始化：容量、队尾下标、队首下标、首地址

    //创建循环队列并对循环队列进行初始化
CirQueue_t * CirQueue_Create(unsigned int size)
{
	//1.利用calloc为循环队列的管理结构体申请一块堆内存
	CirQueue_t *Manager = (CirQueue_t *)calloc(1,sizeof(CirQueue_t));

	if(NULL == Manager)
	{
		perror("calloc memory for manager is failed");
		exit(-1); //程序异常终止
	}

	//2.利用calloc为所有元素申请堆内存
	Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));

	if (NULL == Manager->Addr)
	{
		perror("calloc memory for element is failed");
		free(Manager);
		exit(-1); //程序异常终止
	}

	//3.对管理循环队列的结构体进行初始化（循环队列容量 + 队尾下标+队首下标）
	Manager->Size = size;	//对循环队列中的容量进行初始化
	Manager->Rear = 0;		//队尾下标初值为0
	Manager->Front = 0;		//队首下标初值为0
	
	return Manager;
}

  2. 把需要插入到循环队列的元素按照“先进先出”进行入队，此时需要从队列队尾入队。

    //入队
bool CirQueue_Enqueue(CirQueue_t *Manager, DataType_t Data)
{
	//1.判断循环队列是否已满
	if ( CirQueue_IsFull(Manager) )
	{
		printf("CirQueue is Full!\n");
		return false;
	}

	//2.如果循环队列有空闲空间，则把新元素添加到循环队列尾部
	Manager->Addr[Manager->Rear] = Data;


	//防止队尾下标越界,即超过循环队列的容量
	Manager->Rear = (Manager->Rear+1) % Manager->Size;


	return true;
}

  3. 把需要插入到循环队列的元素按照“先进先出”进行出队，此时需要从队列队首出队!

    //出队
DataType_t CirQueue_Dequeue(CirQueue_t *Manager)
{
	DataType_t temp =0;

	//1.判断循环队列是否为空
	if ( CirQueue_IsEmpty(Manager) )
	{
		printf("CirQueue is Empty!\n");
		return false;
	}

	//2.把元素从队首出队，并备份到变量temp
	temp = Manager->Addr[Manager->Front];
	
	//防止队首下标越界
	Manager->Front = (Manager->Front+1) % Manager->Size;


	return temp;
}

  4. 对循环队列进行元素出队和元素入队时，需要对循环队列元素数量进行分析(满 or 空)

    //判断循环队列是否已满
bool CirQueue_IsFull(CirQueue_t *Manager)
{
	return ( (Manager->Rear + 1) % Manager->Size == Manager->Front ) ? true : false;
}


//判断循环队列是否为空
bool CirQueue_IsEmpty(CirQueue_t *Manager)
{
	return (Manager->Front == Manager->Rear) ? true : false;
}

    循环队列代码完整展示：

    /********************************************************************************************************
*
*
* 该程序实现循环队列元素的增删改查，目的是提高设计程序的逻辑思维，另外为了提高可移植性，所以循环队列中元素
* 的数据类型为DataType_t，用户可以根据实际情况修改循环队列中元素的类型。
*
* 另外，为了方便管理循环队列,所以用户设计SeqList_t结构体，该结构体中包含三个成员：地址+容量+有效元素的下标
*
* 
*
* Copyright (c)  2023-2024   cececlmx@126.com   All right Reserved
* ******************************************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>




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

//构造记录循环队列CircularQueue各项参数(循环队列的首地址 + 循环队列的容量 + 循环队列队尾下标+队首下标)的结构体
typedef struct CircularQueue
{
	DataType_t * Addr;		//记录循环队列首地址
	unsigned int Size;		//记录循环队列的容量
	int			 Rear;      //循环队列队尾下标	
	int			 Front;     //循环队列队首下标

}CirQueue_t;


//创建循环队列并对循环队列进行初始化
CirQueue_t * CirQueue_Create(unsigned int size)
{
	//1.利用calloc为循环队列的管理结构体申请一块堆内存
	CirQueue_t *Manager = (CirQueue_t *)calloc(1,sizeof(CirQueue_t));

	if(NULL == Manager)
	{
		perror("calloc memory for manager is failed");
		exit(-1); //程序异常终止
	}

	//2.利用calloc为所有元素申请堆内存
	Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));

	if (NULL == Manager->Addr)
	{
		perror("calloc memory for element is failed");
		free(Manager);
		exit(-1); //程序异常终止
	}

	//3.对管理循环队列的结构体进行初始化（循环队列容量 + 队尾下标+队首下标）
	Manager->Size = size;	//对循环队列中的容量进行初始化
	Manager->Rear = 0;		//队尾下标初值为0
	Manager->Front = 0;		//队首下标初值为0
	
	return Manager;
}


//判断循环队列是否已满
bool CirQueue_IsFull(CirQueue_t *Manager)
{
	return ( (Manager->Rear + 1) % Manager->Size == Manager->Front ) ? true : false;
}


//入队
bool CirQueue_Enqueue(CirQueue_t *Manager, DataType_t Data)
{
	//1.判断循环队列是否已满
	if ( CirQueue_IsFull(Manager) )
	{
		printf("CirQueue is Full!\n");
		return false;
	}

	//2.如果循环队列有空闲空间，则把新元素添加到循环队列尾部
	Manager->Addr[Manager->Rear] = Data;


	//防止队尾下标越界
	Manager->Rear = (Manager->Rear+1) % Manager->Size;


	return true;
}





//判断循环队列是否为空
bool CirQueue_IsEmpty(CirQueue_t *Manager)
{
	return (Manager->Front == Manager->Rear) ? true : false;
}



//出队
DataType_t CirQueue_Dequeue(CirQueue_t *Manager)
{
	DataType_t temp =0;

	//1.判断循环队列是否为空
	if ( CirQueue_IsEmpty(Manager) )
	{
		printf("CirQueue is Empty!\n");
		return false;
	}

	//2.把元素从队首出队，并备份到变量temp
	temp = Manager->Addr[Manager->Front];
	
	//防止队首下标越界
	Manager->Front = (Manager->Front+1) % Manager->Size;


	return temp;
}






int main(int argc, char const *argv[])
{

	
	return 0;
}

链式队列：以链表为基础

​ 如果打算以链表作为基础来实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。 且使用链式队列时，不用考虑队列的容量大小。

代码实现过程：

​ 为了方便管理链式队列，所以用户可以构造一个结构体类型作为管理结构体，用于存储队列相关的重要信息（数据域+指针域）。因为链式队列不需要考虑大小问题，所欲不需要定义容量变量。

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

//构造记录链式队列LinkQueue各项参数(节点中存储数据 + 当前节点的直接后继地址)的结构体
typedef struct LinkQueue
{
	DataType_t            data;		//记录节点中存储数据
	struct LinkQueue     *next;		//记录当前节点的直接后继地址

}LkQueue_t;

  1. 创建空的链式队列，并对管理结构体进行初始化：数据域+指针域

    /********************************************************************
*
*	name	 :	LkQueue_Create
*	function :  创建链式队列队首，并完成对队首的初始化
*	argument :  
*				none			
*	retval	 :  调用成功返回创建成功的队首地址
*	author	 :  790557054@qq.com
*	date	 :  2024/04/26
* 	note	 :  none
* 	
* *****************************************************************/
LkQueue_t *LkQueue_Create(void)
{
    //为队首申请堆空间，并完成错误处理
    LkQueue_t *Front = (LkQueue_t *)calloc(1, sizeof(LkQueue_t)); 
    if(Front == NULL)
    {
        perror("Calloc  memory for Front is Failed!");
        exit(-1);
    }

    //对队首初始化
    Front->next = NULL;

    //返回队首地址
    return Front; 
}

  2. 在创建新的节点，用于存储需要存入链式队列的元素。

    /********************************************************************
 *
 *	name	 :	LkQueue_NewNode
 *	function :  创建新的结点，并对新结点进行初始化（数据域 + 指针域）
 *	argument :
 *				@data 新节点需要存储的数据
 *
 *	retval	 :  调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
LkQueue_t *LkQueue_NewNode(DataType_t data)
{
	// 1.创建一个新结点并对新结点申请内存
	LkQueue_t *New = (LkQueue_t *)calloc(1, sizeof(LkQueue_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

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

	return New;
}

  3. 把需要插入到链式队列的元素按照“先进先出”进行入队，此时需要从队列队尾入队，即进行单链表的尾插操作。

    /********************************************************************
 *
 *	name	 :	LkQueue_EnQueue
 *	function :  将新节点尾插进链式队列中，即完成入队操作
 *	argument :
 *				@Front 链式队列的队首
 *				@data 新节点的数据域需要存储的数据
 *
 *	retval	 :  调用成功输出"插入成功"，否则输出"插入失败"
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
void LkQueue_EnQueue(LkQueue_t *Front, DataType_t data)
{
	// 定义一个循环指针变量PFront
	LkQueue_t *PFront = Front->next;
	// 调用函数创立一个新节点,并完成对应的错误处理
	LkQueue_t *New = LkQueue_NewNode(data);
	if (New == NULL)
	{
		printf("EnQueue is fail!\n");
		return;
	}

	// 进行判断，排除空链表的情况
	if (Front->next == NULL)
	{
		Front->next = New;
		printf("EnQueue of %d is success!\n", New->data);
		return;
	}

	// 先遍历得到尾结点在插入
	// 1.遍历至尾结点，将尾结点的next更换为新节点
	while (PFront->next != NULL)
	{
		PFront = PFront->next;
	}
	// 跳出while循环时，PFront极为尾节点;
	PFront->next = New;

	printf("EnQueue of %d is success!\n", New->data);

	return;
}

  4. 把需要插入到循环队列的元素按照“先进先出”进行出队，此时需要从队列队首出队,即进行单链表的头删操作。

    /********************************************************************
 *
 *	name	 :	LkQueue_DeQueue
 *	function :  删除链表的首节点，并保持链表的连续性
				即完成链式队列的出队操作
 *	argument :
 *				@Front 链式队列队首
 *
 *	retval	 :  调用成功后删除链式队列的首节点
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
void LkQueue_DeQueue(LkQueue_t *Front)
{
	// 对链式队列的队首的地址进行备份
	LkQueue_t *PFront = Front->next;

	// 判断当前链表是否为空，为空则直接退出
	if (Front->next == 	NULL)
	{
		printf("current linkequeue is empty!\n");
		return;
	}

	// 1.将首节点更换
	Front->next = Front->next->next;
	// 2.将备份与链表节点断开
	PFront->next = NULL;
	// 3.释放掉原首节点
	free(PFront);

	printf("DeQueue is success!\n");

	return;
}

  5. 对链式队列中存储的元素进行遍历输出操作，观察是否符合队列的“先进先出”特点

    /********************************************************************
 *
 *	name	 :	LkQueue_Print
 *	function :  遍历输出链式队列中所有节点的数据域
 *	argument :
 *				@Front 链式队列队首
 *
 *	retval	 :  调用成功输出链表中所有节点的数据域的值
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
void LkQueue_Print(LkQueue_t *Front)
{
	// 对链式队列的队首的地址进行备份
	LkQueue_t *PFront = Front;

	// 判断当前链表是否为空，为空则直接退出
	if (Front->next == NULL)
	{
		printf("current linkeflist is empty!\n");
		return;
	}

	// 从首结点开始遍历
	while (PFront->next)
	{
		// 把队首的直接后继作为新的首节点
		PFront = PFront->next;

		// 输出队首的直接后继的数据域
		printf("%d->", PFront->data);

		// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
		if (PFront->next == NULL)
		{
			break;
		}
	}

	return;
}

    链式队列代码完整展示：

    /*******************************************************************
*
*	file name:	LinkQueue.c
*	author	 :  790557054@qq.com
*	date	 :  2024/04/26
*	function :  该案例是掌握链式队列的相关功能实现
* 	note	 :  None
*
*	CopyRight (c)  2023-2024   790557054@qq.com   All Right Reseverd 
*
* *****************************************************************/
#include <stdio.h>
#include <stdlib.h>

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

//构造记录链式队列LinkQueue各项参数(节点中存储数据 + 当前节点的直接后继地址)的结构体
typedef struct LinkQueue
{
	DataType_t            data;		//记录节点中存储数据
	struct LinkQueue     *next;		//记录当前节点的直接后继地址

}LkQueue_t;

/********************************************************************
*
*	name	 :	LkQueue_Create
*	function :  创建链式队列队首，并完成对队首的初始化
*	argument :  
*				none			
*	retval	 :  调用成功返回创建成功的队首地址
*	author	 :  790557054@qq.com
*	date	 :  2024/04/26
* 	note	 :  none
* 	
* *****************************************************************/
LkQueue_t *LkQueue_Create(void)
{
    //为队首申请堆空间，并完成错误处理
    LkQueue_t *Front = (LkQueue_t *)calloc(1, sizeof(LkQueue_t)); 
    if(Front == NULL)
    {
        perror("Calloc  memory for Front is Failed!");
        exit(-1);
    }

    //对队首初始化
    Front->next = NULL;

    //返回队首地址
    return Front; 
}
/********************************************************************
 *
 *	name	 :	LkQueue_NewNode
 *	function :  创建新的结点，并对新结点进行初始化（数据域 + 指针域）
 *	argument :
 *				@data 新节点需要存储的数据
 *
 *	retval	 :  调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
LkQueue_t *LkQueue_NewNode(DataType_t data)
{
	// 1.创建一个新结点并对新结点申请内存
	LkQueue_t *New = (LkQueue_t *)calloc(1, sizeof(LkQueue_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

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

	return New;
}
/********************************************************************
 *
 *	name	 :	LkQueue_EnQueue
 *	function :  将新节点尾插进链式队列中，即完成入队操作
 *	argument :
 *				@Front 链式队列的队首
 *				@data 新节点的数据域需要存储的数据
 *
 *	retval	 :  调用成功输出"插入成功"，否则输出"插入失败"
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
void LkQueue_EnQueue(LkQueue_t *Front, DataType_t data)
{
	// 定义一个循环指针变量PFront
	LkQueue_t *PFront = Front->next;
	// 调用函数创立一个新节点,并完成对应的错误处理
	LkQueue_t *New = LkQueue_NewNode(data);
	if (New == NULL)
	{
		printf("EnQueue is fail!\n");
		return;
	}

	// 进行判断，排除空链表的情况
	if (Front->next == NULL)
	{
		Front->next = New;
		printf("EnQueue of %d is success!\n", New->data);
		return;
	}

	// 先遍历得到尾结点在插入
	// 1.遍历至尾结点，将尾结点的next更换为新节点
	while (PFront->next != NULL)
	{
		PFront = PFront->next;
	}
	// 跳出while循环时，PFront极为尾节点;
	PFront->next = New;

	printf("EnQueue of %d is success!\n", New->data);

	return;
}
/********************************************************************
 *
 *	name	 :	LkQueue_DeQueue
 *	function :  删除链表的首节点，并保持链表的连续性
				即完成链式队列的出队操作
 *	argument :
 *				@Front 链式队列队首
 *
 *	retval	 :  调用成功后删除链式队列的首节点
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
void LkQueue_DeQueue(LkQueue_t *Front)
{
	// 对链式队列的队首的地址进行备份
	LkQueue_t *PFront = Front->next;

	// 判断当前链表是否为空，为空则直接退出
	if (Front->next == 	NULL)
	{
		printf("current linkequeue is empty!\n");
		return;
	}

	// 1.将首节点更换
	Front->next = Front->next->next;
	// 2.将备份与链表节点断开
	PFront->next = NULL;
	// 3.释放掉原首节点
	free(PFront);

	printf("DeQueue is success!\n");

	return;
}
/********************************************************************
 *
 *	name	 :	LkQueue_Print
 *	function :  遍历输出链式队列中所有节点的数据域
 *	argument :
 *				@Front 链式队列队首
 *
 *	retval	 :  调用成功输出链表中所有节点的数据域的值
 *	author	 :  790557054@qq.com
 *	date	 :  2024/04/26
 * 	note	 :  none
 *
 * *****************************************************************/
void LkQueue_Print(LkQueue_t *Front)
{
	// 对链式队列的队首的地址进行备份
	LkQueue_t *PFront = Front;

	// 判断当前链表是否为空，为空则直接退出
	if (Front->next == NULL)
	{
		printf("current linkeflist is empty!\n");
		return;
	}

	// 从首结点开始遍历
	while (PFront->next)
	{
		// 把队首的直接后继作为新的首节点
		PFront = PFront->next;

		// 输出队首的直接后继的数据域
		printf("%d->", PFront->data);

		// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
		if (PFront->next == NULL)
		{
			break;
		}
	}

	return;
}

int main()
{
	//创建链式队列的队首节点
	LkQueue_t *Front = LkQueue_Create();

	//入队：
	LkQueue_EnQueue(Front,10);
	LkQueue_EnQueue(Front,20);
	LkQueue_EnQueue(Front,30);
	printf("\n");

	//遍历输出
	LkQueue_Print(Front);
	printf("\n");


	//出队：
	LkQueue_DeQueue(Front);
	LkQueue_DeQueue(Front);
	printf("\n");

	//遍历输出
	LkQueue_Print(Front);
	printf("\n");

	LkQueue_DeQueue(Front);
	LkQueue_DeQueue(Front);


	return 0;
}

结果验证：

学习经验：

​ 队列和栈的代码实现都是基于顺序表与链表的，只是队列和栈有着自己不同的特点，前者是“先进先出”，后者是“后进先出”。甚至可以说这二者是顺序表和链表的简化版。但是算法没有绝对的优势，只有在特定环境下的适合性的高低。

热门相关：风流医圣   灭世魔帝   全民女神：重生腹黑千金   大金主，你别假正经了   最强神话帝皇