这篇文章主要讲解了“Java源码之ArrayQueue内部是怎么实现的”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Java源码之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 ) O(1) O(1),不像ArrayList
删除数据的时间复杂度为 O ( n ) O(n) O(n)。在ArrayQueue
内部有两个整型数据head
和tail
,这两个的作用主要是指向队列的头部和尾部,它的初始状态在内存当中的布局如下图所示:
因为是初始状态head
和tail
的值都等于0,指向数组当中第一个数据。现在我们向ArrayQueue
内部加入5个数据,那么他的内存布局将如下图所示:
现在我们删除4个数据,那么上图经过4次删除操作之后,ArrayQueue
内部数据布局如下:
在上面的状态下,我们继续加入8个数据,那么布局情况如下:
我们知道上图在加入数据的时候不仅将数组后半部分的空间使用完了,而且可以继续使用前半部分没有使用过的空间,也就是说在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,因此新的拷贝需要我们一个一个的从就数组拿出来,让后放到新数组当中。下图可以很直观的看出这个过程:
感谢各位的阅读,以上就是“Java源码之ArrayQueue内部是怎么实现的”的内容了,经过本文的学习后,相信大家对Java源码之ArrayQueue内部是怎么实现的这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。