最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 上一节问题分析

    上一节末尾对时间复杂度的分析中,我们可以看出数组队列是有一定程度缺陷的,关键问题就是在于出队这个操作,它的时间复杂度是O(n)级别的,这一小节我们再来看一下这个问题应该怎么解决。

    假设该数组队列可容纳元素是八个,现在已经有五个元素,并且要出队了,也就是要删除队首的元素。

    根据队列的定义,假设队首在左侧,a这个元素就会出队。

    出队之后,所有其他元素都必须向前挪一个单位,之后size–。

    这就是数组底层实现删除一个队首的过程,由于删除后,剩余元素都要向前移动一位,所以时间复杂度是O(n)。

    基于以上分析,相信大家不难想象,如果我们删完了a这个元素之后,剩余元素可不可以不挪一个位置呢?

    当然可以啊!基于这样的想法,我们可以在数组中先记录一下队首是谁。

    比如现在这个数组中,虽然第0个元素是空的,其实队首是存放在索引为1的位置,我们叫它front。

    同时,队尾和之前的size一样,指的是下一次有一个新的元素入队应该存储的位置。

    因此,我们只需要修改一下front的指向就好了。

    准确的说,就是只要front++就可以了,而不需要所有的元素全都向前移动一个单位。

    基于上面的想法,就有了循环队列这样一种队列实现方式。

    循环队列

    在初始的情况下,队列中没有任何元素,front和tail都指向0。

    这里要注意,front本来应该指向数组的第一个元素,而tail指向数组中最后一个元素的后一个位置。

    但是当队列整体为空的时候,front只好和tail指在一起,也就是说:front和tail相等的时候,意味着队列为空。

    接下来,如果有一个元素a入队了,此时我们只需要维护tail也就是队尾就好了。

    tail指向下一个元素再入队的时候的位置,以此类推……

    此时队列里有五个元素,如果我们要出队一个元素怎么办呢?

    非常简单,front指向的是队首元素,此时front指向a,a出队,front向后挪一个位置。

    这种情况下,出队操作不再需要所有的元素都挪动了,只需要front的指向改变就可以了。

    所以变成了一个O(1)的操作,依次类推……

    如果又要有新的元素入队了,如下图所示,这种情况下,tail就不能++了。

    可是大家可以看到,由于挪出前面的数组之后,空间没有被挤掉,所以相当于对于数组来说,前面有可能还有可以利用的空间,这就是循环队列的来由。

    此时可以理解成,其实可以把数组看成是一个环。

    现在这个数组中,一共可以容纳八个元素,对应的索引是0~7。

    7之后的索引其实是0,tail++更准确的说应该是当前的索引加1再%整个数组的长度。

    换句话说,7是怎么计算到0的呢?

    是7+1=8,对8求余等于0,所以在0这个位置还能放新的元素。

    这里要注意,只剩下一个空间了,还能放下一个元素吗?

    假如再有一个元素入队了放在1这个位置,tail++,此时tail变成了2,front也是2,这种情况下,front又等于tail了。

    可此时队列不为空,所以我们应该重新定义一下什么情况下队列为满:如果(tail+1)%c==front,即为队列满。

    换句话说,tail指向的位置就是下次有元素入队应该放入的位置,一旦有新元素放入后,tail就要加一,但是加一后就和front重叠了,就说明队列满了。

    也就是说,我们是有意识的浪费了一个空间。

    代码演示

    新建一个循环队列实现代码

    public class LoopQueue implements Queue {
    
        private E[] data;
        private int front, tail;
        private int size; 
        //  可以思考一下:LoopQueue中不声明size,如何完成所有的逻辑?
    
        public LoopQueue(int capacity){
            data = (E[])new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        public LoopQueue(){
            this(10);
        }
    
        public int getCapacity(){
            return data.length - 1;
        }
    
        @Override
        public boolean isEmpty(){
            return front == tail;
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        // 下一小节再做具体实现
        @Override
        public void enqueue(E e){
    
        }
    
        // 下一小节再做具体实现
        @Override
        public E dequeue(){
            return null;
        }
    
        // 下一小节再做具体实现
        @Override
        public E getFront(){
            return null;
        }
    }
    
    

    源码下载

    [dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

    导航目录

    [dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(2.5)循环队列

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 101会员总数(位)
    • 3672资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 124稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级