阅读java.util.ArrayDeque源码Note

原创
2020/04/25 23:01
阅读数 28

ArrayDeque

  1. resizable-array implemention of Deque
  2. 无容量限制
  3. 非线程安全。若在多线程中使用,需要额外的同步设置
  4. 用作stack时,比java.util.Stack快
  5. 用作Queue时,比java.util.LinkedList快
  6. 时间复杂度。#remove(Object o)、#removeFirstOccurrence、#removeLastOccurrence、#contains、#iterator以及相应的批处理操作,linear time(线性时间);其他方法,基本上是constant time(常量时间)
  7. iterators, fail-fast机制。 ConcurrentModificationException
  8. 底层使用数组存储,不存储队列元素的数组位置为null
  9. head和tail之间的元素(从head开始向左直至tail)肯定不会为null
  10. 初始化时,空的队列,head和tail相等

注意: head和tail是可以在数组上循环的,意即:head和tail不停的在数组上从左向右移动,移动后终点后,再继续从数组的起始位置继续移动。相当于一个环!理解了此处,就可以很方便的理解每个方法。
基于上述内容,可以推理出,tail的位置(在数组上)可能会在head的前面。

    //根据元素个数计算出容量大小
    private static int calculateSize(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        return initialCapacity;
    }

  1. 不允许放入null元素
  2. 在加入单个元素时,加入完成后,若head和tail相等,则双倍扩容
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        // head和tail的位置,不一定是在数组的起始位置。先将head右边的元素拷贝至新数据
        System.arraycopy(elements, p, a, 0, r);
        // 将数组起始位置至head位置的元素拷贝至后续位置
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }
  1. 在队列头部添加元素,, head = (head -1 ) & (elements.length - 1)
//注意此处,不是直接将元素放置于head的位置,而是head前面的位置。因为head代表的是头部元素
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

  1. 在队列尾部添加添加元素,添加完成后,重新计算tail的位置:tail = (tail + 1) & (elements.length - 1)
    //注意此处,直接将元素放置于tail位置。tail用于标明下一个尾部元素添加的位置
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

  1. 从头部移除元素,head向后移动
    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向后移动
        head = (h + 1) & (elements.length - 1);
        return result;
    }

  1. 从尾部移除元素,tail向前移动
    public E pollLast() {
        //tail之前的位置
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        //重置tail
        tail = t;
        return result;
    }

  1. 一定要理解: head代表头部元素的位置;tail代表尾部元素的下一个位置!
  2. 删除指定位置的元素
    private boolean delete(int i) {
        checkInvariants();
        final Object[] elements = this.elements;
        final int mask = elements.length - 1;
        final int h = head;
        final int t = tail;
        // i 之前的元素个数
        final int front = (i - h) & mask;
        // i 之后的元素个数
        final int back  = (t - i) & mask;

        // (t -h) & mask 队列的元素总个数
        // Invariant: head <= i < tail mod circularity
        if (front >= ((t - h) & mask))
            throw new ConcurrentModificationException();
        // 最小元素移动 若i之前的元素个数大于之后的个数,则将之后的元素向前移动;
        // 否则,将之前的元素向后移动。
        // Optimize for least element motion
        if (front < back) {
            if (h <= i) {
                /**
                 * X   X   X   E   E   E   E   E   E   X
                 *             h   i                   t
                 */
                System.arraycopy(elements, h, elements, h + 1, front);
            } else { // Wrap around
                /**
                 * E   E   E   E   E   E   X   X   E   E
                 *     i                   t       h    
                 */
                System.arraycopy(elements, 0, elements, 1, i);
                elements[0] = elements[mask];
                System.arraycopy(elements, h, elements, h + 1, mask - h);
            }
            elements[h] = null;
            head = (h + 1) & mask;
            return false;
        } else {
            if (i < t) { // Copy the null tail as well
                /**
                 * X   X   X   E   E   E   E   E   E   X
                 *             h               i       t
                 */
                System.arraycopy(elements, i + 1, elements, i, back);
                tail = t - 1;
            } else { // Wrap around
                /**
                 * E   X   X   X   E   E   E   E   E   E
                 *     t           h               i 
                 */
                System.arraycopy(elements, i + 1, elements, i, mask - i);
                elements[mask] = elements[0];
                System.arraycopy(elements, 1, elements, 0, t);
                tail = (t - 1) & mask;
            }
            return true;
        }
    }

  1. 计算队列大小
    public int size() {
        return (tail - head) & (elements.length - 1);
    }

欢迎关注我的公众号:

展开阅读全文
amp
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部