美文网首页
ArrayDeque小抄

ArrayDeque小抄

作者: 上海马超23 | 来源:发表于2017-07-12 20:33 被阅读0次
class ArrayDeque {
   // 循环数组,一个数组+2个下标指针
   transient Object[] elements;
   // 第一个元素的索引
   transient int head;
   // 末尾元素的索引+1,即未来下个元素添加的位置
   transient int tail;
   
   public ArrayDeque(int numElements) {
       allocateElements(numElements);
   }
   
   // 保证容量是2的倍数
   private void allocateElements(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
       }
       elements = new Object[initialCapacity];
   }
   
   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;  // 扩容为原来的2倍
     if (newCapacity < 0)  
         throw new IllegalStateException("Sorry, deque too big");  
     Object[] a = new Object[newCapacity];  
     // 既然是head和tail已经重合了,说明tail是在head的左边。  
     // 即大于等于head指针的下标内容应该放在扩容后数组的开头
     System.arraycopy(elements, p, a, 0, r); // 拷贝原数组从head位置到结束的数据  
     // 小于等于tail指针的下标内容,应该放在紧接着刚刚head后数组位置后面
     System.arraycopy(elements, 0, a, r, p); // 拷贝原数组从开始到head的数据  
     elements = (E[])a;  
     head = 0; // 重置head和tail为数据的开始和结束索引  
     tail = n;  
 } 
 
 public void addFirst(E e) {  
     if (e == null)  
         throw new NullPointerException();  
     // 本来可以简单地写成head-1,但如果head为0,减1就变为-1了
     // 和elements.length - 1进行与操作就是为了处理这种情况,这时结果为elements.length - 1, 也就是最后一个元素,形成了循环
     elements[head = (head - 1) & (elements.length - 1)] = e;  
     if (head == tail) // head和tail不可以重叠  
         doubleCapacity();  
 } 

   // 从数组头取出元素,如果是顺序数组的实现,就要把头元素后面所有元素都往前移动,效率很差
   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
       // 弹出元素时,队头下标递增
       // 处理临界情况(当h为elements.length - 1时),与后的结果为0。实现循环
       head = (h + 1) & (elements.length - 1);
       return result;
   }
   
   public void addLast(E e) {
       if (e == null)
           throw new NullPointerException();
       elements[tail] = e;
       if ( (tail = (tail + 1) & (elements.length - 1)) == head)
           doubleCapacity();
   }
}

总结

-1 & N = N
N-1 & N = 0

相关文章

  • ArrayDeque小抄

    总结 -1 & N = NN-1 & N = 0

  • ArrayDeque

    ArrayDeque 原文见Java 容器源码分析之 Deque 与 ArrayDeque。 概述 ArrayDe...

  • 源码的魅力 - ArrayDeque 的工作原理

    ArrayDeque 的工作原理(Android 7.1源码) 简介 ArrayDeque 是以循环数组形式实现的...

  • ArrayDeque:LinkedList

    ArrayDeque和LinkedList都实现了Deque双端队,从两端取值/添加/删除. ArrayDeque...

  • Java ArrayDeque 原理之循环数组

    问:谈谈你对 ArrayDeque 主要方法实现原理的认识? 答:即循环数组的实现原理。 从 ArrayDeque...

  • 死磕 java集合之ArrayDeque源码分析

    问题 (1)什么是双端队列? (2)ArrayDeque是怎么实现双端队列的? (3)ArrayDeque是线程安...

  • Java双端队列-ArrayDeque的使用

    1、概览 本篇,我们将介绍ArrayDeque的使用方法-ArrayDeque是Deque的一个实现。ArrayD...

  • ArrayDeque

    队列方法基础说明见队列接口设计 一 ArrayDeque中操使用了各种位操作,先对位运算进行说明 二进制数表示二进...

  • ArrayDeque

    双端队列,在OkHttp#Dispatcher有用到 感谢xiaoshua ArrayDeque源码分析 一 构...

  • ArrayDeque

    几句话证明你看过ArrayDeque的源码Deque: double ended queue,双端队列,它既可以当...

网友评论

      本文标题:ArrayDeque小抄

      本文链接:https://www.haomeiwen.com/subject/zacihxtx.html