• 【数据结构】队列(Queue)实现详解


    🚩纸上得来终觉浅, 绝知此事要躬行。
    🌟主页:June-Frost
    🚀专栏:数据结构

    🔥该文章主要了解实现队列的相关操作。

    🌍 队列

    🔭概念

     队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 的特性。进行插入操作的一端称为队尾,进行删除操作的一端称为队头。


    🔭结构

     队列的底层实现如果使用数组,虽然插入操作很容易,但是在删除操作的时候就需要不断覆盖数据,效率不太高。所以,队列更适合使用单链表结构实现。对于尾插,只需要定义一个尾指针就可以规避遍历,而且队列的操作中也不需要去找前一个节点,所以单向链表就足以实现队列。


    🔭 应用场景

     队列的应用场景包括许多方面:

    • 公平性排队:
        队列主要用于确保所有的请求或等待者都能得到平等和公正的服务。例如,在银行或政府部门,所有人都需要按顺序办理业务,而不是先到先得或者根据个人地位或身份进行优先办理。通过队列,每个人都可以在公平的环境中办理业务,而不必担心由于其他因素导致的歧视或不公平待遇。此外,在需要分配资源或任务的情况下,队列也可以保证资源的公平分配和任务的合理安排。

    • BFS (广度优先遍历)
       BFS是一种用于遍历或搜索树或图的算法,它从根节点开始,沿着树的宽度遍历树的节点,直到找到目标节点或发现所有节点都被遍历过。在BFS过程中,队列用于存储待处理的节点,并按照先进先出的原则依次处理每个节点。这种算法在解决图论问题时非常常见,如找到两个节点之间的最短路径、检测图是否连通、搜索图中的环等。

    • 流量削锋
       在某些情况下,例如在大促活动或者突发流量洪流来袭时,下游系统可能无法处理所有的请求。通过队列,我们可以将请求放入队列中,让下游系统在有能力处理消息的时候再处理,避免下游订阅系统因突发流量崩溃。


    🌏 结构实现

     结构体的的声明:

    typedef int QDataType;
    //节点
    typedef struct QueueNode
    {
    	struct QueueNode* next;
    	QDataType data;
    }QNode;
    //指针
    typedef struct Queue
    {
    	QNode* head;
    	QNode* tail;
    	int size;//计数
    }Que;
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

     实现队列的时候,最好将两个指针放入一个结构体,这样有很多优点:① 实现队列操作的时候只需要传结构体的地址,可以规避二级指针;②可以减少传参的数量,代码更加简明;③此外如果在结构体中加入一个计数器,那么统计队列数据个数的时候就不需要遍历了。

    🔭 初始化 和 销毁

     销毁就是链表的释放

    //初始化
    void QueueInit(Que* pq)
    {
    	assert(pq);
    	pq->head = pq->tail = NULL;
    	pq->size = 0;
    }
    //销毁
    void QueueDestroy(Que* pq)
    {
    	assert(pq);
    	QNode* cur = pq->head;
    	while (cur)
    	{
    		QNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->tail = pq->head = NULL;
    	pq->size = 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    🔭 入队列

    //入队列
    void QueuePush(Que* pq, QDataType x)
    {
    	assert(pq);
    	QNode* node = (QNode*)malloc(sizeof(QNode));
    	if (node == NULL)
    	{
    		perror("malloc fail");
    		exit(-1);
    	}
    	node->data = x;
    	node->next = NULL;
    	//第一个节点
    	if (pq->tail == NULL)
    	{
    		pq->head = pq->tail = node;
    	}
    	//不是第一个节点
    	else
    	{
    		pq->tail->next = node;
    		pq->tail = node;
    	}
    	pq->size++;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

     入队列要注意分情况:如果是第一个节点,头指针和尾指针都需要被赋值,如果不是第一个,只需要通过尾指针插入节点并更新尾指针。

    🔭 出队列

    //出队列
    void QueuePop(Que* pq)
    {
    	assert(pq && pq->size > 0);
    
    	QNode* next = pq->head->next;
    	if (next == NULL)
    	{
    		free(pq->head);
    		pq->tail = NULL;
    		pq->head = NULL;
    	}
    	else
    	{
    		free(pq->head);
    		pq->head = next;
    	}
    	pq->size--;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    在这里插入图片描述

    🔭 取队头和队尾数据

    //取队头
    QDataType QueueFront(Que* pq)
    {
    	assert(pq && pq->size>0);
    
    	return pq->head->data;
    }
    
    //取队尾
    QDataType QueueBack(Que* pq)
    {
    	assert(pq && pq->size > 0);
    
    	return pq->tail->data;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    🔭判空和数据个数

    //判空
    bool QueueEmpty(Que* pq)
    {
    	assert(pq);
    
    	return pq->head == NULL;
    }
    
    //节点个数
    int QueueSize(Que* pq)
    {
    	assert(pq);
    
    	return pq->size;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

     由于结构体定义了计数器,在插入和删除时就在不断更新个数值,规避了遍历求解个数的方式。

    🔭接口测试

     通过这样的逻辑就实现了先进先出的特性。

    void test()
    {
    	Que q;
    	QueueInit(&q);
    	QueuePush(&q, 1);
    	QueuePush(&q, 2);
    	QueuePush(&q, 3);
    	QueuePush(&q, 4);
    	while (!QueueEmpty(&q))
    	{
    		printf("%d ", QueueFront(&q));
    		QueuePop(&q);
    	}
    	QueueDestroy(&q);
    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    ❤️ 结语

     文章到这里就结束了,如果对你有帮助,你的点赞将会是我的最大动力,如果大家有什么问题或者不同的见解,欢迎大家的留言~

  • 相关阅读:
    STM32F4-TFT-SPI时序逻辑分析仪调试记录
    ctfshow 萌新赛 给她
    js的变量赋值的问题
    PMP每日一练 | 考试不迷路-12.1(包含敏捷+多选)
    spark分布式计算框架
    HK2学习之基础知识
    驱动文件讲解
    基于SpringBoot+Vue实现的党校培训管理系统源代码+数据库
    PMP真的有用吗?
    folium 增加搜索、经纬度弹出,字段弹出的方法
  • 原文地址:https://blog.csdn.net/m0_75219751/article/details/133751170