ArrayDeque源码解析

ArrayDeque源码解析

ArrayDeque实现了Deque接口，既可以看作栈，也可以用作队列，采用循环数组实现，如果head==tail，则扩容为之前的2倍

数据结构

transient Object[] elements;
transient int head;
transient int tail;

构造函数

public ArrayDeque() {
    elements = new Object[16];
}

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

private static int calculateSize(int numElements) { // 根据给定的数字，计算一个刚好比它大的2次幂
    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;
}

private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

addFirst()、addLast()

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    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;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        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;
}

pollFirst()、pollLast()

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

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

peekFirst()、peekLast()

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

public E peekLast() {
    return (E) elements[(tail - 1) & (elements.length - 1)];
}

栈操作

public E peek() {
    return peekFirst();
}

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

队列操作

public boolean offer(E e) {
    return offerLast(e);
}

public E poll() {
    return pollFirst();
}

public E peek() {
    return peekFirst();
}