文章目录队列1.顺序队列(循环)前置知识循环队列相关1.入队2.出队头文件部分实现1.初始化循环队列2.入队3.出队测试案例main函数输出结果2.链式队列前置知识1.入队2.出队头文件部分实现1.创建链式队列2.释放链式队列3.入队4.出队测试案例main函数输出结果输出结果队列1.顺序队列(循环)前置知识一种先进先出的结构​​ 先简述下为什么要写循环队列 -----主要是为了解决“假溢出”就是rear指到最后已经满了 但是同时前面又出队了 这样还有位置但是进不去循环队列相关一个问题 若我们规定空队列时是frontrear 当队列满时呢?也是frontrear???**这里我采用浪费一个空间的方法浪费队列的首空间(也就是队列首个空间不放元素)由于rear可能比front大,也可能比front小,所以在他们相差一个位置的时候就是满的情况 也可能是相差一整圈,也是满的情况(这种是队列中没有一个出队的)这里我们规定队列的最大空间为MaxQueueSize1.frontrear//队列为空2.(rear1)%MaxQueueSizefront//队列为满1.入队1.判断队列是否已满 2.移动rear指针 3.放值判断队列是否已满——if ( ( queue-rear 1 ) % MaxQueueSize queue-front )移动rear指针 ——queue-rear ( queue-rear 1 ) % MaxQueueSize;放值 ——queue-data[queue-rear] e;1.判断队列是否已满 2.移动rear指针 3.放值if((queue-rear1)%MaxQueueSizequeue-front){fprintf(stderr,Queue Full!\n);return-1;}queue-rear(queue-rear1)%MaxQueueSize;queue-data[queue-rear]e;2.出队1.判断队列是否为空 2.移动front指针判断队列是否为空——if (queue-rear queue-front)移动front指针 ——queue-front (queue-front 1) % MaxQueueSize;1.判断队列是否为空 2.移动front指针if(queue-rearqueue-front){fprintf(stderr,Queue Empty!\n);return-1;}queue-front(queue-front1)%MaxQueueSize;头文件部分typedefintElement;#defineMaxQueueSize5typedefstruct{Element data[MaxQueueSize];intfront;intrear;}ArrayQueue;//1.初始化循环队列voidinitArrayQueue(ArrayQueue*queue);//2.入队intenArrayQueue(ArrayQueue*queue,Element e);//3.出队intdeArrayQueue(ArrayQueue*queue,Element*e);实现1.初始化循环队列//1.初始化循环队列voidinitArrayQueue(ArrayQueue*queue){//初始化memset(stack-data,0,sizeof(stack-data));queue-frontqueue-rear0;}2.入队intenArrayQueue(ArrayQueue*queue,Element e){//入队相关代码//1.判断队列是否已满if((queue-rear1)%MaxQueueSizequeue-front){fprintf(stderr,Queue Full!\n);return-1;}//2.移动rear指针queue-rear(queue-rear1)%MaxQueueSize;//3.放值queue-data[queue-rear]e;return0;}3.出队intdeArrayQueue(ArrayQueue*queue,Element*e)//用e返回队头元素{//出队相关代码//1.判断队列是否为空if(queue-rearqueue-front){fprintf(stderr,Queue Empty!\n);return-1;}//2.移动front指针queue-front(queue-front1)%MaxQueueSize;//通过指针修改外部实参 带出队首元素*equeue-data[queue-front];return0;}测试案例main函数voidtest03(){ArrayQueue stu1;//初始化队列initArrayQueue(stu1);//循环入队5个元素for(inti0;iMaxQueueSize-1;i){enArrayQueue(stu1,i100);}//队列已满 入队失败enArrayQueue(stu1,520);//出队 并查看队列中元素Element x1;while(deArrayQueue(stu1,x1)!-1){printf(%d\t,x1);}printf(\n);}输出结果Queue Full!619620621622Queue Empty!2.链式队列前置知识链式队列其实就是单链表 直播不过它只能头进尾出而已先看下队列的样子吧1.入队这个该往rear的后面插 即尾插 为了方便出队(如果头插了 出队的时候front也不能往前走啊) 1.创建新结点 2.更新新节点 3.更新队尾的next指针 连接新节点 4.更新队尾指针创建新节点 —— *QueNodenew_node malloc(sizeof(QueNode));更新新节点 ——new_node-next NULL;更新队尾的next指针 连接新节点 ------queue-rear-next new_node;更新队尾指针 ——queue-rear new_node;1.创建新结点 2.更新新节点 3.更新队尾的next指针 连接新节点 4.更新队尾指针QueNode*new_nodemalloc(sizeof(QueNode));new_node-nextNULL;queue-rear-nextnew_node;queue-rearnew_node;2.出队1.引入辅助指针tmp备份待删除位置 2.修改队头指针 跳过待删除节点 重新衔接队列 3.删除tmp引入辅助指针tmp备份待删除位置 ------ *QueNodetmp queue-front;修改队头指针 跳过待删除节点 重新衔接队列 ------queue-front tmp-next;删除tmp ——free(tmp);1.引入辅助指针tmp备份待删除位置 2.修改队头指针 跳过待删除节点 重新衔接队列 3.删除tmp​QueNode*tmpqueue-front;queue-fronttmp-next;free(tmp);头文件部分typedefintElement;// 链式队列的节点typedefstruct_node{Element data;struct_node*next;}QueNode;// 链式队列的头节点typedefstruct{QueNode*rear;//队列头指针QueNode*front;//队列尾指针intcnt;//用来计数队列中的节点数量 这个其实写不写都可以constchar*name;//链式队列名字 写不写都可以 写着玩}LinkQueue;//1.创建链式队列LinkQueue*createLinkQueue(constchar*name);//2.释放链式队列voidreleaseLinkQueue(LinkQueue*queue);//3.入队intenLinkQueue(LinkQueue*queue,Element e);//4.出队intdeLinkQueue(LinkQueue*queue,Element*e);实现1.创建链式队列LinkQueue*createLinkQueue(constchar*name){//创建链式队列LinkQueue*queuemalloc(sizeof(LinkQueue));if(queueNULL){fprintf(stderr,createLinkQueue malloc failed!\n);returnNULL;}//初始化queue-namename;queue-frontqueue-rearNULL;queue-cnt0;//返回该链式队列returnqueue;}2.释放链式队列voidreleaseLinkQueue(LinkQueue*queue){if(queue){QueNode*tmp;while(queue-front){//出队相关代码tmpqueue-front;queue-fronttmp-next;//不断向后遍历队列中节点free(tmp);//减少队列中节点数量queue-cnt--;}printf(queue have %d node!\n,queue-cnt);//最后释放队列free(queue);}}3.入队// 先有新节点新节点应该rear的next方向插入便于front的删除intenLinkQueue(LinkQueue*queue,Element e){QueNode*nodemalloc(sizeof(QueNode));if(nodeNULL){fprintf(stderr,enLinkQueue new_node malloc failed!\n);return-1;}//入队相关代码node-datae;node-nextNULL;if(queue-rear)//队列中元素不为空时{queue-rear-nextnode;queue-rearnode;}else//当队列中元素为空时{queue-rearqueue-frontnode;}//增加链式队列中节点数量queue-cnt;return0;}4.出队intdeLinkQueue(LinkQueue*queue,Element*e)//用e返回队头元素{//判断队列是否为空if(queue-frontNULL){fprintf(stderr,\tqueue empty!\n);return-1;}//通过指针修改外部实参 带出队首元素*equeue-front-data;//出队相关代码QueNode*tmpqueue-front;queue-fronttmp-next;free(tmp);//减少队列中节点数量queue-cnt--;if(queue-frontNULL){// 队列中已经没有元素queue-rearNULL;//尾指针置空}return0;}测试案例main函数voidtest04(){//创建链式队列LinkQueue*queuecreatLinkkQueue(jj);if(queueNULL){return;}//循环入队5个元素for(inti0;i5;i){enLinkQueue(queue,i619);}Element x1;printf(%s Queue %d show:,queue-name,queue-cnt);//出队 队列中所有元素while(deLinkQueue(queue,x1)!-1){printf(\t%d,x1);}printf(\n);//释放该队列releaseLinkQueue(queue);}intmain(){test04();return0;}输出结果jj Queue5show:619620621622623queue empty!queue have0node!​ 嘻嘻嘻嘻 队列部分到此结束​ (有错误欢迎指出) (疑问也是)❤️❤️至此 队列小节结束 持续更新中… …输出结果jj Queue5show:619620621622623queue empty!queue have0node!​ 嘻嘻嘻嘻 队列部分到此结束​ (有错误欢迎指出) (疑问也是)❤️❤️至此 队列小节结束 持续更新中… …