Collection-3

    前序:队列是平常做业务应用比较少的结构,但是还是要看一下相关的实现方式,特别是JUC包中的同步器,核心原理就是队列和状态的控制。线程安全的集合框架打算单独拿个篇幅整理,由于比较特殊,而且自己也比较薄弱的部分,所以应该会解释的多一些。

   

2. 集合框架 

    2.3 Queue 是在两端出入的List,所以也可以用数组或链表来实现。

LinkedList

容量 

结构 E item;

Node<E> next;

        Node<E> prev;

特点 以双向链表实现的LinkedList既是List,也是Queue。

ArrayDeque 

容量 MIN_INITIAL_CAPACITY = 8; new Object[16];

结构 Object[] elements

扩容  doubleCapacity() int newCapacity = n << 1;  大小是2的倍数,默认是16。

Object[] a = new Object[newCapacity];

System.arraycopy(elements, p, a, 0, r); (原来数组,数组位置,目标数组,数组位置,拷贝长度)

        System.arraycopy(elements, 0, a, r, p);

特点 为了支持FIFO,即从数组尾压入元素(快),从数组头取出元素(超慢),就不能再使用普通ArrayList的实现了,改为使用循环数组。

有队头队尾两个下标:弹出元素时,队头下标递增;加入元素时,队尾下标递增。如果加入元素时已到数组空间的末尾,则将元素赋值到数组[0],同时队尾下标指向0,

再插入下一个元素则赋值到数组[1],队尾下标指向1。如果队尾的下标追上队头,说明数组所有空间已用完,进行双倍的数组扩容。

扩容的时候,把原来数组头元素后面的部分,长度为r,拷贝到新数组 从新数组0位置开始 把原来数组 0 到 头元素坐标的部分拷贝到 r后面

PriorityQueue

容量 初始大小为11

扩容 空间不够时自动50%扩容

特点:用平衡二叉最小堆实现的优先级队列,不再是FIFO,而是按元素实现的Comparable接口或传入Comparator的比较结果来出队,数值越小,优先级越高,越先出队。

但是注意其iterator()的返回不会排序。

评论已关闭。