java源码解读--queue

Queue接口

queue接口特点：可以模拟队列行为，即“先进先出”。

接口结构

queue接口继承了Collection接口，并增加了一些新方法

public interface Queue<E> extends Collection<E>{

	//将元素插入队列，成功返回true，失败抛异常
    boolean add(E e);
	//将元素插入队列，如果失败返回false
    boolean offer(E e);
	//移除并返回队列中的第一个元素，队列为空时，抛异常
    E remove();
	//移除并返回队列中的第一个元素，队列为空时，返回null
    E poll();
	//返回队列中第一个元素，但不移除，队列为空时，抛异常
    E element();
	//返回队列中第一个元素，但不移除，对列为空时，返回null
    E peek();

}

抽象类AbstractQueue

queue接口中，add与offer、remove与poll、element与peek，功能一致，只是对异常情况的处理不同。AbstractQueue源码中可以看出这些方法处理异常的方式。

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {

    protected AbstractQueue() {
    }

	//add底层调用offer，当offer失败返回false时，add方法抛出异常
    public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
	//remove底层调用poll，当poll返回null时，remove方法抛出异常 
    public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
	//element底层调用peek，当peek返回null时，element方法抛出异常
    public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
	//clear方法循环调用poll，直到返回为null
    public void clear() {
        while (poll() != null)
            ;
    }
	
    public boolean addAll(Collection<? extends E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

}

Deque接口

Deque是双端队列，底层由循环数组实现，其继承了Queue接口，并扩展了新特性。
Deque重写了Queue的全部方法，Stack、Collection的部分方法，并增加了对首尾元素处理的相关方法。

public interface Deque<E> extends Queue<E> {

    void addFirst(E e);

    void addLast(E e);

    boolean offerFirst(E e);

    boolean offerLast(E e);

    E removeFirst();

    E removeLast();

    E pollFirst();

    E pollLast();

    E getFirst();

    E getLast();

    E peekFirst();

    E peekLast();

    boolean removeFirstOccurrence(Object o);

    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***

    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();


    // *** Stack methods ***

    void push(E e);

    E pop();


    // *** Collection methods ***

    boolean remove(Object o);

    boolean contains(Object o);

    public int size();

    Iterator<E> iterator();

    Iterator<E> descendingIterator();

}

ArrayDeque

ArrayDeque不可以存取null元素，因为会根据某个位置是否为null来判断元素是否存在。
当作为栈使用时，性能比stack好，作为队列使用时，性能比linkedlist好

类定义

继承了AbstractCollection，实现了Deque接口

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

重要的成员变量

// 第一个元素的索引  
private transient int head;  
// 下个要添加元素的位置，为末尾元素的索引 + 1  
private transient int tail;

构造方法

//默认数组大小16
   public ArrayDeque() {
       elements = new Object[16];
   }
//传入数组大小
   public ArrayDeque(int numElements) {
//调整实际数组大小为大于传入值的最小的2的幂次
       allocateElements(numElements);
   }
//直接传入集合
   public ArrayDeque(Collection<? extends E> c) {
       allocateElements(c.size());
       addAll(c);
   }

调整数组大小

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 = (E[]) new Object[initialCapacity];  
}

add

   public void addFirst(E e) {
       if (e == null)
           throw new NullPointerException();
//因为elements.length是2的幂次，(head - 1) & (elements.length - 1)相当于求模操作
//head-1只可能为-1，-1&(elements.length - 1)=(elements.length - 1)
       elements[head = (head - 1) & (elements.length - 1)] = e;
       if (head == tail)
           doubleCapacity();
   }


   public void addLast(E e) {
       if (e == null)
           throw new NullPointerException();
       elements[tail] = e;
//与head操作类似，为了处理tail=length-1的情况
       if ( (tail = (tail + 1) & (elements.length - 1)) == head)
           doubleCapacity();
   }

   public boolean add(E e) {
       addLast(e);
       return true;
   }

   public boolean offerFirst(E e) {
       addFirst(e);
       return true;
   }

   public boolean offerLast(E e) {
       addLast(e);
       return true;
   }

remove

   public E removeFirst() {
       E x = pollFirst();
       if (x == null)
           throw new NoSuchElementException();
       return x;
   }

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

   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=0
       head = (h + 1) & (elements.length - 1);
       return result;
   }

   public E pollLast() {
//获取tail下标，处理tail=0的特殊情况，移除元素后tail=elements.length-1
       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;
   }

删除指定元素

需要遍历数组，时间复杂度较高

   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;
   }

   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;
   }

   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;

//i不在t和h之间
       if (front >= ((t - h) & mask))
           throw new ConcurrentModificationException();

       // Optimize for least element motion
       if (front < back) {
	// head X X i X X X X tail，head-i的元素大于i-tail元素个数
           if (h <= i) {
               System.arraycopy(elements, h, elements, h + 1, front);
           } else { // Wrap around
	// i X X X X tail X X 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 {
	// head X X X X i X X tail
           if (i < t) { // Copy the null tail as well
               System.arraycopy(elements, i + 1, elements, i, back);
               tail = t - 1;
           } else { // Wrap around
	// tail X X head X X X X 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;
       }

   private void checkInvariants() {
//tail没有元素
       assert elements[tail] == null;
//head和tail位置重合，队列为空，否则head、tail-1位置有元素
       assert head == tail ? elements[head] == null :
           (elements[head] != null &&
            elements[(tail - 1) & (elements.length - 1)] != null);
//head-1的位置没有元素。  
       assert elements[(head - 1) & (elements.length - 1)] == null;
   }

扩容

   private void doubleCapacity() {
//tail和head重合的时候进行扩容，此时tail在head左侧
       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到element数组末尾的元素
       System.arraycopy(elements, p, a, 0, r);
//在复制0到tail之间的元素
       System.arraycopy(elements, 0, a, r, p);
       elements = a;
       head = 0;
       tail = n;
   }