introduce
ArrayDeque is bidirectional queue, thread unsafe bidirectional queue, two-way queue length can be their own capacity, and the length of the need is the power to the power of 2, double side is mainly the head and tail ends can be inserted into the deletion and the retrieval, the implementation class implements the Deque interface, Deque interface provides a queue to implement two-way, The interface provides operations such as insert from head, insert from tail, get from head, get from tail, and delete. An ArrayDeque, by its name, uses arrays to store elements.
The class diagram
It is also clear from the class diagram that ArrayDeque inherits from the Deque interface and from the Queue interface. It also inherits from the Collection interface that iterators can be used to traverse collections.
Source code analysis
Before we look at the source code, we can ask ourselves a few questions. We have already seen that ArrayDeque uses array elements for storage. How do arrays control insertion from the head? How is it possible to insert elements from the head when an array is empty? And when there is an element in the array, such as a=[1,2,3], then there is an element in the array 0, how do we insert the element before the element with index 0? The length of an array is a power of two, right? Why does the length of an array have to be a power of two? Look at the source code analysis with this question in mind.
Field information
The head pointer points to the head of the data element, and the tail pointer points to the tail of the data element. The head pointer and tail pointer control whether the operation is performed on the head or the tail. Here is the field information in ArrayDeque:
/** * The element stored in the array. * /
transient Object[] elements; // non-private to simplify nested class access
/** * header pointer. * /
transient int head;
/** * tail pointer. * /
transient int tail;
/** * The default minimum size of the array. The length has to be a power of two. * /
private static final int MIN_INITIAL_CAPACITY = 8;
Copy the codeCalculateSize method
Is first of all we have to solve the first problem, the problem of the length of the array, the array length front said that must be a power of 2 to the power, but seeing the constructor can specify the length of the array, since you can specify the length of the array, the array length specified for 10, this number is not the power to the power of 2, actually we specify, though not the power to the power of 2, But ArrayDeque will do it for me internally, by adjusting the array length to a power of two. Let’s look at the ArrarDeque constructor:
// The default length is 16.
public ArrayDeque(a) {
elements = new Object[16];
}
/** * allocateElements is called when the array length is specified. * /
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/** * specifies the collection and initializes the size. * /
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
Copy the codeThe allocateElements () constructor calls allocateElements () to initialize an array and adjust its capacity to a power of 2.
/** * Initializes the array size and calls the calculateSize method to adjust the capacity size. * /
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
Copy the codeThe above method initializes array elements and needs to adjust the capacity before initialization. The actual method to adjust the capacity size is calculateSize method.
private static int calculateSize(int numElements) {
// Get the minimum initial capacity.
int initialCapacity = MIN_INITIAL_CAPACITY;
// If the capacity is greater than the minimum capacity, look for a value to the power of 2.
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
}
// Returns a power of 2.
return initialCapacity;
}
Copy the codeFor example, when we initialize ArrayDeque and specify array length 10, it will call calculateSize to calculate a power of 2 when it initializes the array size.
public static void main(String[] args) {
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(10);
}
Copy the code- At line 5, numElements >= initialCapacity is established, and 10>=8 will enter the if statement.
- When the program runs to line 6, initialCapacity = numElements and initialCapacity is set to 10, the binary representation of 10 is 1010.
- Program is running on the seventh row initialCapacity unsigned to the right one, 1010 no symbol to the right one is 0101101 | 0101 = 1111, decimal representation is 15.
- Program is running on the seventh row initialCapacity unsigned to the right one, 1111 no symbol to the right one is 1 | 0011 = 1111, 0011111 decimal representation is 15, continue is 15, when the program is running to the line 12, 15 to add 1 operation, is 16. So in this case 16 is going to be the power of 2 and return.
The whole idea is to change the highest number of digits to 1 for each move, thus changing all binary digits to 1. The resulting decimal value after 1 plus 1 is the value of 2 to the power of 2.
AddFirst method
So that’s the code logic that makes sure that the size of the array is a power of 2, very clever code design, what’s the advantage of the size of the array a power of 2? In fact, I can briefly describe here the advantage is that we can control the position of the pointer in the array, that is, we can solve the first problem, and then continue to analyze the contents of the array when the header is inserted, the source first source first:
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 codeInsert elements in the header. For example, if we look at the following code, first insert elements in the header, then insert elements in the tail, look at the overall insert process. This simple example shows why the array length is set to a power of 2.
public static void main(String[] args) {
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(10);
arrayDeque.addFirst(5);
arrayDeque.addLast(1);
arrayDeque.forEach(System.out::println);
}
Copy the codeThe default value of head and tail pointer head is 0. In this case, the contents of the array are as follows:
Elements [head = (head – 1) & (elements. Length-1)] = e; This line of code is used to expand the array only when the queue is full. Head ==tail indicates that the queue is full. Elements [head = (head – 1) & (elements. Length-1)] = e
- Head =head-1, head=0, then head-1 gets the value 15 (binary subtraction), 15 in binary: 1111
- Elements. Length-1, init size 10, calculateSize array size 16, 16-1=15, binary representation 1111
- 1111&1111 is still 1111, and the subscript of the array is 15.
Yi? And that gives us 15 instead of 0, right? What you might expect is that when you insert the header, when the array is empty, it will insert the element at index 0. It’s not. It will insert the element at index 15.
Inserted into the subscript for 15 place because, if we after inserting value 0 subscript position, when interpolation insert value through the head, found an array of head has no position, it will use an array to insert the tail, the head will point to the position of the tail, which is why the array to be set to a power of 2 to the power of reason, Head = (head – 1) & (elements. Length-1); Head = (head + 1) & (elements. Length-1);
Method AddLast
To return to the example above, we simply run addFirst and continue to run the addLast content, first loading the source code and then analyzing the source code:
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 codeElements [tail] = e; We can store the elements in the array and move the tail pointer.
Tail = (tail + 1) & (elements. Length-1) if the next tail node overlaps with the head node, the array is full and needs to be expanded as follows:
When a thread inserts a value into the ArrayDeque queue again, which is the tail value, tail will point to the head node. At this point, head and tail will overlap. After the overlap, expansion will be performed, as shown below:
ArrayDeque makes clever use of the head and tail of the array. To simplify, the head pointer needs to increase the head pointer by 1 when acquiring data. When the head pointer reaches the end of the array, it points to the head of the array to obtain data from the head of the array. When we get data from the tail pointer, we actually subtract 1 from the tail pointer and move forward. If we reach the head of the array, we point the tail pointer to the end of the array and look forward from the end. If we find the value is empty, the array is empty.
PollFirst method
Of course, ArrayDeque also has peekFirst and peekLast methods for retrieving data. These two simple methods are to get the corresponding pointer value, and I won’t repeat them here, but I will focus on pollFirst and pollLast methods.
public E pollFirst(a) {
// Get the header pointer.
int h = head;
@SuppressWarnings("unchecked")
// Get the value of the array element corresponding to the header pointer.
E result = (E) elements[h];
// Element is null if deque empty
// The array is empty.
if (result == null)
return null;
// Set the header pointer value to null.
elements[h] = null; // Must null out slot
/ / aha? This is what we guessed above, the next position of the head pointer.
head = (h + 1) & (elements.length - 1);
return result;
}
Copy the codeTo demonstrate what pollFirst looks like for the two elements we just inserted, the array element looks like this.
PollFirst; pollFirst; head=15, h=15, result=elements[15]=5; pollFirst;
PollLast method
Here we revert to inserting two elements as follows:
Take a look at the source information, as follows:
public E pollLast(a) {
// Find the position before the tail pointer.
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
// Get the tail element.
E result = (E) elements[t];
if (result == null)
return null;
// Set the tail element to null.
elements[t] = null;
// Adjust the tail pointer position.
tail = t;
return result;
}
Copy the codePollLast: int t = (tail-1) & (elements. Leng-1); pollLast: int t = (tail-1) & (elements. Elements [t] = null elements[t] = 11110000&1111 =0;
Other USES
RemoveFirst and removeLast call pollFist and pollLast, as well as pop and push. PollFist and pollFist are called internally by removeFirst and removeLast. I’m not going to explain them all here, the main methods are described above.
conclusion
-
An ArrayDeque is a two-way queue, and threads are not safe.
-
ArrayDeque is implemented based on arrays.
-
An ArrayDeque’s array length is a power of two.
-
Next and previous representations of Pointers:
- The location of the previous node of the header pointer :(head-1)&(elements. Length-1), and the location of the next node :(head+1)&(elements.
- Last node location of the tail pointer :(tail-1)&(elements. Length-1), next node location :(tail+1)&(elements.
- The previous node location :(i-1)&(elements. Length-1); the next node location :(I +1)&(elements. Length-1)
If you like, you can follow my wechat public account BattleHeart and push articles from time to time