A thousand miles kuibu, thousands of rivers; Make a little progress every day, and one day you’ll be a big shot

preface

The previous article said that LinkedList can also be used for queue and stack functions, but we generally recommend ArrayDeque for queue functions, because the bottom layer is an array, and the queue and stack are all at the head or tail of the operation, so the performance of an array is a little faster than that of a LinkedList.

Both LinkedList and ArrayDeque implement the Deque interface to get queues and stacks. The Deque interface inherits the Queue interface to obtain the Queue function, and then extends the base to achieve the dual-end Queue, so as to obtain the stack function. To get the most out of space, ArrayDeque uses circular queues; A LinkedList can insert null values, whereas an ArrayDeque cannot.

What is a two-enqueued?

In short, it is a queue that can be operated on both ends (🌚 said and did not say the same…). . Haha, let’s see the picture

The general queue looks like this:

A two-endian queue looks like this

In general, ordinary queues can only remove elements at the head and add elements at the tail, while double-ended queues can add and remove elements at both the head and tail

What is a circular queue?

Let’s say you have an array of size 5, and the first element you insert is at index 2, and when you add the fourth element, it doesn’t expand, it compares the first and the last, and then inserts the data at index 0. When the header and tail Pointers are equal, the queue array is full and will expand.

The array is in top down order, and one might say why do the first and the last Pointers point to the third square? Because what I’m showing here is that the first element is inserted at index 2. Of course, an ArrayDeque starts at 0, so the first and last Pointers to the zero subscript are initialized.

What does Deque have?

Without further ado, look at the picture:

The methods of ArrayDeque are mainly in the blue box, and the other two colors of the box are all by calling the methods in the blue box to achieve related functions. See the brain diagram I drew again:

Each function on this queue has two methods, with add(), remove(), and Element () reporting an exception if the operation fails, and offer(), poll(), and peek() returning null or false if the operation fails

The ones in the dark red box are the ones that are really used, so in this article I’ll say addLast(), pollFirst, getFirst(), addFirst(), peekFirst;

Internal variables

ArrayDeque contains only four variables: element[], head pointer, tail pointer, MIN_INITIAL_CAPACITY indicates that the minimum initial capacity is 8

A constructor

The construction method, like any other set, has a parameter construction and no parameter construction

No arguments structure

Simply initialize an array of objects with a size of 16

public ArrayDeque(a) {

    elements = new Object[16];

}

Copy the code

Have the cords structure

Pass an int as an argument

public ArrayDeque(int numElements) {

    allocateElements(numElements);

}

Copy the code
  • AllocateElements (int numElements) Allocates an empty array to hold a given number of elements.
private void allocateElements(int numElements) {

    elements = new Object[calculateSize(numElements)];

}

Copy the code
  • CalculateSize (int numElements) Adjust the size of the passed value

The algorithm above uses bit operations, so if you don’t know about bit operations, you can watchAn operationThis article. We set the value to 2 to the n to satisfy the followingCircular queueThis algorithm

The argument passed is the collection object

public ArrayDeque(Collection<? extends E> c) {

    allocateElements(c.size());

    addAll(c);

}

Copy the code

The first step calls the same method as above, except for the addAll() method

  • addAll(Collection c)

Instead of using the system.arrayCopy () method like ArrayList, we use a for loop to call add() to add the copies one by one. Why do you do that? ArrayDeque (ArrayDeque) ¶ ArrayDeque (ArrayDeque) ¶ ArrayDeque (ArrayDeque) ¶ ArrayDeque (ArrayDeque) cannot have null values. (Add () actually calls addLast(), which we’ll talk about next.)

addLast()

The source code parsing

This method means to add data to the tail. The bits and algorithms in the box below are the core algorithms that implement circular queuing

Remember when we initialized up here, whatever number we passed in, we got 2n squared. The algorithm is that when the right side of ampersand is 2n−1, and the left side of ampersand is a positive integer, no matter how large, the final result is always <=2n; If the number to the left of & is 0, the result is 0; When the number to the left of & is negative, -1=2n−1

Some examples: when 2n= 8,2 n−1=7

  • 4 & 7 = 4 September 22 & 7 = 6 & 7 = 1
  • 0 & 7 = 0
  • 1 & 7 = 7-2 & 7 = 6-8 & 7 = 0
  • DoubleCapacity () is doubled

The flow chart

To make it easier to understand, LET me draw the flow chart of the expansion up, such as head in the middle:

pollFirst()

Remove header data

The source code parsing

When you delete, you do not move the data as you would with an ArrayList. Instead, you just move where the head points

The flow chart

GetFirst () and peekFirst ()

These two methods are the same. They both return the data referred to by head. The difference is that one throws an exception and the other does not

Source code analysis

  • getFirst()
public E getFirst(a) {

    @SuppressWarnings("unchecked")

    E result = (E) elements[head];

    if (result == null)

        throw new NoSuchElementException();

    return result;

}

Copy the code
  • peekFirst()
public E peekFirst(a) {

    // elements[head] is null if deque empty

    return (E) elements[head];

}

Copy the code

addFirst()

The source code parsing

So again, we’re going to use the bit and the algorithm, we’re going to compute the head, and we’re going to insert the data

The flow chart

clear()

The source code parsing

The clearing operation starts with the element referred to by head and continues until head=tail.

size()

The size of the queue is also obtained using the same bit and algorithm described above, with the tail minus the head, and then the bit and the length of the array minus 1. Why do we do that? Why not define a size just like ArrayList and LinkedList? Don’t you think it would be more convenient? One less variable, one less variable to maintain, one less security risks ah

public int size(a) {

    return (tail - head) & (elements.length - 1);

}

Copy the code

conclusion

The above method basically has a shadow of this algorithm, so this is the core; If you don’t know about bit operations, you can read about bit operations;

Core algorithm:

when&The right toWhen,&When the number on the left is a positive integer, no matter how big it is, it’s always going to be <=; when&If the number on the left is 0, the result is 0; when&When the left-hand side is negative, negative 1 is equal to

The ArrayDeque no-parameter constructor initializes an empty array with a capacity of 16. In the previous ArrayList article, the ArrayDeque no-parameter constructor initializes an empty array with a capacity of 10 the first time data is added.

The ArrayDeque is expanded by twice the size of the original array each time

ArrayDeque cannot insert null values