The problem

(1) What is a double-endian queue?

(2) How ArrayDeque implements a double-endian queue?

(3) Is ArrayDeque thread safe?

(4) Is ArrayDeque bounded?

Introduction to the

A double-endian queue is a special queue in which both ends can get in and out of elements, hence its name.

An ArrayDeque is a two-endian queue implemented as an array that is not thread-safe.

Inheritance system

From the inheritance architecture, ArrayDeque implements the Deque interface, which is an enhancement of Queue, inherited from Queue.


public interface Deque<E> extends Queue<E> {
    // Add an element to the queue header
    void addFirst(E e);
    // Add elements to the end of the queue
    void addLast(E e);
    // Add an element to the queue header
    boolean offerFirst(E e);
    // Add elements to the end of the queue
    boolean offerLast(E e);
    // Remove the element from the queue header
    E removeFirst(a);
    // Remove the element from the end of the queue
    E removeLast(a);
    // Remove the element from the queue header
    E pollFirst(a);
    // Remove the element from the end of the queue
    E pollLast(a);
    // View the queue header element
    E getFirst(a);
    // Look at the end of the queue
    E getLast(a);
    // View the queue header element
    E peekFirst(a);
    // Look at the end of the queue
    E peekLast(a);
    // Removes the specified element from the queue head by traversing backwards
    boolean removeFirstOccurrence(Object o);
    Removes the specified element from the end of the queue by traversing forward
    boolean removeLastOccurrence(Object o);

    // *** the method in the queue ***
    
    // Add element, equal to addLast(e)
    boolean add(E e);
     // Add element, equal to offerLast(e)
    boolean offer(E e);
    // Remove elements, equal to removeFirst()
    E remove(a);
    // Remove elements, equal to pollFirst()
    E poll(a);
    // View the element, equal to getFirst()
    E element(a);
    // View the element, equal to peekFirst()
    E peek(a);

    // *** * stack method ***

    // addFirst(e)
    void push(E e);
    // removeFirst()
    E pop(a);

    // *** methods in Collection ***
    
    RemoveFirstOccurrence (o)
    boolean remove(Object o);
    // Check whether an element is included
    boolean contains(Object o);
    // Number of elements
    public int size(a);
    / / the iterator
    Iterator<E> iterator(a);
    // reverse iterator
    Iterator<E> descendingIterator(a);
}
Copy the code

The following classes of methods have been added to the Deque:

(1) *First, operating on elements from the queue header;

(2) *Last, operating on elements from the end of the queue;

(3) Push (e), pop(), the method of manipulating elements in the way of stack;

Source code analysis

The main properties

// An array of elements
transient Object[] elements; // non-private to simplify nested class access
// Queue header position
transient int head;
// The end of the queue
transient int tail;
// Minimum initial capacity
private static final int MIN_INITIAL_CAPACITY = 8;
Copy the code

As you can see from the properties, ArrayDeque uses arrays to store elements and uses a header and tail pointer to identify the head and tail of a queue, with a minimum size of 8.

Main construction methods

// The default constructor with an initial capacity of 16
public ArrayDeque(a) {
    elements = new Object[16];
}
// Specifies the number of elements to initialize
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
// Initialize the elements in collection C into an array
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
// Initialize the array
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
// To calculate the capacity, the logic of this code is to calculate the nearest 2 to the n power greater than numElements and not less than 8
For example, 3 is 8,9 is 16, and 33 is 64
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 code

From the constructor, we know that the default initial capacity is 16 and the minimum capacity is 8.

The team

There are many ways to join a team, and we’re going to focus on two, addFirst(e) and addLast(e).

// Join the queue from the head
public void addFirst(E e) {
    // Null elements are not allowed
    if (e == null)
        throw new NullPointerException();
    // Decrement the head pointer by 1 and modulo the array length by 1
    // This is to prevent the array from reaching the end of the boundary overflow
    // If you come to the end, start from the end
    // loop through an array
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // If the heads and tails are together, expand the capacity
    // The expansion rule is also simple, directly double
    if (head == tail)
        doubleCapacity();
}
// Join the queue from the back
public void addLast(E e) {
    // Null elements are not allowed
    if (e == null)
        throw new NullPointerException();
    // Place the element at the end of the pointer
    // You can see that the tail pointer points to the position next to the last element in the queue
    elements[tail] = e;
    // the tail pointer is incremented by 1, starting from the beginning if it reaches the end of the array
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}
Copy the code

(1) There are two ways to join the queue, from the head of the queue or from the end of the queue;

(2) If the capacity is not enough, directly expand to twice;

(3) make the head and tail Pointers loop in the array range by taking the mode of module;

(4) x & (len-1) = x % len;

capacity

private void doubleCapacity(a) {
    assert head == tail;
    // The position of the header pointer
    int p = head;
    // The old array length
    int n = elements.length;
    // The distance between the header pointer and 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 occurs
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    // Create a new array
    Object[] a = new Object[newCapacity];
    // Copy the elements after the old array head into the new array
    System.arraycopy(elements, p, a, 0, r);
    // Copy the elements between subscripts 0 and head into the new array
    System.arraycopy(elements, 0, a, r, p);
    // Assign to a new array
    elements = a;
    // head points to 0 and tail points to the old array length
    head = 0;
    tail = n;
}
Copy the code

It may be a bit tricky to migrate elements here, but look at the picture below to understand.

Out of the team

PollFirst () and pollLast().

// Exit the queue from the queue head
public E pollFirst(a) {
    int h = head;
    @SuppressWarnings("unchecked")
    // take the queue header element
    E result = (E) elements[h];
    If the queue is empty, null is returned
    if (result == null)
        return null;
    // Set the queue head to null
    elements[h] = null;     // Must null out slot
    // Move the queue header pointer to the right one bit
    head = (h + 1) & (elements.length - 1);
    // Return the obtained element
    return result;
}
// From the end of the queue
public E pollLast(a) {
    // Move the tail pointer to the left one bit
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    // Take the element at the current tail pointer
    E result = (E) elements[t];
    // Return null if the queue is empty
    if (result == null)
        return null;
    // Make the current tail pointer null
    elements[t] = null;
    // tail points to the new tail pointer
    tail = t;
    // Return the obtained element
    return result;
}
Copy the code

(1) There are two ways to exit the queue, from the head of the queue or from the tail of the queue;

(2) make the head and tail Pointers loop in the array range by taking the mode of module;

(3) No shrinkage after the team haha ^^

The stack

When we introduced deques earlier, we said that deques can be used directly as stacks, so how is ArrayDeque implemented?

public void push(E e) {
    addFirst(e);
}

public E pop(a) {
    return removeFirst();
}
Copy the code

Isn’t it very simple, in and out of the stack as long as the operation queue header can be ok.

conclusion

(1) ArrayDeque is a double-ended queue implemented by array;

(2) ArrayDeque is implemented by circulating the array with the head and tail Pointers;

(3) When the capacity of ArrayDeque is insufficient, the capacity will be expanded, and the capacity will be doubled each time;

(4) ArrayDeque can be used as a stack directly;

eggs

Double-endian queue versus dual queue?

A double-endian queue (Deque) is a queue in which both ends of the queue can move elements in and out, and the actual elements are stored inside.

Dual Queue refers to a Queue that serves two purposes. The nodes in the Queue are divided into data nodes and non-data nodes. It is the data structure used by the LinkedTransferQueue.

Remember LinkedTransferQueue? Click on the link to the source analysis of LinkedTransferQueue.

Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.