大家好,又见面了,我是你们的朋友全栈君。
Queue是什么
Queue是具有队列特性的接口
Queue具有先进先出的特点
Queue所有新元素都插入队列的末尾,移除元素都移除队列的头部
public interface Queue extends Collection {
//往队列插入元素,如果出现异常会抛出异常
boolean add(E e);
//往队列插入元素,如果出现异常则返回false
boolean offer(E e);
//移除队列元素,如果出现异常会抛出异常
E remove();
//移除队列元素,如果出现异常则返回null
E poll();
//获取队列头部元素,如果出现异常会抛出异常
E element();
//获取队列头部元素,如果出现异常则返回null
E peek();
}
可以将上面的方法画成以下表格
操作
抛出异常
返回特殊值
插入
add()
offer()
删除
remove()
poll()
查询
element()
peek()
Deque是什么
Deque是一个双端队列
Deque继承自Queue
Deque具有先进先出或后进先出的特点
Deque支持所有元素在头部和尾部进行插入、删除、获取
public interface Deque extends Queue {
void addFirst(E e);//插入头部,异常会报错
boolean offerFirst(E e);//插入头部,异常返回false
E getFirst();//获取头部,异常会报错
E peekFirst();//获取头部,异常不报错
E removeFirst();//移除头部,异常会报错
E pollFirst();//移除头部,异常不报错
void addLast(E e);//插入尾部,异常会报错
boolean offerLast(E e);//插入尾部,异常返回false
E getLast();//获取尾部,异常会报错
E peekLast();//获取尾部,异常不报错
E removeLast();//移除尾部,异常会报错
E pollLast();//移除尾部,异常不报错
}
可以将上面的方法画成以下表格,只不过Deque是有头部和尾部的
操作
抛出异常
返回特殊值
插入
add()
offer()
删除
remove()
poll()
查询
element()
peek()
ArrayDeque是什么
实现于Deque,拥有队列或者栈特性的接口
实现于Cloneable,拥有克隆对象的特性
实现于Serializable,拥有序列化的能力
public class ArrayDeque extends AbstractCollection
implements Deque, Cloneable, Serializable{}
ArrayDeque的成员变量
//数组存储元素
transient Object[] elements;
//头部元素索引
transient int head;
//尾部元素索引
transient int tail;
//最小容量
private static final int MIN_INITIAL_CAPACITY = 8;
ArrayDeque底层使用数组存储元素,同时还使用head和tail来表示索引,但注意tail不是尾部元素的索引,而是尾部元素的下一位,即下一个将要被加入的元素的索引
ArrayDeque的初始化
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection extends E> c) {
allocateElements(c.size());
addAll(c);
}
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];
}
在初始化中,数组要求的大小必须为2^n,所以有这么一个算法,如果当前的大小大于默认规定的大小时,就会去计算出新的大小,那么这个计算过程是怎么样的呢?我们举一个例子进行分析
如果initialCapacity为10的时候,那么二进制为 1010
经过initialCapacity |= (initialCapacity >>> 1)时,那么二进制为 1010 | 0101 = 1111
经过initialCapacity |= (initialCapacity >>> 2)时,那么二进制为 1111 | 0011 = 1111
后面计算的结果都是1111,可以理解为将二进制的低位数都补上1,这样出来的结果都是2^n-1
最后initialCapacity++,2^n-1+1出来的结果就是2^n
这里又有人会有疑问了,为什么initialCapacity>>>16,右移到5位就可以结束呢?那是因为用的是|=符号,从右移1位到5位累加,其实就是整体右移了15位,刚好int值是16位的数,这就刚好满足16位二进制的低位都被补上了1
ArrayDeque的插入
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head – 1) & (elements.length – 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
//tail中保存的是即将加入末尾的元素的索引
elements[tail] = e;
//tail向后移动一位
if ( (tail = (tail + 1) & (elements.length – 1)) == head)
//tail和head相遇,空间用尽,需要扩容
doubleCapacity();
}
在存储的过程中,这里有个有趣的算法,就是tail的计算公式(tail = (tail + 1) & (elements.length – 1)),注意这里的存储采用的是环形队列的形式,也就是当tail到达容量最后一个的时候,tail就为等于0,否则tail的值tail+1
(tail = (tail + 1) & (elements.length – 1))
证明:(elements.length – 1) = 2^n-1 即二进制的所有低位都为1,假设为 11111111
假设:tail为最后一个元素,则(tail + 1)为 (11111111 + 1) = 100000000
结果:(tail + 1) & (elements.length – 1) = 000000000,tail下一个要添加的索引为0
其插入过程中,如果刚好是最后一个元素时
ArrayDeque的扩容
private void doubleCapacity() {
assert head == tail; //扩容时头部索引和尾部索引肯定相等
int p = head;
int n = elements.length;
//头部索引到数组末端(length-1处)共有多少元素
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;
}
ArrayDeque的删除
ArrayDeque支持从头尾两端移除元素,remove方法是通过poll来实现的。因为是基于数组的,在了解了环的原理后这段代码就比较容易理解了
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;
}
public E pollLast() {
int t = (tail – 1) & (elements.length – 1);
@SuppressWarnings(“unchecked”)
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
ArrayDeque的查询
@SuppressWarnings(“unchecked”)
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head];
}
@SuppressWarnings(“unchecked”)
public E peekLast() {
return (E) elements[(tail – 1) & (elements.length – 1)];
}
总结
ArrayDeque是Deque 接口的一种具体实现,是依赖于可变数组来实现的。ArrayDeque 没有容量限制,可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用,效率要高于Stack;ArrayDeque 也可以作为队列来使用,效率相较于基于双向链表的LinkedList也要更好一些
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/191355.html原文链接:https://javaforall.cn