首页 / 算法 / 数据结构与算法四:队列
数据结构与算法四:队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法四:队列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2384字,纯文字阅读大概需要4分钟。
内容图文
![数据结构与算法四:队列](/upload/InfoBanner/zyjiaocheng/657/2b7d80b00dfe4f8591bb6536a4c4177a.jpg)
队列顾名思义就是排队一样,先来的先出去,所有性质就跟排队一样,是一模一样,所有你想得到关于排队有的性质,队列都有,那么队列的应用实际上在操作系统上是非常丰富的,至于为什么我每次都要说一说操作系统是因为我想阐述为什么这些数据结构很重要,即使我们出去水平不够找不到很核心的工作,每天可能天天写业务代码(基本上就是调用接口,写写增删改查什么的),基本上不可能接触到这些东西,但还是要努力的学这些东西的最直观的意义是什么。
在操作系统中,所有的调度,存储都是基于这些数据结构,好了,我们开始谈一谈队列在操作系统中的应用吧,首先,调度算法,你能想到的各个方面的调度都少不了队列,FIFO方式就是直接利用队列表现得,还有什么多级反馈队列,等等,简单地说,队列就是为了也是保证记录下时间或者某种顺序得数据存储结构
接下来,我们开始实现吧:
那么,我们需要依托什么基本结构去实现呢,数组?,我们仔细回想一下,每一次新的都是插入在最后面的,而每一次被服务得都是在最前面的,那么每服务一次,最前面就会被空出来,然后我需要挪动整体往前一格,不然就浪费内存了,故这显然是不科学得,因此,我们在处理队列得时候,一般都会选择循环数组和万能得链表
首先是基于简单循环数组的实现:
struct queue{ int front,rear; int capacity; int *array; }; struct queue *q(int size){ struct queue *q = new(struct queue); if(!q){ cout<<"could not create the queue"<<endl; return NULL; } q->capacity = size; q->front = q->rear =-1; q->array = new(q->capacity*sizeof(int)); if(!q->array) return NULL; return q; } int isEmpty(struct queue *q){ return(q->front == -1); } int isFull(struct queue *q){ return((q->rear+1)%q->capacity === q->front); } void inqueue(struct queue *q,int data) { if(isFull(q)) cout<<"is full"<<endl; else{ q->rear = (q->rear+1)%q->capacity; q->array[q->rear]=data; if(q->front==-1) q->front = q->rear; } } int outqueue(struct queue *q){ int data = 0; if(isEmpty(q)){ cout<<"is Empty,colud not out the element"<<endl; return 0; } else{ q->array[q->front]; if(q->front == q->rear) q->front = q->rear =-1; else q->front = (q->front+1)%q->capacity; } return data; } void deletequeue(struct queue *q){ if(q){ if(q->array) free(q->array); free(q); } } int size(){ return(q->capacity - q->front + q->rear + 1)%q->capacity; }
同时为了使队列使可以变化的,我们同样可以用动态数组写,说白了就是将数组变大,然后复制过来,同样的,我们也是每一次达到溢出的时候,直接将数组翻倍。
初次之外,我们还可以用链表加以实现,同样的,这个玩意就是两边加个指针就好了,其他操作就是链表的操作。
最后,其实每一个数据结构都不是难得,难的在于你如何将他变化成你思考一个问题的基础依据,并加以考量。
内容总结
以上是互联网集市为您收集整理的数据结构与算法四:队列全部内容,希望文章能够帮你解决数据结构与算法四:队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。