arraydeque和linkedlist一样都实现了双端队列deque接口,但它们内部的数据结构和使用方法却不一样。根据该类的源码注释翻译可知:
public class arraydeque<e> extends abstractcollection<e> implements deque<e>, cloneable, serializable
所以arraydeque既可以作为队列(包括双端队列xxxfirst,xxxlast),也可以作为栈(pop/push/peek)使用,而且它的效率也是非常高,下面就让我们一起来读一读jdk1.8的源码。
//存储队列元素的数组 //power of two transient object[] elements; //队列头部元素的索引 transient int head; //添加一个元素的索引 transient int tail; //最小的初始化容量(指定大小构造器使用) private static final int min_initial_capacity = 8;
//默认16个长度 public arraydeque() { elements = new object[16]; } public arraydeque(int numelements) { allocateelements(numelements); } public arraydeque(collection<? extends e> c) { allocateelements(c.size()); addall(c); }
arraydeque通过allocateelements()方法进行扩容。下面是allocateelements()源码:
private void allocateelements(int numelements) { int initialcapacity = min_initial_capacity; // find the best power of two to hold elements. // tests "<=" because arrays aren't kept full. if (numelements >= initialcapacity) { initialcapacity = numelements; initialcapacity |= (initialcapacity >>> 1); initialcapacity |= (initialcapacity >>> 2); initialcapacity |= (initialcapacity >>> 4); initialcapacity |= (initialcapacity >>> 8); initialcapacity |= (initialcapacity >>> 16); initialcapacity++; if (initialcapacity < 0) // too many elements, must back off initialcapacity >>>= 1;// good luck allocating 2 ^ 30 elements } elements = new object[initialcapacity]; }
arraydeque<integer> arraydeque = new arraydeque<>(8);
下面就从主要函数中来找找答案。
扩容是调用doublecapacity() 方法,当head和tail值相等时,会进行扩容,扩容大小翻倍。
private void doublecapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newcapacity = n << 1; if (newcapacity < 0) throw new illegalstateexception("sorry, deque too big"); object[] a = new object[newcapacity]; system.arraycopy(elements, p, a, 0, r); system.arraycopy(elements, 0, a, r, p); elements = a; head = 0; tail = n; }
通过位与计算找到下一个元素的位置。
public boolean add(e e) { addlast(e); return true; }
public void addlast(e e) { if (e == null) throw new nullpointerexception(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doublecapacity(); }
add()函数实际上调用了addlast()函数,顾名思义这是将元素添加到队列尾。前提是不能添加空元素。
8 & 7 = 0 (1000 & 111)
这就是为了上面说的位与计算elements.length - 1 以此得到下一个元素的位置tail。
和addlast相反,添加的元素都在队列最前面
public void addfirst(e e) { if (e == null) throw new nullpointerexception(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doublecapacity(); }
-1 & (lements.length - 1)= lements.length - 1
所以第一次添加一个元素后head就变为lements.length - 1
例如:
arraydeque<integer> arraydeque = new arraydeque<>(7); arraydeque.addfirst(1); arraydeque.addfirst(2); arraydeque.addfirst(3);
执行时,arraydeque内部数组结构变化为:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
3 | 2 | 1 |
第一次添加前head为0,添加时计算:head = -1 & 7 , 计算head得到7。
public e remove() { return removefirst(); } public e removefirst() { e x = pollfirst(); if (x == null) throw new nosuchelementexception(); return x; }
public e pollfirst() { int h = head; @suppresswarnings("unchecked") e result = (e) elements[h]; // element is null if deque empty if (result == null) return null; elements[h] = null; // must null out slot head = (h + 1) & (elements.length - 1); return result; }
删除元素实际上是调用pollfirst()函数。
head = (h + 1) & (elements.length - 1); 位与计算head移动到下一个位置
public int size() { return (tail - head) & (elements.length - 1); }
如对本文有疑问, 点击进行留言回复!!
利用python将Mysql信息以Excel文件并作为邮件附件发送
springmvc+mybaits+mysql上传表情Incorrect string value: ‘\xF0\x9F\xA4\xB4\xF0\x9F...‘ for
SpringCloud Greenwich集成Seata1.2.0详解说明(原创by ulwfcyvi)
mybatis generator生成代码库 与指定的库不一致 为其他库的同名表
网友评论