数据结构队列的应用举例(数据结构之队列)
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(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;
}
//长度 1
q->len ;
}
//元素出队列
intpop(Queue*q)
{
if(q->len>0)
{
//获取头节点的值
Node*h=q->head;
intval=h->val;
//没有其他元素重置为NULL
if(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->
5
10
4
11->12->13->14->
*/
从队列的特性中我们可以看到,队列主要用在先来先服务的场景中。生活中与之相关的就是 12306 的候补买票了以及一些排队的场景下,这种顺序服务的思想在一些消息队列当中也有体现。
相关的代码我已上传到 gitlab: https://gitlab.com/BitLegend/c-data-structure.git
此后的数据结构代码我都会上传在这个仓库中,需要的同学可以自己下载
感谢你能看到这里,欢迎关注我的 vx 公众号:BitLegend,学习更多的知识!我们下期再见!
,免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com