文章目录

• 概述
• ArrayDeque基础知识
• • ArrayDeque内部结构
  • ArrayDeque的构造方法
  • ArrayDeque的扩容操作
• ArrayDeque常用方法
• • 将ArrayDeque作为双端队列使用时
  • • public void addFirst(E e)
    • public void addLast(E e)
    • public boolean offerFirst(E e)
    • public boolean offerLast(E e)
    • public E pollFirst()
    • public E pollLast()
    • public E removeFirst()
    • public E removeLast()
    • public E getFirst()
    • public E getLast()
    • public E peekFirst()
    • public E peekLast()
  • 将ArrayDeque作为队列使用时
  • • public boolean add(E e)
    • public boolean offer(E e)
    • public E remove()
    • public E poll()
    • public E element()
    • public E peek()
  • 将ArrayDeque作为栈使用时
  • • public void push(E e)
    • public E pop()
  • 其他方法
  • • public int size()
    • public boolean isEmpty()
    • public boolean contains(Object o)
    • public void clear()
    • public Object[] toArray()
    • public ArrayDeque clone()

概述

java.util.ArrayDeque是Queue和Deque接口的基础集合。它的继承实现关系如下：

public class ArrayDeque extends AbstractCollectionimplements Deque, Cloneable, Serializable

ArrayDeque继承至AbstractCollection并实现了Deque, Cloneable, Serializable接口，支持可复制以及序列化操作。

ArrayDeque集合是一个基于可循环双指针数组（可扩容）结构实现的双端队列，它既有队列、双端队列的特点，又有栈结构的特点，可用来代替Stack集合进行栈结构的操作。

ArrayDeque基础知识

ArrayDeque内部结构

ArrayDeque的内部结构主要是一个数组，该数组结构是一种可循环使用的数组结构，称为循环数组。

循环数组是一个固定大小的数组，并定义了一个动态的有效数据范围（有限范围小于数组固定长度），只有在有效范围内的数据对象才能被读写，且该有效范围不受数组的头尾限制。

实现中，循环数组定义为elements，并使用名为head、tail的两个属性表示动态的有效数据：

• head属性用于标识下一次进行移除操作的数据对象索引位（队列头部索引为）；
• tail属性用于标识下一次进行添加操作的数据对象索引位（队列尾部索引为）。

当tail属性指向数组的所有一个索引位并进行下一次添加操作时，数组不一定进行扩容操作，而是：tail属性重新从当前数组的0号索引位开始，循环利用有限数据范围外的数组索引位存储新的数据对象。

ArrayDeque的构造方法

1. 构造一个空的ArrayDeque，初始容量为16。

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

2. 构造一个空的ArrayDeque，初始容量为指定大小numElements。

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

3. 构造一个包含指定集合元素的ArrayDeque

    public ArrayDeque(Collection c) {allocateElements(c.size());addAll(c);}public boolean addAll(Collection c) {boolean modified = false;for (E e : c)if (add(e))modified = true;return modified;}

ArrayDeque的扩容操作

ArrayDeque的扩容操作包括以下两步：

1. 根据当前容量大小计算新的容量。
   当扩容前的容量较小时，按照扩容前容量值的1倍计算增量值；当扩容前的容量较大时（超过64），按照扩容前容量值的50%计算增量值。
2. 按照计算得到的扩容增量值使用System.arraycopy方法进行扩容。

    private void doubleCapacity() {assert head == tail;int p = head;int n = elements.length;int r = n - p; // number of elements to the right of pint 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;}

ArrayDeque常用方法

将ArrayDeque作为双端队列使用时

public void addFirst(E e)

在此deque头部插入指定的元素。

    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)

在此deque尾部插入指定的元素。

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

public boolean offerFirst(E e)

在此deque头部插入指定的元素。

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

public boolean offerLast(E e)

在此deque尾部插入指定的元素。

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

public E pollFirst()

检索并删除此deque的第一个元素，如果此deque为空，则返回 null 。

    public E pollFirst() {int h = head;@SuppressWarnings("unchecked")E result = (E) elements[h];// Element is null if deque emptyif (result == null)return null;elements[h] = null;     // Must null out slothead = (h + 1) & (elements.length - 1);return result;}

public E pollLast()

检索并删除此deque的最后一个元素，如果此deque为空，则返回 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;}

public E removeFirst()

检索并删除此deque的第一个元素。 此方法与pollFirst不同之处在于，如果此deque为空，它将抛出异常。

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

public E removeLast()

检索并删除此deque的最后一个元素。 此方法与pollLast不同之处在于，如果此deque为空，它将抛出异常。

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

public E getFirst()

检索但不删除此deque的第一个元素，如果此deque为空，则抛出异常。

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

public E getLast()

检索但不删除此deque的最后一个元素，如果此deque为空，则抛出异常。

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

public E peekFirst()

检索但不删除此deque的第一个元素，如果此deque为空，则返回 null 。

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

public E peekLast()

检索但不删除此deque的最后一个元素，如果此deque为空，则返回 null 。

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

将ArrayDeque作为队列使用时

public boolean add(E e)

在此deque的末尾插入指定的元素。

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

public boolean offer(E e)

在此deque的末尾插入指定的元素。

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

public E remove()

检索并删除由此deque的头部元素。 如果此deque为空，它将抛出异常。

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

public E poll()

检索并删除由此deque的头部元素。 如果此deque为空，返回null。

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

public E element()

检索但不删除由此deque的头部元素。 如果此deque为空，它将抛出异常。

    public E element() {return getFirst();}

public E peek()

检索但不删除由此deque的头部元素。 如果此deque为空，返回null。

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

将ArrayDeque作为栈使用时

public void push(E e)

入栈

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

public E pop()

出栈

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

其他方法

public int size()

返回此deque中的元素数。

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

public boolean isEmpty()

判断此deque是否为空。

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

public boolean contains(Object o)

如果此deque包含指定的元素，则返回true 。

    public boolean contains(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))return true;i = (i + 1) & mask;}return false;}

public void clear()

清空

    public void clear() {int h = head;int t = tail;if (h != t) { // clear all cellshead = tail = 0;int i = h;int mask = elements.length - 1;do {elements[i] = null;i = (i + 1) & mask;} while (i != t);}}

public Object[] toArray()

返回一个包含此deque中所有元素的数组（从第一个到最后一个元素）。

    public Object[] toArray() {return copyElements(new Object[size()]);}

public ArrayDeque clone()

返回此deque的副本。

    public ArrayDeque clone() {try {@SuppressWarnings("unchecked")ArrayDeque result = (ArrayDeque) super.clone();result.elements = Arrays.copyOf(elements, elements.length);return result;} catch (CloneNotSupportedException e) {throw new AssertionError();}}