当前位置:鱼C工作室 >数据结构和算法 > 查看文章

栈和队列8 – 数据结构和算法30

栈和队列8

 

让编程改变世界

Change the world by program


 

队列的顺序存储结构

 

为什么小甲鱼上节课说队列的实现上我们更愿意用链式存储结构来存储?

我们先按照应有的思路来考虑下如何构造队列的顺序存储结构,然后发掘都遇到了什么麻烦。

我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的存储单元,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端则是队头。

 

No Pic You Say a J8

 

队列的顺序存储结构

入队列操作其实就是在队尾追加一个元素,不需要任何移动,时间复杂度为O(1)。

出队列则不同,因为我们已经架设下标为0的位置是队列的队头,因此每次出队列操作所有元素都要向前移动。

 

队列的顺序存储结构

在现实中也是如此,一群人在排队买火车票,前边的人买好了离开,后面的人就要全部向前一步补上空位。

可是我们研究数据结构和算法的一个根本目的就是要想方设法提高我们的程序的效率,按刚才的方式,出队列的时间复杂度是O(n),效率大打折扣!

如果我们不去限制队头一定要在下标为0的位置,那么出队列的操作就不需要移动全体元素。

 

队列的顺序存储结构

但是这样也会出现一些问题,例如按下边的情形继续入队列,就会出现数组越界的错误。

 

队列的顺序存储结构

可事实上我们有0和1两个下标还空着,这叫假溢出。

 

循环队列定义

 

我们再想想,要解决假溢出的办法就是如果后面满了,就再从头开始,也就是头尾相接的循环。

循环队列它的容量是固定的,并且它的队头和队尾指针都可以随着元素入出队列而发生改变,这样循环队列逻辑上就好像是一个环形存储空间。

 

但要注意的是,在实际的内存当中,不可能有真正的环形存储区,我们只是用顺序表模拟出来的逻辑上的循环。

我们通过一段动画片来加深印象吧!

 

循环队列

 

于是我们发觉了,似乎循环队列的实现只需要灵活改变front和rear指针即可。

也就是让front或rear指针不断加1,即时超出了地址范围,也会自动从头开始。我们可以采取取模运算处理:

(rear+1) % QueueSize

(front+1) % QueueSize

 

取模就是取余数的意思,他取到的值永远不会大于除数,大家结合实例拿张纸算一算就知道啦~

分页阅读: 1 2 3 下一页
为您推荐

报歉!评论已关闭.