ArrayDeque
ArrayDeque is an implementation of the Deque interface that uses mutable arrays, so there is no capacity limit. At the same time, ArrayDeque is thread-unsafe and cannot be used in multithreaded environments without external synchronization.
ArrayDeque is a Deque implementation class that can be used as a Stack, which is more efficient than a Stack. It can also be used as a queue, which is more efficient than a LinkedList. Note that ArrayDeque does not support null values.
ArrayDeque met
Specification and inheritance
Again, the international convention is to look at ArrayDeque’s specification, which is often where you get confused, but first let’s look at its inheritance, just to get a sense of what it is
We can see that ArrayDeque has the function of a Queue by implementing a Deque interface. Since the Deque of ArrayDeque inherits the interface of Queue, ArrayDeque also has the function of Queue. Note that ArrayDeque is a two-way queue, and both sides of the queue can be added, deleted, or eject. So we can use a two-way queue as a Stack, and a LinkedList as a Stack.
/**
* Resizable-array implementation of the {@link Deque} interface. Array
* deques have no capacity restrictions; they grow as necessary to support
* usage. They are not thread-safe; in the absence of external
* synchronization, they do not support concurrent access by multiple threads.
* Null elements are prohibited. This class is likely to be faster than
* {@link Stack} when used as a stack, and faster than {@linkLinkedList} * When used as a queue. * Implements a Deque interface for mutable arrays, ArrayDeque has no capacity limit, capacity will be expanded on demand. Arraydeques are not thread-safe, they do not support concurrent access from multiple threads without external locking synchronization, and NULL values are not allowed. Arraydeques perform better than Stack classes when used as stacks. Queue performance is better than LinkedList * <p>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. * ArrayDeque's many operations except delete and traverse (which are listed above) have amortized time complexity at constant level * <p>The iterators returned by this class's {@code iterator} method are
* <i>fail-fast</i>: 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. * ArrayDeque iterator The iterators returned by the method are fail-fast (this has been explained many times, * <p>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: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*/
public class ArrayDeque<E> extends AbstractCollection<E>implements Deque<E>, Cloneable.Serializable
{
/** * Stores an array of elements in a queue. The size of the queue is the length of the array, which is always an exponential of 2
transient Object[] elements; // non-private to simplify nested class access
/** * The index of the element at the head of the deque (which is the * element that would be removed by remove() or pop()); Or an * arbitrary number equal to tail if the deque is empty
transient int head;
/** * the subscript of the element at the end of the queue */
transient int tail;
/** * The minimum capacity that we'll use for a newly created deque. * Must be a power of 2. */
private static final int MIN_INITIAL_CAPACITY = 8;
}
Copy the codeArrayDeque operates in the following ways. Later we will explain the source code implementation of some methods to figure out how ArrayDeque works
OfferFirst (E E) Add an element to the front of the array. OfferFirst (E E) add an element to the front of the array. OfferLast (E E) add an element to the front of the array. And returns whether 2 was added successfully. PollFirst () removes the first element and returns the value of the deleted element. PollFirst () removes the first element and returns the value of the deleted element. If the element is null, pollFirst() will return null. PollLast () removes the last element and returns the value of the deleted element. If null, pollLast() throws an exception to delete the last element and returns the value of the deleted element. RemoveFirstOccurrence (Object O) Removes the first occurrence of the specified element removeLastOccurrence(Object O) Removes the last occurrence of the specified element 3. GetFirst () gets the first element, getLast() gets the last element if not, and 4 if not. Add (E E) adds an element to the end of the queue. Offer (E E) adds an element to the end of the queue and returns whether it succeeded. Remove () removes the first element in the queue and returns the value of that element. Will throw an exception (in fact, the underlying invocation is removeFirst (), poll () to delete the first element in the queue, and returns the value of the element, if the element is null, the return null (actually called pollFirst ()) element () for the first element, An exception peek() is thrown to get the first element if not, if null 5 is returned. Push (E E) adds an element to the top of the stack. Pop (E E) removes the element at the top of the stack. If there is no element at the top of the stack, exception 6 is raised. DescendingIterator () retrieves the element number isEmpty() to determine whether the queue isEmpty. Iterator() iterator is descendingIterator(). ToArray () clear() Clear () Clone () Clone () a new queueCopy the codeArrayDeque source
A constructor
/** * Constructs an empty array deque with an initial capacity sufficient to hold 16 elements. * Constructs an empty array deque */ Constructs an empty array deque with an initial capacity sufficient to hold 16 elements
public ArrayDeque(a) {
elements = new Object[16];
}
/** * Constructs an empty array deque with an initial capacity * sufficient to hold the specified number of elements. * Creates a Deque of a specified size, large enough to hold a specified number of elements *@param numElements lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
// Create a Deque containing the specified collection elements
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
Copy the codeCan see no arguments structure created by default is an array of size of 16 to accommodate the element in the queue, but when we specify the capacity, and not directly create an array of a specified size, but to call a method, and we’re from its construction method can also get some information on the description of information, that is enough, So the proof has to be at least larger than what we specify, how big is that, and we’re going to look at this method.
/** * Allocates empty array to hold the given number of elements. * Creates an empty array to hold a specified number of elements *@param numElements the number of elements to hold
*/
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
Copy the codeWe see that this method calls another method calculateSize(numElements), whose argument is the integer we passed in, and returns the lowest exponential power of 2 greater than numElements by the following calculation
/** * The minimum capacity that we'll use for a newly created deque. * Must be a power of 2. */
private static final int MIN_INITIAL_CAPACITY = 8;
private static int calculateSize(int numElements) {
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;
}
Copy the codeThis also confirms the information in the class comment, which explains why the size of a queue is always an exponential of two, and we know that the minimum size of a queue is eight, right
AddFirst addLast and Add methods
We saw earlier in the class comment that Queue does not allow null values, and the reason for this is that all the methods have null-detection, because there are only a few methods that can add elements, and we can see that they all do determine whether the element is null, right
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
Copy the codeLet’s take a look at the implementation of addFirst. First we do a null check, and then we compute the head, which is where the head of the queue is. This calculation is a bit confusing. Head = (head – 1) & (elements. Length-1) calculates 15, so our head is the end of the array. So we know that next time the subscript of head is 15
And we actually saw this when we looked at Stack, where we thought that the top of the Stack should be the array subscript 0 or at least the left end of the array, but the top of the Stack is the right end of the array, because you don’t have to move the rest of the array after you pop the top of the Stack
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
Copy the codeWe see that the first line of the addLast method is NULL, and we know that tail is 0 by default, so we see that the end of the Queue is the header of the data. Then check whether tail and head are equal. If so, the queue is full and needs to be expanded
/**
* Inserts the specified element at the end of this deque.
* <p>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;
}
Copy the codeThen we see that the Add method actually calls the addLast method.
From addFirst and addLast(add) we know that the process of adding elements is a process from both sides to the middle. Now let’s simulate this process using a diagram
@Test
public void createQueue(a) {
ArrayDeque<String> brothers = new ArrayDeque<>(7);
// First insertion
brothers.addFirst("The boss");
brothers.addLast("Old.");
// Insert the second time
brothers.addFirst("The second");
brothers.addLast("The old seven");
// Insert for the third time
brothers.addFirst("Old");
brothers.addLast("Old six");
}
Copy the codeThere is a family of eight brothers to the mountain tiger today, as the saying goes, father and son soldiers, tiger brothers, father for a bowl of water, according to the strength of the brothers a pair of distribution, both for the sake of fairness and safety, if the old seven and the old eight a group, it does not know to the end is to feed the tiger or hit the tiger. But dad didn’t learn the data structure well, or the first and second arranged together.
After the third insert, tail=3 and head=4. If the next insert is the fourth insert, head will be equal to tail= 4 and expansion will be triggered.
@Test
public void createQueue(a) {
ArrayDeque<String> brothers = new ArrayDeque<>(7);
// First insertion
brothers.addFirst("The boss");
brothers.addLast("Old.");
// Insert the second time
brothers.addFirst("The second");
brothers.addLast("The old seven");
// Insert for the third time
brothers.addFirst("Old");
brothers.addLast("Old six");
// Insert the fourth time
brothers.addFirst("Old four");
// The expansion will be triggered when the old four is inserted
brothers.addLast("Property");
System.out.println(brothers);
}
Copy the code
Output [old four, old three, two, big eight, old seven, old six, old five]
If you’re curious, this output is a little odd, because it doesn’t print the array indices from small to large. Instead, we print from head to the last bit of the array, and then from subscript 0 to tail, assuming we describe the output using the result after the third insert
We print the data from left to right from the beginning of the head to the end of the array, which is the right half of the head. We print the data from left to right, which is 0 to tail, which is the left half of the head. So let’s think about why we’re doing this, and let’s look at how we access elements, okay
GetFirst and getLast methods
Let’s explain the getFirst and getLast methods for the following data
getFirst
/ * * *@throws NoSuchElementException {@inheritDoc} * /
public E getFirst(a) {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
Copy the codeSince head refers to the head of the current queue, use elements[head] to return the element in the head of the queue
getLast
/ * * *@throws NoSuchElementException {@inheritDoc} * /
public E getLast(a) {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
Copy the codeSince tail is the next element pointing to the tail of the current queue, elements[tail-1] is required to return the tail element of the queue.
@Test
public void createQueue(a) {
ArrayDeque<String> brothers = new ArrayDeque<>(7);
// First insertion
brothers.addFirst("The boss");
brothers.addLast("Old.");
// Insert the second time
brothers.addFirst("The second");
brothers.addLast("The old seven");
// Insert for the third time
brothers.addFirst("Old");
brothers.addLast("Old six");
// Insert the fourth time
brothers.addFirst("Old four");
brothers.addLast("Property");
System.out.println(brothers);
String laosi = brothers.getFirst();
String laowu = brothers.getLast();
System.out.println(laosi);
System.out.println(laowu);
System.out.println(brothers);
}
Copy the codeThe output
Old four, old three, old two, old eight, old seven, old six, old five, old four, old five, old four, old five, old four, old three, old two, old five, old eight, old seven, old six, old fiveCopy the codePollFirst and pollLast
The difference between poll and GET is whether or not to delete an element after it is retrieved
@Test
public void createQueue(a) {
ArrayDeque<String> brothers = new ArrayDeque<>(7);
// First insertion
brothers.addFirst("The boss");
brothers.addLast("Old.");
// Insert the second time
brothers.addFirst("The second");
brothers.addLast("The old seven");
// Insert for the third time
brothers.addFirst("Old");
brothers.addLast("Old six");
// Insert the fourth time
brothers.addFirst("Old four");
brothers.addLast("Property");
System.out.println(brothers);
String laosi = brothers.pollFirst();
String laowu = brothers.pollLast();
System.out.println(laosi);
System.out.println(laowu);
System.out.println(brothers);
}
Copy the codeThe output
Old four, old three, old two, old brother, old eight, old seven, old six, old five. Old four, old five.Copy the codeWe see that the pollFirst and pollLast methods also remove elements from the queue surface after they are accessed, so let’s look at the source implementation
pollFirst
public E pollFirst(a) {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
// Set to null to cut off and reference the object so that the garbage collector can reclaim it
elements[h] = null; // Must null out slot
// Move head to point to the next bit.
head = (h + 1) & (elements.length - 1);
return result;
}
Copy the codeThis method is basically the same as getFirst, except that the array no longer references the object by resetting the head and setting the previous head position to NULL
public E pollLast(a) {
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;
}
Copy the codeThe operation is basically the same as pollFirst
toArray
public Object[] toArray() {
return copyElements(new Object[size()]);
}
Copy the codeWe know that the underlying implementation of the queue is an array, so why provide a copyElements method that returns an array instead of returning an array directly? And that actually has to do with the design of the queue, because the toArray method returns us an ordered array from the queue to the end of the queue, whereas the array that stores the elements in an ArrayDeque is not ordered. For example, the following data
The toArray method should return something like this
@Test
public void createQueue(a) {
ArrayDeque<String> brothers = new ArrayDeque<>(7);
// First insertion
brothers.addFirst("The boss");
brothers.addLast("Old.");
// Insert the second time
brothers.addFirst("The second");
brothers.addLast("The old seven");
// Insert for the third time
brothers.addFirst("Old");
brothers.addLast("Old six");
// Insert the fourth time
brothers.addFirst("Old four");
brothers.addLast("Property");
System.out.println(brothers);
System.out.println(Arrays.toString(brothers.toArray()));
}
Copy the codeThe output
Old four, old three, old two, old eight, old seven, old six, old fiveCopy the codePrintln (brothers); system.out.println (brothers); And the System. The out. Println (Arrays. ToString (brothers. ToArray ())); It’s the same, so we can look at the implementation of toArray
/** * 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. * Here is a sentence, in order (from first to last element in the deque) in order from beginning to end *@return its argument
*/
private <T> T[] copyElements(T[] a) {
if (head < tail) {
System.arraycopy(elements, head, a, 0, size());
} else if (head > tail) {
int headPortionLen = elements.length - head;
// Copy the data to the right of head (left to right)
System.arraycopy(elements, head, a, 0, headPortionLen);
// Copy data to the left of tail (left to right)
System.arraycopy(elements, 0, a, headPortionLen, tail);
}
return a;
}
Copy the codeWe see that the elements in the queue are copied in two parts to preserve order. If (head
doubleCapacity
Many of the other methods are also simple to implement and will not be explained here. DoubleCapacity is the last method on the left. We know that when the head and tail are equal, we need to expand the capacity. How to expand the capacity is the following method.
/** * Doubles the capacity of this deque. Call only when full, i.e., * When head and tail have wrapped around to become equal. * When head and tail have wrapped around to become equal
private void doubleCapacity(a) {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
// bit element, double the capacity, negative if the int limit is exceeded and throw an exception
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
// Create new array
Object[] a = new Object[newCapacity];
// Copy the elements into the new array in two parts, but put the right part of the head before the left part of the tail
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
// Reset the variable
elements = a;
// Head is back to 0, and the next time we insert the element, we return to the highest index of the array, and we see that head is less than tail
head = 0;
tail = n;
}
Copy the codeWe see that the next time we insert an element, which in this case is the old five, it triggers the expansion
Let’s illustrate the process of expansion from the drawing
In fact, we saw that when we expanded the queue, we put the head of the queue to the left of the tail. We can see that the head is less than tail after copying, which is the toArray if (head < tail) judgment
private <T> T[] copyElements(T[] a) {
if (head < tail) {
System.arraycopy(elements, head, a, 0, size());
} else if (head > tail) {
int headPortionLen = elements.length - head;
// Copy the data to the right of head (left to right)
System.arraycopy(elements, head, a, 0, headPortionLen);
// Copy data to the left of tail (left to right)
System.arraycopy(elements, 0, a, headPortionLen, tail);
}
return a;
}
Copy the codeconclusion
Queue we’ve talked a lot about queues. Both linkedList-based queues and two-way queues are implemented based on linked lists at the bottom, so deletion (popup) does not involve data migration
ArrayDeque is designed with two ends in the middle to avoid data migration. When head and tail are equal, they need to be expanded.