文档章节

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左边

© 著作权归作者所有

共有 人打赏支持
脑丨残
粉丝 8
博文 60
码字总数 23267
作品 0
西安

暂无文章

Spring IOC实现原理

1、BeanDefinition 对依赖翻转模式中管理对象依赖关系的数据抽象 实现依赖翻转功能的核心数据结构 依赖翻转功能都是围绕对BeanDefinition 处理完成的 有了这些BeanDefinition 基础数据结构,...

职业搬砖20年
28分钟前
1
0
Python判断变量的数据类型的两种方法

1、isinstance(变量名,类型) def varargsql(self, sql, *args): if isinstance(args, tuple): self.cursor.execute(sql, args) self.conn.commit() 2、通过与其他已......

fang_faye
28分钟前
1
0
xml 转义特殊字符

XML中共有5个特殊的字符,分别是:&<>“’。如果配置文件中的注入值包括这些特殊字符,就需要进行特别处理。有两种解决方法:其一,采用本例中的特殊标签,将包含特殊字符的字符串封装起来;...

inidcard
30分钟前
1
0
Mysql中哪些sql 不会走索引

1. 索引列参与了计算 SELECT `sname` FROM `stu` WHERE `age`+10=30; 2. 索引使用了函数运算 SELECT `sname` FROM `stu` WHERE LEFT(`date`,4) <1990; 3. like SELECT * FROM `houdunwang` W......

ChyiHuang
39分钟前
2
0
nginx 504 Gateway Time-out

打开nginx.config: 参数介绍: #设定http服务器http{include mime.types; #文件扩展名与文件类型映射表default_type application/octet-stream; #默认文件类型#charset utf-8; #默...

lyle_luo
41分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部