1.ArrayDeque analysis
1.1 inheritance system
As can be seen from its name, it is a double ended Queue implemented by array. Compared with LinkedList, which is a double ended Queue implemented by linked list, ArrayDeque implements the Queue interface and is also a common class under Collection.
1.2 common methods
public interface Deque<E> extends Queue<E> {
// Add element to queue header
void addFirst(E e);
// Add element to end of queue
void addLast(E e);
// Add element to queue header
boolean offerFirst(E e);
// Add element to end of queue
boolean offerLast(E e);
// Remove element from queue header
E removeFirst();
// Remove element from end of queue
E removeLast();
// Remove element from queue header
E pollFirst();
// Remove element from end of queue
E pollLast();
// View queue header elements
E getFirst();
// View end of queue element
E getLast();
// View queue header elements
E peekFirst();
// View end of queue element
E peekLast();
// Removes the specified element from the queue header traversal backward
boolean removeFirstOccurrence(Object o);
// Removes the specified element from the end of the queue traversal forward
boolean removeLastOccurrence(Object o);
// ***Methods in queue***
// Add element, equal to addLast(e)
boolean add(E e);
// Add element, equal to offerLast(e)
boolean offer(E e);
// Remove element, equal to removeFirst()
E remove();
// Remove element, equal to pollFirst()
E poll();
// View element, equal to getFirst()
E element();
// View element, equal to peekFirst()
E peek();
// ***Stack method***
// Stack, equal to addFirst(e)
void push(E e);
// Out of stack, equal to removeFirst()
E pop();
// ***Methods in Collection***
// Delete the specified element, equal to removeFirstOccurrence(o)
boolean remove(Object o);
// Check whether an element is included
boolean contains(Object o);
// Number of elements
public int size();
// iterator
Iterator<E> iterator();
// reverse iterator
Iterator<E> descendingIterator();
}
2. Core structure
2.1 properties
//Underlying array
transient Object[] elements;
//Head pointer
transient int head;
//Tail pointer
transient int tail;
//The default minimum capacity. Note: the length of elements must be to the power of 2.
private static final int MIN_INITIAL_CAPACITY = 8;
2.2 constructor
- When the parameterless constructor is called, an array with a length of 16 is created by default.
- Call the constructor passing in the initial capacity n. when n is less than 8, an array with length of 8 will be initialized. When n is greater than or equal to 8, an array with a length < the power of the smallest 2 > greater than n will be initialized (for example, if 3 is passed in, it will be 8, if 9 is passed in, it will be 16, and if 16 is passed in, it will be 32)
/* 1
* The null parameter constructor initializes an array with a length of 16 at the bottom
*/
public ArrayDeque() {
elements = new Object[16];
}
/* 2
* Pass in the initial capacity. Note that the final capacity is greater than (not equal to) the power of the maximum 2 of numElements
* Then it will be created.
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/* 3
* Create an array with a len gt h < less than or equal to the power of the maximum 2 of c.size >
* Then add the elements in c to elements.
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
/
addAll(c);
}
allocateElements
//Construct an array with a len gt h < strictly greater than the power of the smallest 2 of numElements >
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
//Returns a power strictly greater than the smallest 2 of numElements (8 when numElements is less than 8)
private static int calculateSize(int numElements) {
//MIN_INITIAL_CAPACITY = 8
int initialCapacity = MIN_INITIAL_CAPACITY;
//When numElements is greater than or equal to 8, calculate the power of the smallest 2 greater than numElements
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
}
//Here, if numElements is less than 8, it directly returns 8
return initialCapacity;
}
3. Detailed explanation of core methods
3.1 joining the team
- There are two ways to join the queue, from the head of the queue or from the end of the queue;
- If the capacity is insufficient, it will be doubled directly;
- Make the head and tail pointers circulate in the array range by taking the module;
- X & (len - 1) = x% len, use & faster;
//Join the team from the head of the team
public void addFirst(E e) {
//Element is not allowed to be NULL
if (e == null)
throw new NullPointerException();
/*
* Because element Length must be the power of 2. The binary of power of 2-1 is a string of 1 from the low order, and the high order is 0
* Initially, head = 0, 0 - 1 = - 1, - 1 & 15 = 15, and then head = 15
* Next time 15 - 1 = 14, 14 & 15 = 14, head = 14
* In the next 14 - 1 = 13, 13 & 15 = 13, head = 13
* ......
* Eventually, when the array is not full, it loops back.
* That is, the head refers to the current team head element.
*/
elements[head = (head - 1) & (elements.length - 1)] = e;
//Tail points to the next position of the header element. Judge head == tail, that is, judge whether the array is full and needs to be expanded.
if (head == tail)
//As can be seen from the method name, the expansion is twice the length of the original array.
doubleCapacity();
}
// Join the team from the end of the team
public void addLast(E e) {
// null elements are not allowed
if (e == null)
throw new NullPointerException();
//Initially, the tail is 0 and directly enters the queue. At this time, the tail points to the next position of the header element entering the queue from the end of the queue.
elements[tail] = e;
/*
* head Points to the position of the team head element
* tail + 1 Point to the next element of the queue head and judge whether = = head, that is, judge whether the array is full.
* That is, whether to follow the logic of capacity expansion.
*/
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
3.2 capacity expansion
private void doubleCapacity() {
assert head == tail;
// Position of head pointer
int p = head;
// Array length
int n = elements.length;
// The distance from the head pointer to the end of the array
int r = n - p; // number of elements to the right of p
// The new length is twice the old length
int newCapacity = n << 1;
// Determine whether overflow
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
// New array
Object[] a = new Object[newCapacity];
// Copy the elements after the old array head to the new array
System.arraycopy(elements, p, a, 0, r);
// Copy the elements between the subscripts 0 and head of the old array to the new array
System.arraycopy(elements, 0, a, r, p);
// Assign to new array
elements = a;
// head points to 0 and tail points to the position represented by the length of the old array
head = 0;
tail = n;
}
Element migration diagram
3.3 departure
// Get out of the queue from the queue head
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
// Take the queue header element (the header refers to the header element)
E result = (E) elements[h];
// If the queue is empty, null is returned
if (result == null)
return null;
// Leave the queue header empty
elements[h] = null;
// The queue header pointer shifts one bit to the right
head = (h + 1) & (elements.length - 1);
// Returns the obtained element
return result;
}
// Out of line at the end of the queue
public E pollLast() {
// The tail pointer moves one bit to the left, because through addLast(), we can know that tail points to the next position of the header element
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
// Gets the element at the current tail pointer
E result = (E) elements[t];
// Returns null if the queue is empty
if (result == null)
return null;
// Dispose of the current tail pointer as null
elements[t] = null;
// Tail points to the new tail pointer
tail = t;
// Returns the obtained element
return result;
}
3.4 use as stack
//Head in the team
public void push(E e) {
addFirst(e);
}
//Head out of the team
public E pop() {
//pollFirst() is still called
return removeFirst();
}
4. Summary
(1) ArrayDeque is a double ended queue implemented in array mode;
(2) ArrayDeque's entry and exit is realized by recycling the array through the head and tail pointers;
(3) ArrayDeque will be expanded when the capacity is insufficient, and the capacity will be doubled each time
(4) ArrayDeque can be directly used as a stack;
Double ended queue and double queue
Double ended queue and double queue?
- Deque refers to a queue in which both ends of the queue can enter and exit elements, in which real elements are stored.
- Dual Queue refers to a queue with two purposes. The nodes in it are divided into data nodes and non data nodes. It is the data structure used by LinkedTransferQueue.