Most {@code ArrayDeque} operations run in amortized constant time. * Exceptions include * {@link #remove(Object) remove}, * {@link #removeFirstOccurrence removeFirstOccurrence}, * {@link #removeLastOccurrence removeLastOccurrence}, * {@link #contains contains}, * {@link #iterator iterator.remove()}, * and the bulk operations, all of which run in linear time. * *
The iterators returned by this class's {@link #iterator() iterator} * method are fail-fast: If the deque is modified at any time after * the iterator is created, in any way except through the iterator's own * {@code remove} method, the iterator will generally throw a {@link * ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the * future. * *
Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw {@code ConcurrentModificationException} on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs. * *
This class and its iterator implement all of the * optional methods of the {@link Collection} and {@link * Iterator} interfaces. * *
This class is a member of the
*
* Java Collections Framework.
*
* @author Josh Bloch and Doug Lea
* @param This method is equivalent to {@link #add}.
*
* @param e the element to add
* @throws NullPointerException if the specified element is null
*/
public void addLast(E e) {
// checkInvariants();
Objects.requireNonNull(e);
Object[] elements;
int capacity;
final int s;
if ((s = size) == (capacity = (elements = this.elements).length)) {
grow(1);
capacity = (elements = this.elements).length;
}
elements[add(head, s, capacity)] = e;
size = s + 1;
// checkInvariants();
}
/**
* Adds all of the elements in the specified collection at the end
* of this deque, as if by calling {@link #addLast} on each one,
* in the order that they are returned by the collection's
* iterator.
*
* @param c the elements to be inserted into this deque
* @return {@code true} if this deque changed as a result of the call
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
public boolean addAll(Collection c) {
final int s = size, needed = c.size() - (elements.length - s);
if (needed > 0)
grow(needed);
c.forEach((e) -> addLast(e));
// checkInvariants();
return size > s;
}
/**
* Inserts the specified element at the front of this deque.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Deque#offerFirst})
* @throws NullPointerException if the specified element is null
*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* Inserts the specified element at the end of this deque.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Deque#offerLast})
* @throws NullPointerException if the specified element is null
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
// checkInvariants();
E e = pollFirst();
if (e == null)
throw new NoSuchElementException();
return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeLast() {
// checkInvariants();
E e = pollLast();
if (e == null)
throw new NoSuchElementException();
return e;
}
public E pollFirst() {
// checkInvariants();
int s, h;
if ((s = size) == 0)
return null;
final Object[] elements = this.elements;
@SuppressWarnings("unchecked") E e = (E) elements[h = head];
elements[h] = null;
if (++h >= elements.length) h = 0;
head = h;
size = s - 1;
return e;
}
public E pollLast() {
// checkInvariants();
final int s, tail;
if ((s = size) == 0)
return null;
final Object[] elements = this.elements;
@SuppressWarnings("unchecked")
E e = (E) elements[tail = add(head, s - 1, elements.length)];
elements[tail] = null;
size = s - 1;
return e;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getFirst() {
// checkInvariants();
if (size == 0) throw new NoSuchElementException();
return elementAt(head);
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getLast() {
// checkInvariants();
if (size == 0) throw new NoSuchElementException();
return elementAt(tail());
}
public E peekFirst() {
// checkInvariants();
return (size == 0) ? null : elementAt(head);
}
public E peekLast() {
// checkInvariants();
return (size == 0) ? null : elementAt(tail());
}
/**
* Removes the first occurrence of the specified element in this
* deque (when traversing the deque from head to tail).
* If the deque does not contain the element, it is unchanged.
* More formally, removes the first element {@code e} such that
* {@code o.equals(e)} (if such an element exists).
* Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
* @param o element to be removed from this deque, if present
* @return {@code true} if the deque contained the specified element
*/
public boolean removeFirstOccurrence(Object o) {
if (o != null) {
final Object[] elements = this.elements;
final int capacity = elements.length;
int from, end, to, leftover;
leftover = (end = (from = head) + size)
- (to = (capacity - end >= 0) ? end : capacity);
for (;; from = 0, to = leftover, leftover = 0) {
for (int i = from; i < to; i++)
if (o.equals(elements[i])) {
delete(i);
return true;
}
if (leftover == 0) break;
}
}
return false;
}
/**
* Removes the last occurrence of the specified element in this
* deque (when traversing the deque from head to tail).
* If the deque does not contain the element, it is unchanged.
* More formally, removes the last element {@code e} such that
* {@code o.equals(e)} (if such an element exists).
* Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
* @param o element to be removed from this deque, if present
* @return {@code true} if the deque contained the specified element
*/
public boolean removeLastOccurrence(Object o) {
if (o != null) {
final Object[] elements = this.elements;
final int capacity = elements.length;
int from, to, end, leftover;
leftover = (to = ((end = (from = tail()) - size) >= -1) ? end : -1) - end;
for (;; from = capacity - 1, to = capacity - 1 - leftover, leftover = 0) {
for (int i = from; i > to; i--)
if (o.equals(elements[i])) {
delete(i);
return true;
}
if (leftover == 0) break;
}
}
return false;
}
// *** Queue methods ***
/**
* Inserts the specified element at the end of this deque.
*
* This method is equivalent to {@link #addLast}.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Collection#add})
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
addLast(e);
return true;
}
/**
* Inserts the specified element at the end of this deque.
*
* This method is equivalent to {@link #offerLast}.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Queue#offer})
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
return offerLast(e);
}
/**
* Retrieves and removes the head of the queue represented by this deque.
*
* This method differs from {@link #poll poll} only in that it throws an
* exception if this deque is empty.
*
* This method is equivalent to {@link #removeFirst}.
*
* @return the head of the queue represented by this deque
* @throws NoSuchElementException {@inheritDoc}
*/
public E remove() {
return removeFirst();
}
/**
* Retrieves and removes the head of the queue represented by this deque
* (in other words, the first element of this deque), or returns
* {@code null} if this deque is empty.
*
* This method is equivalent to {@link #pollFirst}.
*
* @return the head of the queue represented by this deque, or
* {@code null} if this deque is empty
*/
public E poll() {
return pollFirst();
}
/**
* Retrieves, but does not remove, the head of the queue represented by
* this deque. This method differs from {@link #peek peek} only in
* that it throws an exception if this deque is empty.
*
* This method is equivalent to {@link #getFirst}.
*
* @return the head of the queue represented by this deque
* @throws NoSuchElementException {@inheritDoc}
*/
public E element() {
return getFirst();
}
/**
* Retrieves, but does not remove, the head of the queue represented by
* this deque, or returns {@code null} if this deque is empty.
*
* This method is equivalent to {@link #peekFirst}.
*
* @return the head of the queue represented by this deque, or
* {@code null} if this deque is empty
*/
public E peek() {
return peekFirst();
}
// *** Stack methods ***
/**
* Pushes an element onto the stack represented by this deque. In other
* words, inserts the element at the front of this deque.
*
* This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @throws NullPointerException if the specified element is null
*/
public void push(E e) {
addFirst(e);
}
/**
* Pops an element from the stack represented by this deque. In other
* words, removes and returns the first element of this deque.
*
* This method is equivalent to {@link #removeFirst()}.
*
* @return the element at the front of this deque (which is the top
* of the stack represented by this deque)
* @throws NoSuchElementException {@inheritDoc}
*/
public E pop() {
return removeFirst();
}
/**
* Removes the element at the specified position in the elements array.
* This can result in forward or backwards motion of array elements.
* We optimize for least element motion.
*
* This method is called delete rather than remove to emphasize
* that its semantics differ from those of {@link List#remove(int)}.
*
* @return true if elements moved backwards
*/
boolean delete(int i) {
// checkInvariants();
final Object[] elements = this.elements;
final int capacity = elements.length;
final int h = head;
int front; // number of elements before to-be-deleted elt
if ((front = i - h) < 0) front += capacity;
final int back = size - front - 1; // number of elements after
if (front < back) {
// move front elements forwards
if (h <= i) {
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
System.arraycopy(elements, 0, elements, 1, i);
elements[0] = elements[capacity - 1];
System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
}
elements[h] = null;
if ((head = (h + 1)) >= capacity) head = 0;
size--;
// checkInvariants();
return false;
} else {
// move back elements backwards
int tail = tail();
if (i <= tail) {
System.arraycopy(elements, i + 1, elements, i, back);
} else { // Wrap around
int firstLeg = capacity - (i + 1);
System.arraycopy(elements, i + 1, elements, i, firstLeg);
elements[capacity - 1] = elements[0];
System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
}
elements[tail] = null;
size--;
// checkInvariants();
return true;
}
}
// *** Collection Methods ***
/**
* Returns the number of elements in this deque.
*
* @return the number of elements in this deque
*/
public int size() {
return size;
}
/**
* Returns {@code true} if this deque contains no elements.
*
* @return {@code true} if this deque contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns an iterator over the elements in this deque. The elements
* will be ordered from first (head) to last (tail). This is the same
* order that elements would be dequeued (via successive calls to
* {@link #remove} or popped (via successive calls to {@link #pop}).
*
* @return an iterator over the elements in this deque
*/
public Iterator The {@code Spliterator} reports {@link Spliterator#SIZED},
* {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
* {@link Spliterator#NONNULL}. Overriding implementations should document
* the reporting of additional characteristic values.
*
* @return a {@code Spliterator} over the elements in this deque
* @since 1.8
*/
public Spliterator This method is equivalent to {@link #removeFirstOccurrence(Object)}.
*
* @param o element to be removed from this deque, if present
* @return {@code true} if this deque contained the specified element
*/
public boolean remove(Object o) {
return removeFirstOccurrence(o);
}
/**
* Removes all of the elements from this deque.
* The deque will be empty after this call returns.
*/
public void clear() {
clearSlice(elements, head, size);
size = head = 0;
// checkInvariants();
}
/**
* Nulls out size elements, starting at head.
*/
private static void clearSlice(Object[] elements, int head, int size) {
final int capacity = elements.length, end = head + size;
final int leg = (capacity - end >= 0) ? end : capacity;
Arrays.fill(elements, head, leg, null);
if (leg != end)
Arrays.fill(elements, 0, end - capacity, null);
}
/**
* Returns an array containing all of the elements in this deque
* in proper sequence (from first to last element).
*
* The returned array will be "safe" in that no references to it are
* maintained by this deque. (In other words, this method must allocate
* a new array). The caller is thus free to modify the returned array.
*
* This method acts as bridge between array-based and collection-based
* APIs.
*
* @return an array containing all of the elements in this deque
*/
public Object[] toArray() {
return toArray(Object[].class);
}
private If this deque fits in the specified array with room to spare
* (i.e., the array has more elements than this deque), the element in
* the array immediately following the end of the deque is set to
* {@code null}.
*
* Like the {@link #toArray()} method, this method acts as bridge between
* array-based and collection-based APIs. Further, this method allows
* precise control over the runtime type of the output array, and may,
* under certain circumstances, be used to save allocation costs.
*
* Suppose {@code x} is a deque known to contain only strings.
* The following code can be used to dump the deque into a newly
* allocated array of {@code String}:
*
* {@code String[] y = x.toArray(new String[0]);}
*
* Note that {@code toArray(new Object[0])} is identical in function to
* {@code toArray()}.
*
* @param a the array into which the elements of the deque are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose
* @return an array containing all of the elements in this deque
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this deque
* @throws NullPointerException if the specified array is null
*/
@SuppressWarnings("unchecked")
public