article_content

队列是一种特殊的线性表，遵循先入先出、后入后出的基本原则，一般来说，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，但是java的某些队列运行在任何地方插入删除；比如我们常用的 LinkedList 集合，它实现了Queue 接口，因此，我们可以理解为 LinkedList 就是一个队列；

1：队列特性

队列主要分为阻塞和非阻塞，有界和无界、单向链表和双向链表之分；

阻塞和非阻塞

阻塞队列
  入列(添加元素)时，如果元素数量超过队列总数，会进行等待（阻塞），待队列的中的元素出列后，元素数量未超过队列总数时，就会解除阻塞状态，进而可以继续入列；
   出列(删除元素)时，如果队列为空的情况下，也会进行等待（阻塞），待队列有值的时候即会解除阻塞状态，进而继续出列；
阻塞队列的好处是可以防止队列容器溢出；只要满了就会进行阻塞等待；也就不存在溢出的情况；
只要是阻塞队列，都是线程安全的；

非阻塞队列
不管出列还是入列，都不会进行阻塞，
入列时，如果元素数量超过队列总数，则会抛出异常，
出列时，如果队列为空，则取出空值；

一般情况下，非阻塞式队列使用的比较少，一般都用阻塞式的对象比较多；阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法：

出队阻塞方法： take()
入队阻塞方法： put()

有界和无界

有界：有界限，大小长度受限制
无界：无限大小，其实说是无限大小，其实是有界限的，只不过超过界限时就会进行扩容，就行ArrayList 一样，在内部动态扩容

单向链表和双向链表

单向链表： 每个元素中除了元素本身之外，还存储一个指针，这个指针指向下一个元素；

双向链表：除了元素本身之外，还有两个指针，一个指针指向前一个元素的地址，另一个指针指向后一个元素的地址；

2：Java 队列接口继承图

3：队列常用方法

　　add        增加一个元索                     如果队列已满，则抛出一个IIIegaISlabEepeplian异常
　　remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
　　element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
　　offer       添加一个元素并返回true       如果队列已满，则返回false
　　poll         移除并返问队列头部的元素    如果队列为空，则返回null
　　peek       返回队列头部的元素             如果队列为空，则返回null
　　put         添加一个元素                      如果队列满，则阻塞
　　take        移除并返回队列头部的元素     如果队列为空，则阻塞
drainTo(list) 一次性取出队列所有元素

知识点： remove、element、offer 、poll、peek 其实是属于Queue接口。

4：阻塞队列与非阻塞队列具体详解

非阻塞队列：

1、ConcurrentLinkedQueue

单向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安全，内部基于节点实现

2、ConcurrentLinkedDeque

双向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安全

3、PriorityQueue

内部基于数组实现，线程不安全的队列

阻塞队列：

1、DelayQueue

一个支持延时获取元素的无界阻塞队列

2、LinkedTransferQueue

一个由链表结构组成的无界阻塞队列。

Java并发包--LinkedBlockingDeque - ken007 - 博客园

3、ArrayBlockingQueue

有界队列，阻塞式,初始化时必须指定队列大小，且不可改变；，底层由数组实现；

4、SynchronousQueue

最多只能存储一个元素，每一个put操作必须等待一个take操作，否则不能继续添加元素

5、PriorityBlockingQueue

一个带优先级的队列，而不是先进先出队列。元素按优先级顺序被移除，而且它也是无界的，也就是没有容量上限，虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError 错误；

博客：

LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。（LinkedBlockingDeque还是可选容量的(防止过度膨胀)，即可以指定队列的容量。如果不指定，默认容量大小等于Integer.MAX_VALUE（@Native public static final int MAX_VALUE = 0x7fffffff））

　　ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。

　　LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。

　　PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。

　　LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。

　　SynchronousQueue：一个不存储元素的阻塞队列。

　　DealyQueue：一个使用优先级队列实现的无界阻塞队列。

高并发第十三弹:J.U.C 队列 SynchronousQueue.ArrayBlockingQueue.LinkedBlockingQueue.LinkedTransferQueue - 爱呼吸的鱼 - 博客园

二：双端队列Deque

双端队列既可以当作队列也可以当作栈！方法中可以先入先出也可以先入后出，因为是双端的，所以栈我们不推荐使用Vector的实现类Stack，推荐使用双端队列ArrayDeque来做栈。

Deque———ArrayDeque类详解

类型	方法	作用
添加元素	public void addFirst(E e)	在数组前面添加元素
	public void addLast(E e)	在数组后面添加元素
	public boolean offerFirst(E e)	在数组前面添加元素，并返回是否添加成功
	public boolean offerLast	在数组后面添加元素，并返回是否添加成功
删除元素	public E pollFirst()	删除第一个元素，并返回删除元素的值，如果元素为null，将返回null
	public E removeFirst()	删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常
	public E pollLast()	删除最后一个元素，并返回删除元素的值，如果为null，将返回null
	public E removeLast()	删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常
	public boolean removeFirstOccurrence(Object o)	删除第一次出现的指定元素
	public boolean removeLastOccurrence(Object o)	删除最后一次出现的指定元素
获取元素	public E getFirst()	获取第一个元素,如果没有将抛出异常
获取元素	public E getLast()	获取最后一个元素，如果没有将抛出异常
队列操作	public boolean add(E e)	在队列尾部添加一个元素
	public boolean offer(E e)	在队列尾部添加一个元素，并返回是否成功
	public E remove()	删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())
	public E poll()	删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())
	public E element()	获取第一个元素，如果没有将抛出异常
	public E peek()	获取第一个元素，如果返回null
栈操作	public void push(E e)	栈顶添加一个元素
栈操作	public E pop()	移除栈顶元素,如果栈顶没有元素将抛出异常
其他	public int size()	获取队列中元素个数
	public boolean isEmpty()	判断队列是否为空
	public Iterator iterator()	迭代器，从前向后迭代
	public Iterator descendingIterator()	迭代器，从后向前迭代
	public boolean contains(Object o)	判断队列中是否存在该元素
	public Object[] toArray()	转成数组
	public T[] toArray(T[] a)	转成a数组常
	public void clear()	清空队列
	public ArrayDeque clone()	克隆(复制)一个新的队列

六.参考资料

1.数据结构

ArrayDeque类是双端队列的线性实现类。

具有以下特征：

☞ ArrayDeque是采用数组方式实现的双端队列。
☞ ArrayDeque的出队入队是通过头尾指针循环，利用数组实现的。
☞ ArrayDeque容量不足时是会扩容的，每次扩容容量增加一倍。
☞ ArrayDeque可以直接作为栈使用。当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList。
☞ 无容量大小限制，容量按需增长。
☞ 非线程安全队列，无同步策略，不支持多线程安全访问。
☞ 具有fail-fast特性，不能存储null值，支持双向迭代器遍历。

ArrayDeque的实现结构图如下所示:

2.类标题

ArrayDeque类的标题如下：

public class ArrayDeque extends AbstractCollection implements Deque, Cloneable, Serializable

这个标题说明ArrayDeque类是AbstractCollection类的子类，并且实现了三个接口：Deque、Cloneable和Serializable。

如下图所示：

1.ArrayDeque实现了Deque接口，即能将LinkedList当做双端队列使用。
2.ArrayDeque实现了Cloneable接口，即覆盖了函数clone()，能克隆。
3.ArrayDeque实现java.io.Serializable接口，LinkedList支持序列化，能通过序列化去传输。
4.ArrayDeque是非同步的[2]。

【注2】在这里的非同步指的是,当使用线程的时候,对于这个集合对象进行操作,那么不同的线程所获取的这个集合对象是不同的.所以是说不同步,在多线程的形式是不安全的.

3.字段

transient Object[] elements;
存储元素的数组

transient int head;
队列头位置

transient int tail;
队列尾位置

private static final int MIN_INITIAL_CAPACITY = 8;
一个新创建的队列的最小容量

4.构造函数

4.1 无参的构造方法,创建一个容量为16的ArrayDeque

源码如下：


    public ArrayDeque() {       //无参构造函数，默认的底层数组大小为16.
        elements = new Object[16];
    }

4.2 有参的构造方法，创建一个指定大小的ArrayDeque

源码如下：


    public ArrayDeque(int numElements) { //如果指定初始容量小于8，将会返回容量为8的新数组。
        allocateElements(numElements);   //调用allocateElements方法，分配新数组
    }
 
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        //做移位与运算最后加一得到比给定长度大的最小的2的幂数。
        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];
    }

源码分析：对于一个给定长度，先判断是否小于定义的最小长度，如果小于，则使用定义的最小长度作为数组的长度。否则，找到比给定长度大的最小的2的幂数（在if里面的语句实现这一功能）。

如下图所示：

【注】 ">>>"表示无符号右移，也叫逻辑右移。即若该数为正，则高位补0，若该数为负数，则右移后高位同样补0.

4.3 有参的构造方法，将现有集合元素C加入队列进行构造

源码如下：


    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());//调用上述allocateElements()方法，分配型数组内存空间。
        addAll(c);//调用addAll()方法，将现有集合元素c添加到ArrayDeque中。
    }
 
//addAll(Collection c) inherited from AbstractCollection
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }
//将集合元素添加到ArrayDeque末尾
    public boolean add(E e) {
        addLast(e);//addLast()方法作用为：在最后一个元素后面添加元素。详见下述public void addLast(E e)。
        return true;
    }

源码分析：先根据已有集合c大小，通过allocateElement()方法创建最小的2的幂数的数组空间。addAll()将c中元素通过add()逐个添加到型数组中。

5.方法分析

添加元素

public void addFirst(E e)
作用:在ArrayDeque前面添加元素。

源码如下:


    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;//将元素e添加到ArrayDeque双端队列的队首位置。
        if (head == tail)//(head == tail)判定内存不足
            doubleCapacity();//进行扩容操作
    }
 
//扩容为原来的两倍
    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];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }
 
    //java.lang.System
/*
    @Function:复制数组，以插入元素，但是要将index之后的元素都往后移一位。然后就是插入元素，增加sized的值
    @src:源数组  srcPos:源数组要复制的起始位置   dest:目的数组  destPos:目的数组放置的起始位置  length:复制的长度
*/
    public static native void arraycopy(Object src,int srcPos,Object dest, int destPosint length);

源码分析：将元素插入到head前一位，同时修改head值。判断内存是否足够，若不够，扩容为原数组的两倍。然后通过System.arraycopy()，将原来数组的元素复制到新数组中。

elements[head = (head - 1) & (elements.length - 1)] = e;

当head ≠ 0时

因为element数组的内存大小为2的n次幂，因此(elements.length-1),二进制为全1，[head - 1] & (elements.length - 1)]值始终为head-1的值。即在element[head-1]插入元素。

当head = 0时

head - 1 = -1。其中-1用二进制表示为全1，与elements.length - 1逐位与，结果为elements.length - 1的值，即在数组的末尾插入元素。

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

将elements数组从head索引(n-p)长度复制到a数组从0开始的位置。然后将elements数组从0索引开始p长度复制到a数组r索引开始的位置。

如下图所示：

public void addLast(E e)
作用：在ArrayDeque后面添加元素。

源码如下：


    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;//将e放到tail位置
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)//和head的操作类似，为了处理临界情况 (tail为length - 1时)，和length - 1进行与操作，结果为0
            doubleCapacity();//将ArrayDeque容量扩展为原来的两倍。源码详见上述public void addFirst(E e)
    }

源码分析：在ArrayDeque中tail索引处添加元素e。若添加元素后tail+1 == head，判定内存不足，对ArrayDeque调用doubleCapacity()进行扩容操作。

public boolean offerFirst(E e)
作用：在ArrayDeque前添加一个元素，并返回是否添加成功。

源码如下：


    public boolean offerFirst(E e) {
        addFirst(e);//在ArrayDeque数组head前添加元素，addFirst()详见上述public void addFirst().
        return true;
    }

源码分析：调用addFirst()方法，当添加成功后返回true。

public boolean offerLast(Object o)
作用：在ArrayDeque后面添加一个元素，并返回是否添加成功。

源码如下：


    public boolean offerLast(E e) {
        addLast(e);//在ArrayDeque数组tail出添加元素，addLast()详见上述public void addLast()
        return true;
    }

源码分析：调用addLast()方法，当添加成功后返回true.

public E pollFirst()
作用：删除第一个元素，并返回删除元素的值。如果元素为null，将返回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;
    }

源码分析：将数组的第一个元素赋值给result并返回，同时将head后移。

public E removeFirst()
作用：删除第一个元素，并返回删除元素的值。如果元素为null，将抛出异常。

源码如下：


    public E removeFirst() {
        E x = pollFirst();//将删除后的值赋给x,pollFirst()详见上述pollFirst()
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

源码分析：调用pollFirst()返回删除的值，若返回值为null，抛出异常。

public E pollLast()
作用：删除最后一个元素，并返回删除元素的值。如果元素为null，将返回null。

源码如下：


    public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

源码分析： (tail - 1) & (elements.length - 1)指定待删除元素的位置，并将待删除元素赋值给result.同时将数组中最后一个元素赋null值。

public E removeLast()
作用：删除最后一个元素，并返回删除元素的值。如果元素为null，将抛出异常。

源码如下：


    public E removeLast() {
        E x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

源码分析：调用pollLast()返回删除的值，若返回值为null，抛出异常。

public boolean removeFirstOccurrence(Object o)
作用：删除第一次出现的指定元素。

源码如下：


    public boolean removeFirstOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = head;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i + 1) & mask;//从头到尾遍历
        }
        return false;
    }

源码分析：

i = (i + 1) & mask;

对数组从头到尾进行遍历，

原理如下图所示：

从数组的head处对非空元素进行遍历，若数组中包含o对象，调用delete()进行删除，并返回true；否则，返回false。

private boolean delete(int i)源码如下所示：


    private void checkInvariants() {//有效性检查
        assert elements[tail] == null;//tail位置没有元素
        assert head == tail ? elements[head] == null :
            (elements[head] != null &&
             elements[(tail - 1) & (elements.length - 1)] != null);//如果head和tail重叠，队列为空；否则heaed位置有元素，tail-1位置有元素
        assert elements[(head - 1) & (elements.length - 1)] == null;//head-1 的位置没有元素
    }
 
 
    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;
        final int front = (i - h) & mask;//i到head元素处之间的元素个数
        final int back  = (t - i) & mask;//i到tail元素处之间的元素个数
 
        // Invariant: head <= i < tail mod circularity
        if (front >= ((t - h) & mask))//i到head元素处的距离大于现有元素总数，抛出异常
            throw new ConcurrentModificationException();
 
        // Optimize for least element motion
        if (front < back) {//i的元素靠近head,移动开始的元素，返回false.
            if (h <= i) {//当i在head的后面
                //将从head开始长度为front的数组片段复制到head+1开始的地方
                System.arraycopy(elements, h, elements, h + 1, front);
            } else { // 当i在head的前面
                //将0 ~ （i - 1)的元素后移一位，将数组最后一位元素移到数组第一位，将head后的元素后移一位。
                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 {//i的位置靠近tail，移动末尾的元素，返回true.
            if (i < t) { 当i在tail的前面
                //将从i + 1开始长度为back的数组片段复制到以i开始的地方
                System.arraycopy(elements, i + 1, elements, i, back);
                tail = t - 1; 
            } else { //当i在tail后面
                //将从i+1到数组最后一个元素往前移动一位，再将第一个元素移到最后一位。将剩余元素往前移动一位
                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;
        }
    }

源码分析：为了算法的复杂度，将delete()函数分为三种情况

如下图所示：

一.待删除元素距离第一个元素比最后一个元素近

1.1 待删除元素在数组中的位置在第一个元素的后面

将从head开始长度为front的数组片段复制到head+1开始的地方。如下图所示：

1.2 待删除元素在数组中的位置在第一个元素的前面

将0 ~ （i - 1)的元素后移一位，将数组最后一位元素移到数组第一位，将head后的元素后移一位。如下图所示：

二.待删除元素距离最后一个元素比第一个元素近

2.1 待删除元素在数组中的位置在第一个元素的前面

将从i + 1开始长度为back的数组片段复制到以i开始的地方。如下图所示：

2.2 待删除元素在数组中的位置在第一个元素的后面

将从i+1到数组最后一个元素往前移动一位，再将第一个元素移到最后一位。将剩余元素往前移动一位。如下图所示：

三.待删除元素到第一个元素的距离等于到最后一个元素的距离

同情况二。

public boolean removeLastOccurrence(Object o)
作用：删除最后一次出现的指定元素。

源码如下：


    public boolean removeLastOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = (tail - 1) & mask;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i - 1) & mask;//从尾到头遍历
        }
        return false;
    }

源码分析：从最后一个元素处对数组进行遍历，若数组中包含o对象，调用delete()进行删除，并返回true；否则，返回false。原理同上述public boolean removeFirstOccurrence(Object o)。

public E getFirst()
作用：获取第一个元素，如果没有将抛出异常。

源码如下：


    public E getFirst() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

源码分析：将head索引处元素值返回。

public E getLast()
作用：获取最后一个元素，如果没有将抛出异常。

源码如下：


    public E getLast() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[(tail - 1) & (elements.length - 1)];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

源码分析：将最后一个元素值返回。

public boolean add(E e)
作用：在队列尾部添加一个元素。

源码如下：


    public boolean add(E e) {
        addLast(e);//addLast()方法作用为：在最后一个元素后面添加元素。详见下述public void addLast(E e)。
        return true;
    }

public boolean offer(E e)
作用：在队列尾部添加一个元素，并返回是否成功

源码如下：


    public boolean offer(E e) {
        return offerLast(e);//offerLast()源码分析详见上述public boolean offerLast(Object o)
    }

public E remove()
作用：删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())

源码如下：


    public E remove() {
        return removeFirst();//移除队列第一个元素。removeFirst()源码分析详见上述：public E removeFirst()
    }

public E poll()
作用：删除队列中第一个元素，并返回该元素的值，如果元素为null，将返回null。

源码如下：


    public E poll() {
        return pollFirst();//删除第一个元素，并返回删除元素的值.pollFirst()源码分析详见上述public E pollFirst()
    }

public E element()
作用：获取第一个元素。如果没有将抛出异常

源码如下：


    public E element() {
        return getFirst();//getFirst()用于获取第一个元素， 源码详见上述： public E getFirst()
    }

public E peek()
作用：获取第一个元素，如果返回null.

源码如下：


    public E peek() {
        return peekFirst();
    }
 
    public E peekFirst() {
        // elements[head] is null if deque empty
        return (E) elements[head];
    }

public void push(E e)
作用：栈顶添加一个元素.

源码如下：


    public void push(E e) {
        addFirst(e);//在head索引前添加元素，并将head前移。源码分析详见上述：public void addFirst(E e)
    }

public E pop()
作用：栈顶添加一个元素.

源码如下：


    public E pop() {
        return removeFirst();//删除第一个元素，并返回删除元素的值。源码分析详见上述：public E removeFirst()
    }

public int size()
作用：获取队列中元素个数.

源码如下：


    public int size() {
        return (tail - head) & (elements.length - 1);
    }

源码分析：当tail在数组中的位置在head的后面(tail - head) & (elements.length - 1) 等价于 (tail - head)。当tail在数组中的位置在head的前面(tail - head) & (elements.length - 1) 等价于 elements - (tail - head)。

public boolean isEmpty()
作用：判断队列是否为空。

源码如下：


    public boolean isEmpty() {
        return head == tail;
    }

源码分析： tail位置的元素一定为空，head和tail相等，也为空。

public Iterator iterator()
作用：迭代器，从前往后迭代

源码如下：


    public Iterator<E> iterator() {
        return new DeqIterator();
    }
 
    private class DeqIterator implements Iterator<E> {  
      private int cursor = head;  
      private int fence = tail; // 迭代终止索引，同时也为了检测并发修改。  
      private int lastRet = -1; // 最近的next()调用返回的索引。据此可以定位到需要删除元素的位置。  
      public boolean hasNext() {  
          return cursor != fence;  
      }  
  
      public E next() {  
          if (cursor == fence)  
              throw new NoSuchElementException();  
          E result = elements[cursor];  
          // This check doesn't catch all possible comodifications,  
          // but does catch the ones that corrupt traversal  
          if (tail != fence || result == null)  
              throw new ConcurrentModificationException();  
          lastRet = cursor;  
          cursor = (cursor + 1) & (elements.length - 1); // 游标位置加1  
          return result;  
      }  
  
      public void remove() {  
          if (lastRet < 0)  
              throw new IllegalStateException();  
          if (delete(lastRet)) { // 如果将元素从右往左移，需要将游标减1。  
              cursor = (cursor - 1) & (elements.length - 1); // 游标位置回退1。  
fence = tail; // 重置阀值。  
   }  
          lastRet = -1;  
      }  
  }

源码分析： ArrayDeque继承了Iterable接口，必须实现其中的iterator()，ArrayDeque实现从头往后遍历的迭代器iterator()，其中主要包含：hasNext()方法用于判定当前cursor是否还有下一个元素；next()方法来锁定下一个元素；以及remove()用于移除lastRet处的元素值。

public Iterator descendingIterator()
作用：迭代器，从后向前迭代

源码如下：


    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }       
 
    private class DescendingIterator implements Iterator<E> {  
  
        private int cursor = tail; // 游标开始索引为tail  
        private int fence = head; // 游标的阀值为head  
        private int lastRet = -1;  
  
        public boolean hasNext() {  
            return cursor != fence;  
        }  
  
        public E next() {  
            if (cursor == fence)  
                throw new NoSuchElementException();  
            cursor = (cursor - 1) & (elements.length - 1); // tail是下个添加元素的位置，所以要减1才是尾节点的索引。  
            E result = elements[cursor];  
            if (head != fence || result == null)  
                throw new ConcurrentModificationException();  
            lastRet = cursor;  
            return result;  
        }  
  
        public void remove() {  
            if (lastRet < 0)  
                throw new IllegalStateException();  
            if (!delete(lastRet)) { // 如果从左往右移，需要将游标加1。  
                cursor = (cursor + 1) & (elements.length - 1);  
                fence = head;  
            }  
            lastRet = -1;  
        }  
    }

源码分析： DescendingIterator是从后往前的迭代器。其中主要包含：hasNext()方法用于判定当前cursor是否还有下一个元素；next()方法来锁定下一个元素；以及remove()用于移除lastRet处的元素值。

public boolean contains(Object o)
作用：判断队列中是否存在钙元素。

源码如下：


    public boolean contains(Object o) {
        if (o == null)
            return false;//ArrayDeque不能存储null值
        int mask = elements.length - 1;
        int i = head;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x))
                return true;
            i = (i + 1) & mask;//处理临界情况
        }
        return false;
    }

源码分析：同上述：public boolean removeFirstOccurrence(Object o),从前往后遍历，如果在数组中存在与o相同的元素，则返回true。否则，返回false。

public Object[] toArray()
作用：转成数组。

源码如下：


    public Object[] toArray() {
        return copyElements(new Object[size()]);
    }
 
    private <T> T[] copyElements(T[] a) {
        if (head < tail) {//将elements数组所有元素复制到从0索引开始的a数组中
            System.arraycopy(elements, head, a, 0, size());
        } else if (head > tail) {//先复制从elements数组head~elements.length - 1处数组，然后将0 ~ tail - 1索引处元素复制到后面
            int headPortionLen = elements.length - head;
            System.arraycopy(elements, head, a, 0, headPortionLen);
            System.arraycopy(elements, 0, a, headPortionLen, tail);
        }
        return a;
    }

源码分析：把所有元素拷贝到新创建的Object数组上，所以对返回数组的修改不会影响该双端队列。

public T[] toArray(T[] a)
作用：转成指定数组。

源码如下：


    public <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size)//目标数组大小不够
            a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(), size);//利用反射创建类型为T，大小为size的数组
        copyElements(a);//拷贝所有元素到目标数组。源码详见上述：>public Object[] toArray()
        if (a.length > size)
            a[size] = null;//结束标识
        return a;
    }

源码分析：

a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);

public void clear()
作用：清空队列。

源码如下：


    public void clear() {
        int h = head;
        int t = tail;
        if (h != t) { // 判空条件
            head = tail = 0;
            int i = h;
            int mask = elements.length - 1;
            do {
                elements[i] = null;//清除元素
                i = (i + 1) & mask;
            } while (i != t);
        }
    }

源码分析：从前往后将数组值置空值。

public ArrayDeque clone()
作用：克隆(复制)一个新的队列。

源码如下：


    public ArrayDeque<E> clone() {
        try {
            @SuppressWarnings("unchecked")
            ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
            //传入elements数组与数组长度返回一个新数组。
            result.elements = Arrays.copyOf(elements, elements.length);//深度复制
            return result;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError();
        }
    }

源码分析： ArrayDeque类实现了Cloneable接口，可以通过super调用父类Object的clone()，克隆后result指向ArrayDeque队列。

6.参考资料

死磕 java集合之ArrayDeque源码分析
 ArrayDeque类的使用详解

三：栈Stack

1、栈的理解

栈（Stack）是一种受限的线性数据结构，所谓受限是指栈只暴露栈顶和栈底的操作，其底层是由数组实现的。栈的特性是先进后出，类似于手枪压弹，原理示意图如下：
在这里插入图片描述

2、Stack的继承关系

在这里插入图片描述

3、被弃用的Stack

3.1 被弃用的原因

从继承关系中，我们可以看到Stack的基本方法与底层实现，由于Vector是动态数组接口，其底层的实现是数组，因此，Stack的底层实现也是数组，且继承了Vector的公共方法。
从前文（简析Vector类）我们知道，Vector类具有动态扩容和随机访问的特性，因此，继承了Vector类的Stack也同样具有这些特性，这恰好违背了Stack数据结构的设计原理，正因为如此，Java中的Stack一直被认为是糟糕的实现，官方也将Stack标志为“弃用”（deprecated）。
综上所述，导致Stack糟糕实现的原因是Stack与Vector类的关系出现了错误，不应该是继承关系（is-a），而应是组合关系（has-a）。

3.2 如何替代

官方推荐使用Deque（双端队列）接口来实现Stack：

Deque<E> stack = new ArrayDeque<>();

虽然官方做出了推荐，但是我们仍然可以发现，Deque实现的Stack实质是一个双端队列，可以在队列的两端实现插入和删除操作，仍然破坏力了封装性，并不安全，可以看出这并不是一个完美的方法。
因此，在实际中更推荐大家再做一层封装，通过逻辑限定为只能一端操作插入和删除，形成一个真正的栈。

3.3 队列实现栈

用队列实现栈，只需要⼀个队列作为底层数据结构。
要实现的栈的API如下：


class MyStack {
	/** 添加元素到栈顶 */
	public void push(int x);
	/** 删除栈顶的元素并返回 */
	public int pop();
	/** 返回栈顶元素 */
	public int top();
	/** 判断栈是否为空 */
	public boolean empty();
}

先说 push API，直接将元素加⼊队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 top 查
看栈顶元素的话可以直接返回：


class MyStack {
	Queue<Integer> q = new LinkedList<>();
	int top_elem = 0;
	/** 添加元素到栈顶 */
	public void push(int x) {
		// x 是队列的队尾，是栈的栈顶
		q.offer(x);
		top_elem = x;
	}
	/** 返回栈顶元素 */
	public int top() {
		return top_elem;
	}
}

我们的底层数据结构是先进先出的队列，每次 pop 只能从队头取元素；但是栈是后进先出，也就是说 pop
API 要从队尾取元素：
在这里插入图片描述
解决⽅法简单粗暴，把队列前⾯的都取出来再加⼊队尾，让之前的队尾元素排到队头，这样就可以取出了：


/** 删除栈顶的元素并返回 */
public int pop() {
	int size = q.size();
	while (size > 1) {
		size--;
	}
	// 之前的队尾元素已经到了队头
	return q.poll();
}

这样实现还有⼀点⼩问题就是，原来的队尾元素被提到队头并删除了，但是 top_elem 变量没有更新，我们
还需要⼀点⼩修改：


/** 删除栈顶的元素并返回 */
public int pop() {
	int size = q.size();
	// 留下队尾 2 个元素
	while (size > 2) {
		q.offer(q.poll());
		size--;
	}
	// 记录新的队尾元素
	top_elem = q.peek();
	q.offer(q.poll());
	// 删除之前的队尾元素
	return q.poll();
}

最后，API empty 就很容易实现了，只要看底层的队列是否为空即可：


/** 判断栈是否为空 */
public boolean empty() {
	return q.isEmpty();
}

很明显，⽤队列实现栈的话，pop 操作时间复杂度是 O(N)，其他操作都是 O(1) 。

3.4 面试中的Stack

如果面试中关注的是算法和程序的逻辑，那么数据结构的使用就不是重点，但是如果能用Deque实现，那自然是更好，尤其是需要考察对Java原因的理解。

一：队列Queue

1：队列特性

阻塞和非阻塞

有界和无界

单向链表和双向链表

2：Java 队列接口继承图

3：队列常用方法

4：阻塞队列与非阻塞队列具体详解

非阻塞队列：

1、ConcurrentLinkedQueue

2、ConcurrentLinkedDeque

3、PriorityQueue

1、DelayQueue

2、LinkedTransferQueue

3、ArrayBlockingQueue

4、SynchronousQueue

5、PriorityBlockingQueue

二：双端队列Deque

Deque———ArrayDeque类详解

1.数据结构

2.类标题

3.字段

4.构造函数

5.方法分析

添加元素

6.参考资料

三：栈Stack

1、栈的理解

2、Stack的继承关系

3、被弃用的Stack

3.1 被弃用的原因

3.2 如何替代

3.3 队列实现栈

3.4 面试中的Stack