//循环双端队列：Circle Double Ended Queue//本质是对动态数组的优化//队头队尾都可以添加或删除元素//相比于普通循环队列需要注意的点是在队头插入元素时的对front前移的处理public class CircleDequeZH<E> {private int size;private int front;private E elements[];private static final int DEFAULT_CAPACITY = 10;public CircleDequeZH() {elements = (E[]) new Object[DEFAULT_CAPACITY];}private int getMo(int a, int b){return a > b ? (a-b) : a;//%运算效率太低，当a<2b时可以用这个表达式替代取模，而循环队列front+index最大等于2*length-1，恰好符合要求}//计算队头队尾元素下标可以写一个函数，用来映射循环队列中的真实索引public int realIndexCaculate(int index){if (index<0){return getMo((index + front + elements.length), elements.length);//当front=0时，我们在队头插入元素，front要前移，也就是到整个数组的末尾，所以单独写一个if应对这种情况//这时候front的新位置为（front-1+length）%length}return getMo((index+front),elements.length);//!!!//就是要找队列中的下标为index的（第index+1个）元素，返回它在我们数组里的真实下标//我觉得影响以后的可读性就没用}private void ifNeedEnLarge(int needCapacity){int oldcapacity = elements.length;if (needCapacity<=oldcapacity){return;}else{int newcapacity = oldcapacity + (oldcapacity>>1);E[] newElements = (E[]) new Object[newcapacity];for (int i=0;i<size;i++){//循环队列获取第i个元素的下标的方式：newElements[i]=elements[(i+front)%elements.length];//这个扩容的方式就是把队列里的元素依次出队到另一个队列里，同时重置队头的位置}front = 0;elements = newElements;System.out.println("enLarge Success"+" newCapacity = "+newcapacity);}}public int size(){return size;}public boolean isEmpty(){return size == 0;}//清空循环队列，涉及到元素的真实下标计算，同扩容那里public void clear(){for (int i = 0;i<size;i++){elements[(i+front)%elements.length]=null;}size = 0;front = 0;}//出队，主要注意对front的处理public E deQueueFront(){E element = elements[front];elements[front] = null;front = (front+1)%elements.length;size--;return element;}//从队尾出队public E deQueueNear(){E element = elements[realIndexCaculate(size-1)];elements[realIndexCaculate(size-1)] = null;size--;return element;}//从队头入队public void enQueueFront(E element){ifNeedEnLarge(size+1);elements[realIndexCaculate(-1)] = element;front = realIndexCaculate(-1);size++;}//入队，主要注意对入队位置的计算public void enQueueNear(E element){ifNeedEnLarge(size+1);elements[(front+size)% elements.length] = element;size++;}public String arrayPrint(){StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(" ").append("front= ").append(elements[front]).append(" [");for (int i = 0; i< elements.length; i++ ){if (elements[i]==null){string.append("null,");}else {string.append(elements[i]).append(",");}}string.append("]");return string.toString();}}
