Java源码刨析之ArrayDeque

Java中的ArrayDeque是一种基于动态数组的双端队列数据结构。本篇文章将与读者一起深入分析Java中ArrayDeque的源代码，从中学习这种数据结构的实现原理。

容量扩充

由于使用动态数组来存储队列中的元素，因此在添加元素时，需要判断是否需要扩展数组的容量。容量扩充的代码实现如下：

private void doubleCapacity() {
    int newCapacity = elements.length << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] newArray = new Object[newCapacity];
    int headN = elements.length - head;
    System.arraycopy(elements, head, newArray, 0, headN);
    System.arraycopy(elements, 0, newArray, headN, head);
    elements = newArray;
    head = 0;
    tail = size;
}

这段代码中首先将数组容量扩展为原来的两倍，然后使用System类的arraycopy()方法将原数组中从head位置开始到末尾的元素拷贝到新的数组的开头，将原数组中从0位置到head位置的元素拷贝到新的数组中从headN位置开始的位置，最后再改变head和tail的值，以确定队列的范围和队列大小。

入队操作

队列的入队操作代码如下：

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

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ((tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
    size++;
}

这段代码首先将新元素添加到队列的尾部，并通过位运算的方式取得新的tail值。然后检查队列是否已满，如果满了就执行容量扩充操作。

出队操作

队列的出队操作代码如下：

public E removeFirst() {
    E x = pollFirst();
    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 = (h + 1) & (elements.length - 1);
    size--;
    return result;
}

这段代码首先调用了pollFirst()方法获取队列中第一个元素，并返回该元素的值。如果该元素为null，则抛出NoSuchElementException异常。最后还需要将head的值加1，并将队列大小减1。

示例说明

下面以两条示例说明ArrayDeque的使用。

示例1：正向遍历

ArrayDeque<String> deque = new ArrayDeque<>();
deque.add("Java");
deque.add("is");
deque.add("awesome");

for(String str : deque) {
    System.out.println(str);
}

输出结果：
Java
is
awesome

该示例首先创建了一个String类型的ArrayDeque对象，在该对象中添加了三个元素。然后使用for循环遍历该队列，依次打印出队列中的每个元素。

示例2：反向遍历

ArrayDeque<String> deque = new ArrayDeque<>();
deque.push("Java");
deque.push("is");
deque.push("awesome");

Iterator<String> iterator = deque.descendingIterator();

while(iterator.hasNext()) {
    System.out.println(iterator.next());
}

输出结果：
awesome
is
Java

该示例与示例1类似，创建了一个String类型的ArrayDeque对象，并在该对象中添加了三个元素。不同之处在于使用push()方法将元素添加到队列的头部。接着使用迭代器将队列反向遍历，并依次打印出所有元素。