链式队列

队列

原理介绍:

​ 队列(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;
    }
    

结果验证:

学习经验:

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

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