深刻分析（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、计算机系统根底、算法与数据结构）常识。