关于算法:深入剖析JDKArrayQueue源码

深刻分析（JDK）ArrayQueue 源码

前言

在本篇文章当中次要给大家介绍一个比较简单的 JDK 为咱们提供的容器ArrayQueue，这个容器次要是用数组实现的一个单向队列，整体的构造绝对其余容器来说就比较简单了。

ArrayQueue 外部实现

在谈 ArrayQueue 的外部实现之前咱们先来看一个 ArrayQueue 的应用例子：

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]

首先 ArrayQueue 外部是由循环数组实现的，可能保障减少和删除数据的工夫复杂度都是 $O(1)$，不像 ArrayList 删除数据的工夫复杂度为 $O(n)$。在 ArrayQueue 外部有两个整型数据 head 和tail，这两个的作用次要是指向队列的头部和尾部，它的初始状态在内存当中的布局如下图所示：

因为是初始状态 head 和tail的值都等于 0，指向数组当中第一个数据。当初咱们向 ArrayQueue 外部退出 5 个数据，那么他的内存布局将如下图所示：

当初咱们删除 4 个数据，那么上图通过 4 次删除操作之后，ArrayQueue外部数据布局如下：

在下面的状态下，咱们持续退出 8 个数据，那么布局状况如下：

咱们晓得上图在退出数据的时候不仅将数组后半局部的空间应用完了，而且能够持续应用前半部分没有应用过的空间，也就是说在 ArrayQueue 外部实现了一个循环应用的过程。

ArrayQueue 源码分析

构造函数

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];
}

下面的构造函数的代码比拟容易了解，次要就是依据用户输出的数组空间长度去申请数组，不过他具体在申请数组的时候会多申请一个空间。

add 函数

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
}

下面的代码也绝对比拟容易看懂，在上文当中咱们曾经提到了 ArrayQueue 能够循环将数据退出到数组当中去，这一点在下面的代码当中也有所体现。

remove 函数

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;
}

从下面的代码当中能够看出，在 remove 函数当中咱们必须传递参数 0，否则会抛出异样。而在这个函数当中咱们只会删除以后 head 下标所在位置的数据，而后将 head 的值进行循环加 1 操作。

get 函数

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];
}

get函数的参数示意失去第 i 个数据，这个第 i 个数据并不是数组地位的第 i 个数据，而是间隔 head 地位为 i 的地位的数据，理解这一点，下面的代码是很容易了解的。

resize 函数

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;
}

在 resize 函数当中首先申请新长度的数组空间，而后将原数组的数据一个一个的拷贝到新的数组当中，留神在这个拷贝的过程当中，从新更新了 head 与tail，而且并不是简略的数组拷贝，因为在之前的操作当中 head 可能曾经不是了 0，因而新的拷贝须要咱们一个一个的从就数组拿进去，让后放到新数组当中。下图能够很直观的看出这个过程：

总结

在本篇文章当中次要给大家介绍了 ArrayQueue 的外部实现过程和原理，并且看了 ArrayQueue 的源代码，有图的辅助整个浏览的过程应该是比拟清晰的，ArrayQueue也是一个比较简单的容器，JDK对他的实现也比较简单。

以上就是本文所有的内容了，心愿大家有所播种，我是 LeHung，咱们下期再见！！！（记得 点赞 珍藏哦！）

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。