如图,进行入队(push)操作的时候,我们首先需要特判一下队列是否为空,如果队列为空的话,需要将头指针和尾指针一同指向第一个结点,即front=n;rear=n。
当如果队列不为空的时候,我们只需要将尾结点向后移动,通过不断移动next指针指向新的结点构成队列即可。
其代码可以表示为:
//入队操作 void push(queue *q,int data){ node *n =init_node(); n->data=data; n->next=NULL; //采用尾插入法 //if(q->rear==NULL){ //使用此方法也可以 if(empty(q)){ q->front=n; q->rear=n; }else{ q->rear->next=n; //n成为当前尾结点的下一结点 q->rear=n; //让尾指针指向n } }
出队(pop)操作,是指在队列不为空的情况下(请注意一定要进行队列判空的操作),进行一个判断,如图,如果队列只有一个元素了(即头尾指针均指向了同一个结点),直接将头尾两指针制空(NULL)并释放这一个结点即可。
如图,当队列含有二以上个元素时,我们需要将队列的头指针指向头指针当前指向的下一个元素并释放掉当前元素即可。
其代码可以表示为:
//出队操作 void pop(queue *q){ node *n=q->front; if(empty(q)){ return ; //此时队列为空,直接返回函数结束 } if(q->front==q->rear){ q->front=NULL; //只有一个元素时直接将两端指向制空即可 q->rear=NULL; free(n); //记得归还内存空间 }else{ q->front=q->front->next; free(n); } }
打印队列的全部元素是在队列不为空的情况下,通过结点的next指向依次遍历并输出元素既可以。
其代码可以表示为
//打印队列元素 void print_queue(queue *q){ node *n = init_node(); n=q->front; if(empty(q)){ return ; //此时队列为空,直接返回函数结束 } while (n!=NULL){ printf("%d\t",n->data); n=n->next; } printf("\n"); //记得换行 }
遍历操作还有很多变形,比如说进行计算队列中含有多少元素。
int calac(queue *q){ node *n = init_node(); n=q->front; int cnt=0; //计数器设计 if(empty(q)){ return 0; //此时队列为空,直接返回函数结束 } while (n!=NULL) { n=n->next; cnt++; } return cnt; }
#include<stdio.h> #include<stdlib.h> //结点定义 typedef struct node{ int data; struct node *next; }node; //队列定义,队首指针和队尾指针 typedef struct queue{ node *front; node *rear; }queue; //初始化结点 node *init_node(){ node *n=(node*)malloc(sizeof(node)); if(n==NULL){ //建立失败,退出 exit(0); } return n; } //初始化队列 queue *init_queue(){ queue *q=(queue*)malloc(sizeof(queue)); if(q==NULL){ //建立失败,退出 exit(0); } //头尾结点均赋值NULL q->front=NULL; q->rear=NULL; return q; } //队列判空 int empty(queue *q){ if(q->front==NULL){ return 1; //1--表示真,说明队列非空 }else{ return 0; //0--表示假,说明队列为空 } } //入队操作 void push(queue *q,int data){ node *n =init_node(); n->data=data; n->next=NULL; //采用尾插入法 //if(q->rear==NULL){ if(empty(q)){ q->front=n; q->rear=n; }else{ q->rear->next=n; //n成为当前尾结点的下一结点 q->rear=n; //让尾指针指向n } } //出队操作 void pop(queue *q){ node *n=q->front; if(empty(q)){ return ; //此时队列为空,直接返回函数结束 } if(q->front==q->rear){ q->front=NULL; //只有一个元素时直接将两端指向制空即可 q->rear=NULL; free(n); //记得归还内存空间 }else{ q->front=q->front->next; free(n); } } //打印队列元素 void print_queue(queue *q){ node *n = init_node(); n=q->front; if(empty(q)){ return ; //此时队列为空,直接返回函数结束 } while (n!=NULL) { printf("%d\t",n->data); n=n->next; } printf("\n"); //记得换行 } //主函数调用,这里只是简单介绍用法 int main(){ queue *q=init_queue(); ///////////////入队操作///////////////// printf("入队\n"); for(int i=1;i<=5;i++){ push(q,i); print_queue(q); } ///////////////出队操作///////////////// printf("出队\n"); for(int i=1;i<=5;i++){ pop(q); print_queue(q); } return 0; }
对于基本的操作,可以同链表的题目测试,自定义一些数据集来测试,这里不再提供直接的问题链接,其次可以试着去做一些基本的队列操作的题目,如:
接着,队列的操作会在很多的算法设计中使用到,尤其是BFS(广度优先搜索)算法的设计和一些图论的算法设计几乎无法离开各种类型的队列的灵活使用。
对于本样例代码,同学们可以试将队列元素数量设计入结构体中,这样每次询问队列中含有多少元素时就不必在进行依次遍历出元素数量而直接出答案了。
1895 | 蓝桥杯算法提高VIP-队列操作 |
本文固定URL:https://www.dotcpp.com/course/106
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程