网站建设大数据电商平台管理系统

网站建设大数据,电商平台管理系统,安宁网站建设熊掌,开发网站的流程步骤文章目录前言 #x1f680;一、队列的概念 #x1f4a1;1. 什么是队列#xff1f;2. 队列有什么用#xff1f;二、队列的模拟实现 #x1f6e0;️1. 选型#xff1a;数组 vs 链表#xff1f;2. 代码实现2.1 结构体定义2.2 初始化2.3 入队 (Push)2.4 出队 (Pop)2.5 获取队…文章目录前言 一、队列的概念 1. 什么是队列2. 队列有什么用二、队列的模拟实现 ️1. 选型数组 vs 链表2. 代码实现2.1 结构体定义2.2 初始化2.3 入队 (Push)2.4 出队 (Pop)2.5 获取队头 队尾数据2.6 获取长度 判空2.7 销毁队列三、代码测试 结语 前言 哈喽各位小伙伴欢迎回到我的数据结构系列专栏这是我们征服数据结构之路的第三站。在前两篇中我们已经拿下了链表和栈还没看过的同学强烈建议先补个票基础打牢才能飞得更高哦~ 链接我放在下面啦。https://blog.csdn.net/S_tarfish/article/details/155815933?fromshareblogdetailsharetypeblogdetailsharerId155815933sharereferPCsharesourceS_tarfishsharefromfrom_linkhttps://blog.csdn.net/S_tarfish/article/details/155418909?fromshareblogdetailsharetypeblogdetailsharerId155418909sharereferPCsharesourceS_tarfishsharefromfrom_link虽说前两篇的内容可能还略显青涩但我已经在计划后续的“装修”工程了敬请期待好了闲话少叙今天我们要解锁一个非常经典且常用的数据结构——队列Queue。准备好了吗让我们开始吧一、队列的概念 1. 什么是队列队列Queue是一种特殊的线性表。它的特殊之处在于它对数据的访问进行了严格的限制只允许在表的一端进行插入数据而在另一端进行删除数据。这就好比我们在食堂排队打饭入队Push新来的人只能站在队尾。出队Pop只有排在队头的人才能先打到饭离开。这种操作特性被称为FIFO (First In First Out)即先进先出。队尾Rear/Back进行插入操作的一端。队头Front/Head进行删除操作的一端。2. 队列有什么用你可能会问“费劲限制这么多图啥呢” 其实队列在计算机科学和日常生活中的应用简直不要太多保持公平性这是最直观的作用。比如银行的叫号系统、医院的挂号系统、餐馆的排队小程序本质上都是队列。先抽号的先服务确保了公平。广度优先遍历BFS在图论和树的算法中队列是实现 BFS 的核心辅助结构。比如 QQ/微信 的“好友推荐”功能推荐你好友的好友或者寻找迷宫的最短路径底层往往都要用到队列。缓冲区比如我们在键盘上打字如果 CPU 忙不过来按键信息会被暂时存在一个队列里保证输入的顺序不会乱。二、队列的模拟实现 ️1. 选型数组 vs 链表在实现队列之前我们面临一个选择是用数组顺序表还是链表来实现如果用数组入队在数组尾部很简单但出队删除头部元素需要将后续所有元素向前移动时间复杂度是O(N)效率较低。如果用链表入队即链表的尾插如果我们记录了尾节点指针复杂度是O(1)。出队即链表的头删直接释放第一个节点即可复杂度也是O(1)。结论为了追求极致的效率我们选择使用链表来实现队列且为了操作方便我们需要维护一个指向队头的指针和一个指向队尾的指针。2. 代码实现2.1 结构体定义为了方便管理我们定义两个结构体Qnode表示链表中的每一个节点。Queue用来维护队列的整体状态头指针、尾指针、元素个数。#includestdio.h#includestdlib.h#includeassert.h#includestdbool.h//定义队列元素的数据类型方便后续修改typedefintQDataType;// 1. 定义队列节点的结构typedefstructQueuenode{QDataType val;structQueuenode*next;}Qnode;// 2. 定义队列本身的结构typedefstructQueue{// 把头和尾的指针封装在一起队列只能在头尾两端操作// 这样能简化函数参数不必每次都传递两个指针Qnode*phead;// 指向队头用于出队Qnode*ptail;// 指向队尾用于入队intsize;// 增加size成员可以O(1)时间复杂度获取队列长度}Queue;2.2 初始化养成好习惯使用前先初始化。voidQueueInit(Queue*pq){assert(pq);// 保证传进来的结构体指针有效// 初始状态下队列为空头尾指针均置空pq-pheadNULL;pq-ptailNULL;pq-size0;}2.3 入队 (Push)入队操作实际上就是链表的尾插。这里需要注意处理队列为空的特殊情况。voidQueuePush(Queue*pq,QDataType x){assert(pq);// 1. 既然是插入首先要开辟新节点Qnode*newnode(Qnode*)malloc(sizeof(Qnode));if(newnodeNULL){perror(malloc fail);return;}newnode-valx;newnode-nextNULL;// 新节点将作为尾节点next必然指向NULL// 2. 链接节点分类讨论// 情况A如果你是第一个进队的元素if(pq-pheadNULL){// 此时头和尾都是你pq-pheadpq-ptailnewnode;}// 情况B队列里已经有兄弟了else{// 旧的尾节点指向新节点pq-ptail-nextnewnode;// 更新尾指针指向新的节点pq-ptailnewnode;}// 3. 别忘了计数pq-size;}2.4 出队 (Pop)出队操作实际上就是链表的头删。⚠️注意这里有一个很容易踩的坑当队列只剩下一个节点时删掉它后不仅phead要变空ptail也要置空否则ptail就变成野指针了。voidQueuePop(Queue*pq){assert(pq);assert(pq-size!0);// 队列为空时不能删除断言报错// 1. 保存下一个节点的地址防止丢失Qnode*nextpq-phead-next;// 2. 释放当前的头节点free(pq-phead);// 3. 更新头指针pq-pheadnext;// 4. 【关键判断】如果删完后队列空了// 此时 phead 已经变成了 NULL但 ptail 还指着刚才被 free 掉的空间if(pq-pheadNULL){pq-ptailNULL;// 必须手动置空防止 ptail 变成野指针}// 5. 计数减一pq-size--;}2.5 获取队头 队尾数据// 取队头数据QDataTypeQueueFront(Queue*pq){assert(pq);assert(pq-size!0);// 队列不能为空returnpq-phead-val;}// 取队尾数据QDataTypeQueueBack(Queue*pq){assert(pq);assert(pq-size!0);returnpq-ptail-val;}2.6 获取长度 判空因为我们在结构体中维护了size这两个操作非常简单高效。// 获取队列长度intQueueSize(Queue*pq){assert(pq);returnpq-size;}// 判空size为0即为空boolEmpty(Queue*pq){assert(pq);returnpq-size0;}2.7 销毁队列有始有终申请的内存记得释放。voidQueueDestroy(Queue*pq){assert(pq);Qnode*curpq-phead;while(cur){// 记录下一个以便能继续往后走Qnode*nextcur-next;free(cur);curnext;}// 善后工作pq-pheadpq-ptailNULL;pq-size0;}三、代码测试 逻辑写得再好跑起来才是硬道理。让我们写个main函数测试一下我们的队列是否符合“先进先出”的特性。#includeiostreamusingnamespacestd;// 假设上面的函数声明在 queue.h 中实现在 queue.c 中// 这里为了演示方便直接包含// #include queue.hintmain(){Queue q1;QueueInit(q1);// 1. 模拟入队1 2 3 4printf(入队顺序: 1 - 2 - 3 - 4\n);QueuePush(q1,1);QueuePush(q1,2);QueuePush(q1,3);QueuePush(q1,4);printf(开始出队及获取信息:\n);// 2. 只要队列不为空就打印队头元素并出队while(!Empty(q1)){// 打印格式队头元素 队尾元素 当前长度coutFront:QueueFront(q1) | Back:QueueBack(q1) | Size:QueueSize(q1)endl;QueuePop(q1);}QueueDestroy(q1);return0;}运行结果如下结果分析我们可以清晰地看到第一行Front是 1Size是 4。Pop一次后第二行Front变成了 2Size变成了 3。这完美验证了队列FIFO先进先出的特性。结语 到这里关于队列的基础知识和链式实现就讲完啦相比于顺序表队列在特定场景下的作用不可替代。如果你觉得这篇文章对你有帮助不妨点个赞支持一下这对我通过持续输出高质量内容非常重要后续我会更新更复杂的二叉树等内容关注不迷路哦~我们下期见