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，返回2static 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 arrayint 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 );//添加操作1click(arrayDeque, dequeBack);//添加操作2click(arrayDeque, dequeBack);//添加操作3click(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，4click( 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;}