数据结构队列的应用举例数据结构之队列

导读队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性....

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表进行插入操作的端称为队尾，进行删除操作的端称为队头队列的特性总结为：先进先出 这中特性在日常中类似于排队，先来的先进行服务，下面我们就来说一说关于数据结构队列的应用举例?我们一起去了解并探讨一下这个问题吧!

数据结构队列的应用举例

数据结构之队列什么是队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的特性总结为：先进先出。 这中特性在日常中类似于排队，先来的先进行服务！

队列的实现

我们使用链表实现队列，一个头节点和一个为节点表示队列的头部和尾部。出队列和入队列的时间复杂度为 O(1)。空间复杂度为 O(n)

单向队列

队列是只允许在一端进行插入操作,在另外一段进行删除操作的线性表，队列不允许在中间部位进行操作

循环队列

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

双向队列

双端队列是一种两端都可以 删除元素和追加元素的线性结构。双端队列比普通的队列更加灵活。双端队列可以用双向链表实现。

单向队列的实现方式:

节点定义

#include<stdio.h>#include<stdlib.h>typedefstructNode{//节点的值intval;//节点的在一个节点structNode*next;}Node;typedefstructQueue{/*data*///队列的头节点Node*head;//队列的尾节点Node*tail;//队列的元素数量intlen;}Queue;//初始化队列Queue*init(){//申请空间Queue*q=malloc(sizeof(Queue));//初始化成员属性q->head=q->tail=NULL;q->len=0;returnq;}

入队操作

//元素入队列voidpush(Queue*q,intval){//申请空间Node*node=malloc(sizeof(Node));node->val=val;node->next=NULL;//判断队列是不是为空if(q->len==0){//直接赋值q->head=q->tail=node;}else{//将元素添加至队列末尾q->tail->next=node;q->tail=node;}//长度 1q->len ;}

出队操作

//元素出队列intpop(Queue*q){if(q->len>0){//获取头节点的值Node*h=q->head;intval=h->val;//没有其他元素重置为NULLif(h->next==NULL){q->head=q->tail=NULL;}else{q->head=h->next;}//释放节点空间free(h);q->len--;returnval;}return0xFFFFFF;}

其他操作

//返回队列的长度intsize(Queue*q){if(q==NULL){return-1;}returnq->len;}voidprintQueue(Queue*q){if(q!=NULL){Node*h=q->head;while(h!=NULL){printf("%d->",h->val);h=h->next;}printf("\n");}}//销毁队列voiddestory(Queue*q){if(q!=NULL){//逐个释放节点的元素Node*h=q->tail;while(h!=NULL){free(h);h=h->next;}//释放队列free(q);}}

测试结果

intmain(){Queue*queue=init();push(queue,10);push(queue,11);push(queue,12);push(queue,13);push(queue,14);printQueue(queue);printf("%d\n",size(queue));printf("%d\n",pop(queue));printf("%d\n",size(queue));printQueue(queue);destory(queue);return0;}/*10->11->12->13->14->510411->12->13->14->*/

队列的应用

从队列的特性中我们可以看到，队列主要用在先来先服务的场景中。生活中与之相关的就是 12306 的候补买票了以及一些排队的场景下，这种顺序服务的思想在一些消息队列当中也有体现。

相关的代码我已上传到 gitlab: https://gitlab.com/BitLegend/c-data-structure.git

此后的数据结构代码我都会上传在这个仓库中，需要的同学可以自己下载

感谢你能看到这里，欢迎关注我的 vx 公众号：BitLegend，学习更多的知识！我们下期再见！