Java中的ArrayDeque
ArrayDeque是基于动态数组实现的双端队列，支持在两端快速插入和删除元素。这样设计操作数据更加灵活，提供接近数组的性能
特点
- 内部使用的是Object[ ]数组，元素存储在一段连续的空间中，能快速访问
- 双端：使用了头尾指针，实现在头尾快速插入删除
- 不能使用索引位访问，访问是通过头尾指针进行(头尾指针其实就是数组索引位，但是是内部维护)
- 数组在逻辑上是循环的，通过头尾指针循环访问
- ArrayDeque是无界的，数组满了(头尾指针一样)就会进行扩容
- 旧数组容量小于64，新容量为旧容量的两倍+2；大于等于64则是旧容量的1.5倍
- 非线程安全的
在添加删除操作中，始终保持着，头指针指向的位置有元素，尾指针指向的位置是空的
方法
构造方法
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
//创建一个ArrayDeque，默认容量是16，直接分配内存空间
public ArrayDeque() {
elements = new Object[16];
}
//创建一个ArrayDeque，手动传入初始化容量
public ArrayDeque(int numElements) {
elements =
new Object[(numElements < 1) ? 1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}
//创建一个ArrayDeque，复制传入集合的元素
public ArrayDeque(Collection<? extends E> c) {
this(c.size());
copyElements(c);
}
}add和remove
//当前指针前移一位后小于0(超出数组范围了)，指针重新指向数组长度-1的位置
//前移后大于等于0，则返回指针前移后的位置
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}
//当前指针后移一位后大于等于数组长度，指针重新指向数组头部
//否则直接返回后移后的指针位置
static final int inc(int i, int modulus) {
if (++i >= modulus) i = 0;
return i;
}
//从头部添加元素，头尾相遇则扩容，头指针向数组前面移动，超出范围直接转到数组尾部
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e;
if (head == tail)
grow(1);
}
//在指针尾部添加元素，头尾相遇则扩容，尾部指针向后移动，超出范围直接转向数组头部
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[tail] = e;
if (head == (tail = inc(tail, es.length)))
grow(1);
}
//根据指针获取元素
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}
//从头部删除元素，删除后头指针后移一位
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
//从尾部删除元素(尾指针前移一位后获取元素)，删除后尾指针在前移一位后的位置
public E pollLast() {
final Object[] es;
final int t;
E e = elementAt(es = elements, t = dec(tail, es.length));
if (e != null)
es[tail = t] = null;
return e;
}get
//获取头节点
public E peekFirst() {
return elementAt(elements, head);
}
//获取尾节点此处tail指向的是最后一个值的下一位，tail指向的位置是没有值的
//调用dec(tail, es.length)方法计算出最后一个值的位置，获取到并返回
//调用完tail的值依然是3(值传递传递的是副本)
public E peekLast() {
final Object[] es;
return elementAt(es = elements, dec(tail, es.length));
}
//调用完i的值是2，返回2
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}扩容
//扩容：传入参数为最小扩容容量
private void grow(int needed) {
final int oldCapacity = elements.length;
int newCapacity;
//计算需要扩容多少，旧容量小于64，就是旧容量+2
//旧容量大于等于64，则扩容的量是原来的一半
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
//如果jump小于最小扩容容量或者扩容后的新容量比最大容量还大，重新计算新容量
//此处 newCapacity = (oldCapacity + jump) 计算了newCapacity 的值
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
//如果尾部指针位置比头部指针更靠前，或者是头尾指针在同一个位置并且头指针指向的元素不为null
//计算出扩容后多出来的容量，将新数组中头指针指向的元素
//拷贝到新数组头指针偏移newSpace的位置
//拷贝的个数是oldCapacity - head
//将原来位置的数据都清空
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}使用场景
历史操作记录保存和回退
public static void main( String[] args ) {
ArrayDeque arrayDeque = new ArrayDeque( 30 );
ArrayDeque dequeBack = new ArrayDeque( 30 );
//添加操作1
click(arrayDeque, dequeBack);
//添加操作2
click(arrayDeque, dequeBack);
//添加操作3
click(arrayDeque, dequeBack);
//回退到操作2，操作3放入dequeBack尾部
before(dequeBack,arrayDeque);
//回退到操作1，操作2放入dequeBack尾部
before(dequeBack,arrayDeque);
//从dequeBack尾部取一个元素放入arrayDeque尾部
after( arrayDeque, dequeBack);
//页面点击，清空dequeBack(操作3被清掉了)，操作4放入arrayDeque
//此时dequeBack.size = 0；arrayDeque = 1，2，4
click( arrayDeque, dequeBack);
}
//页面点击
public static void click(ArrayDeque arrayDeque, ArrayDeque dequeBack){
HistoryRecord record = new HistoryRecord( );
arrayDeque.offerLast( record );
dequeBack.clear();
}
//后退
public static HistoryRecord before(ArrayDeque arrayDeque, ArrayDeque dequeBack){
if(arrayDeque.size() == 0 ){
return null;
}
HistoryRecord record = ( HistoryRecord ) arrayDeque.pollLast();
dequeBack.offerLast( record );
return record;
}
//前进
public static HistoryRecord after(ArrayDeque arrayDeque, ArrayDeque dequeBack){
if(dequeBack.size() == 0 ){
return null;
}
HistoryRecord record = ( HistoryRecord ) dequeBack.pollLast();
arrayDeque.offerLast( record );
return record;
}滑动窗口问题
滑动窗口最大值
双端队列存储数组的索引
- 第一个窗口：3个值比较大小，返回最大的
- 后续窗口：实际比较的元素只有新进入窗口的值，其他两个在上一个窗口就比较过了
//如果队尾的元素(下标)所在的nums[index]比当前nums[i]小，就把队尾下标移除
//将i添加到队尾
//如果队首的下标比i-k还小，就把队首的下标移除（超出窗口范围了）
//当队尾的下标大于等于k-1的时候，返回队首下标
//目的：保证队首下标对应的值是窗口中最大的；队列中只存在窗口范围内的下标，不在的弹出
//下标在队列中是升序排序
public static int[] maxSlidingWindow( int[] nums, int k ) {
if(nums.length == 0){
return null;
}
int length = nums.length;
ArrayDeque<Integer> deque = new ArrayDeque<>( length );
ArrayList<Integer> list = new ArrayList( length );
for (int i = 0; i < length; i++) {
// 移除队列中比当前元素小的元素
//(循环弹出，直到找到队列中比nums[i]大的。如果最后队列弹出完了，也结束循环)
while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.addLast(i);
// 移除超出窗口范围的队首元素
if (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 当窗口形成时记录结果
if (i >= k - 1) {
list.add( nums[deque.peekFirst()] );
}
}
return list.stream().mapToInt( Integer::intValue ).toArray();
}非双端队列解法
public static int[] maxSlidingWindow( int[] nums, int k ) {
if(nums == null || nums.length == 0 || nums.length < k){
return null;
}
int length = nums.length;
int[] subnums = new int[k];
ArrayList<Integer> list = new ArrayList( length );
int i = 0;
for ( ; i < k; i++ ) {
subnums[i] = nums[i];
}
list.add( math(subnums, k) );
while ( i < length ){
//保证新加入的数据替换掉前一个窗口中被移除的数据
subnums[i%k] = nums[i++];
list.add(math(subnums, k)) ;
}
return list.stream().mapToInt( Integer::intValue ).toArray();
}
public static int math(int[] subnums, int k){
int max = subnums[0];
for ( int i = 0; i < k; i++ ) {
max = Math.max( max, subnums[i]);
}
return max;
}