| Methods Summary |
|---|
| public boolean | add(E e)Inserts the specified element at the end of this deque.
This method is equivalent to {@link #addLast}.
addLast(e);
return true;
|
| public void | addFirst(E e)Inserts the specified element at the front of this deque.
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
|
| public void | addLast(E e)Inserts the specified element at the end of this deque.
This method is equivalent to {@link #add}.
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
|
| private void | allocateElements(int numElements)Allocate empty array to hold the given number of elements.
// ****** Array allocation and resizing utilities ******
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
}
elements = (E[]) new Object[initialCapacity];
|
| private void | checkInvariants()
assert elements[tail] == null;
assert head == tail ? elements[head] == null :
(elements[head] != null &&
elements[(tail - 1) & (elements.length - 1)] != null);
assert elements[(head - 1) & (elements.length - 1)] == null;
|
| public void | clear()Removes all of the elements from this deque.
The deque will be empty after this call returns.
int h = head;
int t = tail;
if (h != t) { // clear all cells
head = tail = 0;
int i = h;
int mask = elements.length - 1;
do {
elements[i] = null;
i = (i + 1) & mask;
} while (i != t);
}
|
| public java.util.ArrayDeque | clone()Returns a copy of this deque.
try {
ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
result.elements = Arrays.copyOf(elements, elements.length);
return result;
} catch (CloneNotSupportedException e) {
throw new AssertionError();
}
|
| public boolean | contains(java.lang.Object o)Returns true if this deque contains the specified element.
More formally, returns true if and only if this deque contains
at least one element e such that o.equals(e).
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
E x;
while ( (x = elements[i]) != null) {
if (o.equals(x))
return true;
i = (i + 1) & mask;
}
return false;
|
| private T[] | copyElements(T[] a)Copies the elements from our element array into the specified array,
in order (from first to last element in the deque). It is assumed
that the array is large enough to hold all elements in the deque.
if (head < tail) {
System.arraycopy(elements, head, a, 0, size());
} else if (head > tail) {
int headPortionLen = elements.length - head;
System.arraycopy(elements, head, a, 0, headPortionLen);
System.arraycopy(elements, 0, a, headPortionLen, tail);
}
return a;
|
| private boolean | delete(int i)Removes the element at the specified position in the elements array,
adjusting head and tail as necessary. This can result in motion of
elements backwards or forwards in the array.
This method is called delete rather than remove to emphasize
that its semantics differ from those of {@link List#remove(int)}.
checkInvariants();
final E[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
final int front = (i - h) & mask;
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
if (front < back) {
if (h <= i) {
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
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 {
if (i < t) { // Copy the null tail as well
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
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;
}
|
| public java.util.Iterator | descendingIterator()
return new DescendingIterator();
|
| private void | doubleCapacity()Double the capacity of this deque. Call only when full, i.e.,
when head and tail have wrapped around to become equal.
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 = (E[])a;
head = 0;
tail = n;
|
| public E | element()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 getFirst();
|
| public E | getFirst()
E x = elements[head];
if (x == null)
throw new NoSuchElementException();
return x;
|
| public E | getLast()
E x = elements[(tail - 1) & (elements.length - 1)];
if (x == null)
throw new NoSuchElementException();
return x;
|
| public boolean | isEmpty()Returns true if this deque contains no elements.
return head == tail;
|
| public java.util.Iterator | iterator()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 new DeqIterator();
|
| public boolean | offer(E e)Inserts the specified element at the end of this deque.
This method is equivalent to {@link #offerLast}.
return offerLast(e);
|
| public boolean | offerFirst(E e)Inserts the specified element at the front of this deque.
addFirst(e);
return true;
|
| public boolean | offerLast(E e)Inserts the specified element at the end of this deque.
addLast(e);
return true;
|
| public E | peek()Retrieves, but does not remove, the head of the queue represented by
this deque, or returns null if this deque is empty.
This method is equivalent to {@link #peekFirst}.
return peekFirst();
|
| public E | peekFirst()
return elements[head]; // elements[head] is null if deque empty
|
| public E | peekLast()
return elements[(tail - 1) & (elements.length - 1)];
|
| public E | poll()Retrieves and removes the head of the queue represented by this deque
(in other words, the first element of this deque), or returns
null if this deque is empty.
This method is equivalent to {@link #pollFirst}.
return pollFirst();
|
| public E | pollFirst()
int h = head;
E result = 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);
E result = elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
|
| public E | pop()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 removeFirst();
|
| public void | push(E e)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}.
addFirst(e);
|
| private void | readObject(java.io.ObjectInputStream s)Deserialize this deque.
s.defaultReadObject();
// Read in size and allocate array
int size = s.readInt();
allocateElements(size);
head = 0;
tail = size;
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
elements[i] = (E)s.readObject();
|
| public E | remove()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 removeFirst();
|
| public boolean | remove(java.lang.Object o)Removes a single instance of the specified element from this deque.
If the deque does not contain the element, it is unchanged.
More formally, removes the first element e such that
o.equals(e) (if such an element exists).
Returns true if this deque contained the specified element
(or equivalently, if this deque changed as a result of the call).
This method is equivalent to {@link #removeFirstOccurrence}.
return removeFirstOccurrence(o);
|
| public E | removeFirst()
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
|
| public boolean | removeFirstOccurrence(java.lang.Object o)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 e such that
o.equals(e) (if such an element exists).
Returns true if this deque contained the specified element
(or equivalently, if this deque changed as a result of the call).
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
E x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
|
| public E | removeLast()
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
|
| public boolean | removeLastOccurrence(java.lang.Object o)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 e such that
o.equals(e) (if such an element exists).
Returns true if this deque contained the specified element
(or equivalently, if this deque changed as a result of the call).
if (o == null)
return false;
int mask = elements.length - 1;
int i = (tail - 1) & mask;
E x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i - 1) & mask;
}
return false;
|
| public int | size()Returns the number of elements in this deque.
return (tail - head) & (elements.length - 1);
|
| public java.lang.Object[] | toArray()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 copyElements(new Object[size()]);
|
| public T[] | toArray(T[] a)Returns an array containing all of the elements in this deque in
proper sequence (from first to last element); the runtime type of the
returned array is that of the specified array. If the deque fits in
the specified array, it is returned therein. Otherwise, a new array
is allocated with the runtime type of the specified array and the
size of this deque.
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
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 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 String:
String[] y = x.toArray(new String[0]);
Note that toArray(new Object[0]) is identical in function to
toArray().
int size = size();
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
copyElements(a);
if (a.length > size)
a[size] = null;
return a;
|
| private void | writeObject(java.io.ObjectOutputStream s)Serialize this deque.
s.defaultWriteObject();
// Write out size
s.writeInt(size());
// Write out elements in order.
int mask = elements.length - 1;
for (int i = head; i != tail; i = (i + 1) & mask)
s.writeObject(elements[i]);
|
