文档章节

Queue.ArrayDequeue

脑丨残
 脑丨残
发布于 2017/05/22 21:04
字数 348
阅读 2
收藏 0

#ArrayDequeue

  • 内部数组,双向队列,线程不安全,性能高于stack。做队列性能高于linkedList,内部数组。
  • 内部操作指针,进行操作,容量不足,自动扩容。
    transient Object[] elements; // non-private to simplify nested class access
    /**
     * The index of the element at the head of the deque (which is the
     * element that would be removed by remove() or pop()); or an
     * arbitrary number equal to tail if the deque is empty.
     */
    transient int head;
    /**
     * The index at which the next element would be added to the tail
     * of the deque (via addLast(E), add(E), or push(E)).
     */
    transient int tail;
  • offer方法和add方法都是通过其中的addLast方法实现,每添加一个元素,就把元素加到数组的尾部,此时,head指针没有变化,而tail指针加一,因为指针是循环加的,所以当tail追上head,((this.tail = this.tail + 1 & this.elements.length - 1) == this.head)时,数组容量翻一倍,继续执行。
public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
  • remove方法和poll方法都是通过其中的pollFirst方法实现,每移除一个元素,该元素所在位置变成null,此时,tail指针没有变化,而head指针加一,当数组中没有数据时,返回null
    public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }
  • 扩容,先复制head右边,再复制head左边

© 著作权归作者所有

共有 人打赏支持
上一篇: Queue.LinkedList
下一篇: Queue.ArrayBlockQueue
脑丨残
粉丝 8
博文 60
码字总数 23267
作品 0
西安
私信 提问

暂无文章

AI赋能一键自动检测:页面异常、控件异常、文本异常

摘要: 1.前言 闲鱼质量团队一直致力于交付高质量的app给用户,当前随着AI技术不断发展,TensorFlow大热,也给测试手段带来了更多种可能,本文接下来给大家介绍AI在闲鱼测试的一点实践:如何...

阿里云官方博客
13分钟前
0
0
Microsoft Remote Desktop For Mac

地址:https://rink.hockeyapp.net/apps/5e0c144289a51fca2d3bfa39ce7f2b06/ 解决国内App store不能下载的问题。

Cheuker
24分钟前
0
0
原地打印刷新(倒计时)

原地打印刷新(倒计时) 代码如下 from time import sleepfor i in reversed(range(1, 11)): print("\r倒计时:{}秒".format(i), end="") sleep(1)...

_Change_
37分钟前
0
0
php,vue,vue-ssr 做出来的页面有什么区别?

欢迎大家前往腾讯云+社区,获取更多腾讯海量技术实践干货哦~ 本文由shirishiyue发表于云+社区专栏 目前我这边的web页面,都是采用php+smarty模板生成的,是一种比较早期的开发模式。好处是没...

腾讯云加社区
43分钟前
1
0
安卓的切图规范

Android UI 切图命名规范、标注规范及单位描述 很多UI设计师做APP切图都会有两套,一套是Android的,一套是IOS的。IOS我这边暂不作讲解,因为我本人也不是开发IOS。这里整理一下我在Android...

mo311
47分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部