Analyze Java ArrayQueue source code.

ArrayQueue internal implementation

Before talking about the internal implementation of ArrayQueue, let’s first look at an ArrayQueue Usage example:

public void testQueue() {
    ArrayQueue<Integer> queue = new ArrayQueue<>(10);
    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.add(4);
    System.out.println(queue);
    queue.remove(0); // 这个参数只能为0 表示删除队列当中第一个元素，也就是队头元素
    System.out.println(queue);
    queue.remove(0);
    System.out.println(queue);
}
// 输出结果
[1, 2, 3, 4]
[2, 3, 4]
[3, 4]

First of all, ArrayQueue is internally implemented by a circular array, which may ensure that the time complexity of adding and deleting data is the same, unlike ArrayListdeleting data. The time complexity of is. There are two integer data head and tail inside ArrayQueue. The functions of these two are mainly to point to the head and tail of the queue, and its initial state. The layout in the memory is as shown below:

Because the values ​​of head and tail are both equal to 0 in the initial state, Points to the first data in the array. Now we add 5 pieces of data to ArrayQueue, then its memory layout will be as shown below:

Now we delete 4 pieces of data, then After 4 deletion operations in the above picture, the internal data layout of ArrayQueue is as follows:

In the above state, we continue to add 8 data, then The layout is as follows:

We know that when adding data in the above figure, not only the space in the second half of the array is used up, but also the unused space in the first half can be continued to be used. , that is to say, a recycling process is implemented inside ArrayQueue.

ArrayQueue source code analysis

Constructor

public ArrayQueue(int capacity) {
    this.capacity = capacity + 1;
    this.queue = newArray(capacity + 1);
    this.head = 0;
    this.tail = 0;
}

@SuppressWarnings("unchecked")
private T[] newArray(int size) {
    return (T[]) new Object[size];
}

The above constructor code is relatively easy to understand. It mainly applies for an array based on the length of the array space entered by the user, but it is specific When applying for an array, one more space will be applied for.

add function

public boolean add(T o) {
    queue[tail] = o;
    // 循环使用数组
    int newtail = (tail + 1) % capacity;
    if (newtail == head)
        throw new IndexOutOfBoundsException("Queue full");
    tail = newtail;
    return true; // we did add something
}

The above code is relatively easy to understand. We have mentioned above that ArrayQueue can add data to the array in a loop. This is also reflected in the code above.

remove function

public T remove(int i) {
    if (i != 0)
        throw new IllegalArgumentException("Can only remove head of queue");
    if (head == tail)
        throw new IndexOutOfBoundsException("Queue empty");
    T removed = queue[head];
    queue[head] = null;
    head = (head + 1) % capacity;
    return removed;
}

As can be seen from the above code, we must pass parameter 0 in the remove function, otherwise an exception will be thrown. In this function, we will only delete the data at the current head subscript position, and then perform a cyclic operation of adding 1 to the value of head.

get function

public T get(int i) {
    int size = size();
    if (i < 0 || i >= size) {
        final String msg = "Index " + i + ", queue size " + size;
        throw new IndexOutOfBoundsException(msg);
    }
    int index = (head + i) % capacity;
    return queue[index];
}

getThe parameters of the function indicate that the ith data is obtained, and the ith data is not It is not the ith data in the array position, but the data at the i position from head. Knowing this, the above code is easy to understand. of.

resize function

public void resize(int newcapacity) {
    int size = size();
    if (newcapacity < size)
        throw new IndexOutOfBoundsException("Resizing would lose data");
    newcapacity++;
    if (newcapacity == this.capacity)
        return;
    T[] newqueue = newArray(newcapacity);
    for (int i = 0; i < size; i++)
        newqueue[i] = get(i);
    this.capacity = newcapacity;
    this.queue = newqueue;
    this.head = 0;
    this.tail = size;
}

In the resize function, first apply for an array space of new length, and then copy the data of the original array to the new array one by one. Note During this copy process, head and tail are updated again, and it is not a simple array copy, because in the previous operation, head may no longer be 0, so the new copy requires us to take it out from the old array one by one and then put it into the new array. The following figure can clearly see this process:

The above is the detailed content of Analyze Java ArrayQueue source code.. For more information, please follow other related articles on the PHP Chinese website!