这次谈谈ArrayDeque吧。 先看看他的班级关系图吧。 其中一些标识接口被忽视了
让我们看看类的定义
publicclassarraydequeeextendsabstractcollectioneimplementsdequee，Cloneable，Serializable{.}从这里开始，他实现了deque接口
队列：布尔添加(e )； 布尔关闭器(e )； E remove (； 电子池(； E element (； E peek (； eque :语音助手(e )； voidaddlast(e )； 蓝牙前端(ee； 蓝牙(e )； e移除第一个(； E removeLast (； E pollFirst (； 电子轮询last (； 综上所述，Queue接口只定义了几种队列方法，其中一种用于队列，Deque有几种xxFirstxxLast操作方法，这些方法不仅支持队列操作，还支持堆栈操作也请注意addFirstaddLast方法。 由于可以在一个队列中的所有头和尾操作元素，ArrayDeque类支持双端队列和堆栈的所有操作，从而了解他的继承实现关系。 那么，数组transient Object[] elements，用于正式保存其他源实现属性//元素； //头指针transient int head； //末尾指针transient int tail； //容量限制privatestaticfinalintmax _ array _ size=integer.max _ value-8； 综上所述，ArrayDeque的实现仍然采用数组实现，存在一定的容量限制。 其次，从结构构筑方法来看，是没有参加、有初始化容量、以集合为参数制作实例的3种结构构筑方法
publicarraydeque ((元素=new object [ 16 ]； }默认结构的默认容量为16，然后查看其他结构方法
如果publicarraydeque (intnum elements ) /参数小于1，则将1作为默认初始化容量，否则比较容量是否等于Integer.MAX_VALUE。 否则，假设为integer.max _ value 1: (num elements==integer.max _ value )？ integer.max _ value : num elements 1； }这样，即使传递了错误的参数(如负数)，ArrayDeque也不会报告错误。 此外，如果ArrayDeque的最大初始化容量为Integer.MAX_VALUE，而不是负数或最大值，则将参数1初始化为长度，可以看出为什么要传递参数，如果参数为1，则他此时，head和tail都指向0。 另外，第二个null始终为tail保留的是以集合为参数的构建方法
publicarraydeque (收集？ extendsec(//调用上述分析的构建方法，将集合元素的数量设置为默认初始化容量this(c.size ) )； //将集合中的元素复制到数组中的复制元素(c )； }隐私保护要素(collection？ extends E c ) { //forEach是循环的方法，然后在Java8中添加了：操作符，因此//将遍历集合中的元素，并按顺序调用此类的addLast方法添加到数组中//对于具体的addLast，我们将立即开始分析c.foreach在问题之前，我们知道ArrayDeque是双端队列实现，类实现依赖于数组。 当数组中嵌入元素时，head一定指向数组的下标0元素。 此时，取出开头元素，数组index=0位置的元素为null。 那么，此时head必须向后移动一个位置，指向以下元素： 这样，此时，即使添加tail，也一定会向后移动一个位置。 这样，以前释放的index=0的元素的位置不是会浪费吗？ 为了说明这个问题，请看一下图吧
图应该很清楚，所以我们现在面临着这样徒劳的问题。 那么，ArrayDeque提出的解决方案是
案就是将数组作为一个逻辑上的循环数组使用,当head后移导致前面为null时,并且tail到达一个数组的最后位置,那么就去检查head前面的位置是否有空闲的,因为取出都是从head取,所以不会出现断断续续有数据的情况,所以他就要去判断数组位置是否为null,所以ArrayDeque是不允许插入null元素的 看图之后我们知道了大概的思路,所以我们知道了head不会总是0的,tail也不一定总是大于head的,那么对于ArrayDeque最终是怎么实现调整的,我们来看他的源码实现鉴于方法太多,我们就挑出最核心的方法说 add public boolean add(E e) { //默认将元素添加到数组最后面 addLast(e); return true;}public void addLast(E e) { if (e == null) throw new NullPointerException(); //保存引用 final Object[] es = elements; //tail的实现保证永远指向最后一个元素的下一个null位置 //所以可以直接进行插入 es[tail] = e; //这个方法可以说是很巧妙了,主要目的是在于判断是否还有空余位置插入元素 //是否需要扩容,并且还确定tail的指向 if (head == (tail = inc(tail, es.length))) grow(1);}static final int inc(int i, int modulus) { if (++i >= modulus) i = 0; return i;} 理解inc方法有点不容易,所以我们画图来说 从上图,我们就非常清楚了inc的方法的巧妙,也清楚了add方法的流程 分清数组的First和Last ArrayDeque<String> stringArrayDeque = new ArrayDeque<>(4);stringArrayDeque.addFirst("1");stringArrayDeque.addLast("2");sys(stringArrayDeque); //输出方法结果
[2, null, null, null, 1] 所以数组的<-这边是Last,相反则是First addFirst public void addFirst(E e) { if (e == null) throw new NullPointerException(); final Object[] es = elements; //直接使用方法计算位置然后出入 es[head = dec(head, es.length)] = e; if (head == tail) //数组满了 grow(1);//扩容}static final int dec(int i, int modulus) { if (--i < 0) i = modulus - 1; return i;} 经过了inc方法,dec方法我们看着就容易理解多了,其目的就是寻找head的插入位置,上图 OK到这我们就完全了解了他们的实现了, 然后其中涉及到的grow方法我们没有说,下来我们来看一下 grow private void grow(int needed) { final int oldCapacity = elements.length; int newCapacity; // 如果容量小,则增加一倍,否则增加50% int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1); //如果需要增加的容量比指定需要增长的容量小 //或者 //之前的容量加上需要增加的容量后的 总容量大于数组最大容量 if (jump < needed || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0) newCapacity = newCapacity(needed, jump); //确定后开始拷贝 final Object[] es = elements = Arrays.copyOf(elements, newCapacity); // Exceptionally, here tail == head needs to be disambiguated //如果tail和head之间还有位置 //或者数组满了和排除是初始化状态的数组 if (tail < head || (tail == head && es[head] != null)) { //新增容量 int newSpace = newCapacity - oldCapacity; //将数组内元素整理一下 System.arraycopy(es, head, es, head + newSpace, oldCapacity - head); //将之前的元素置空 for (int i = head, to = (head += newSpace); i < to; i++) es[i] = null; }}//边缘条件下的容量计算,特别是溢出private int newCapacity(int needed, int jump) { final int oldCapacity = elements.length, minCapacity; //总容量大于数组最大容量 if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) { //达到上限,报错 if (minCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); //返回最大容量 return Integer.MAX_VALUE; } //到这就代表没有超过限制 //如果指定需要增长的大于方法计算出来的需要增长的容量 if (needed > jump) //就返回之前容量和指定增加的容量的和 return minCapacity; //否则如果没有超过限制,就返回之前容量和计算出来的容量之和,否则就返回数组上限值 return (oldCapacity + jump - MAX_ARRAY_SIZE < 0) ? oldCapacity + jump : MAX_ARRAY_SIZE;} 好了大概的逻辑我们就清楚了,实现扩容并不是只根据参数进行扩容而是进行多方面考虑,比如数组的大小 addAll public boolean addAll(Collection<? extends E> c) { final int s, needed; //deque中的元素数加上集合中的元素数加上永远保证的一个null空间之和减去 //数组的长度,如果大于0表名数组不够,进行grow,否则就不grow if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0) grow(needed); //循环拷贝进去 copyElements(c); return size() > s;}//返回此deque中的元素数public int size() { return sub(tail, head, elements.length);}static final int sub(int i, int j, int modulus) { //判断是否是tail与head有null,让后分情况处理 if ((i -= j) < 0) i += modulus; return i;} 到这add方法基本即结束了,下面是删除方法,删除方法有remove和poll,两者的区别在之前的文章提到过了,在这我就只分析一下remove好了 remove public E remove() { return removeFirst();}public E removeFirst() { //还是调用了poll方法... E e = pollFirst(); //其实poll方法跟remove方法只是缺了这个判断 if (e == null) throw new NoSuchElementException(); return e;}public E pollFirst() { final Object[] es; final int h; //返回数组索引i处的元素 E e = elementAt(es = elements, h = head); //返回的元素不为null if (e != null) { //将它设置为null es[h] = null; //inc方法返回head下一个元素位置 head = inc(h, es.length); } //返回元素 return e;}//实现简单static final <E> E elementAt(Object[] es, int i) { return (E) es[i];} 还有根据OBject对象删除了,无非就是for循环去找,判断相等的办法是equals 对于removeLast的实现就是采用了pollLast方法,里面的核心实现肯定一样,不同的是它使用dec方法,将tail做参数返回位置,别的其他都一样删除了方法还有delete,方法的区别是,i位置被删除后,元素后的整体会迁移还有适应Java8出现的一些lambda方法,比如removeIf,参数是Predicate函数接口,如果你了解lambda你就会知道这个怎样用了add方法是默认在last添加元素,而remove是在first删除,所以这两个方法就构成了一个队列的操作下面介绍的push.pop就构成了一个栈的操作 push没啥可说的了,都分析过了
public void push(E e) { addFirst(e);}public void addFirst(E e) { if (e == null) throw new NullPointerException(); final Object[] es = elements; es[head = dec(head, es.length)] = e; if (head == tail) grow(1);} pop也没啥可说的了
public E pop() { return removeFirst();}//调用关系自己看一下吧 ,上面也有贴源码 所以到这我就将一核心办法给写了一下,当然这完全是自己的分析,也是第一次看,所以不对的地方请指正,谢谢您 总结 那么今天的分析比较令自己惊讶的地方就是inc这个方法,真的是十分的巧妙,而对于其他操作,只要了解一下堆栈是啥再继续在本子上画画图就出来了,那么今天介绍的ArrayDeque是一个数组实现,有容量,不是线程安全,好像已经把他概括完了...对了, 源注释介绍本类的时候, 告诉了我们使用这个类比Stack和LinkedList要快