增加扩容方法
private void expansionCapacity(int newCapacity){ int oldCapacity = elements.length; if (oldCapacity >= size + 1) return; // 创建一个新的容量的数组 // newCapacity = oldCapacity + (oldCapacity >> 1); T[] newElements = (T[]) new Object[newCapacity]; // 拷贝元素 for (int i = 0; i < size; i++) { newElements[i] = elements[(i + front) % elements.length]; } // 指向新的内存空间 elements = newElements; front = 0; System.out.println("扩容成功,由" + oldCapacity + "扩展至" + newCapacity); } 复制代码
修改enQueue方法代码
public void enQueue(T element){ expansionCapacity(elements.length + (elements.length >> 1)); elements[(front + size) % elements.length] = element; size++; } 复制代码
扩容测试代码
@Test public void testExpansion() { queue.deQueue(); System.out.println(queue); for (int i = 0; i < 3; i++) { queue.enQueue(i); } System.out.println(queue); for (int i = 0; i < 3; i++) { queue.deQueue(); } System.out.println("After deQueue: " + queue); for (int i = 0; i < 4; i++) { queue.enQueue(i + 100); } System.out.println("After enQueue: " + queue); for (int i = 0; i < 8; i++) { queue.deQueue(); } System.out.println(queue); } 复制代码
执行测试
五、循环双端队列
可以在两端进行添加、删除操作的循环队列
新建一个CircleDeque
public class CircleDeque<T> { private int front; private int size; private T[] elements; public static final int DEFAULT_CAPACITY = 10; // 构造函数，定义数组的长度 public CircleDeque(){ elements = (T[]) new Object[DEFAULT_CAPACITY]; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } public void clear(){ for (int i = 0; i < elements.length; i++) { elements[index(i)] = null; } size = 0; front = 0; } public int index(int index){ return (front + index) % elements.length; } private void expansionCapacity(int newCapacity){ int oldCapacity = elements.length; if (oldCapacity >= size + 1) return; // 创建一个新的容量的数组 // newCapacity = oldCapacity + (oldCapacity >> 1); T[] newElements = (T[]) new Object[newCapacity]; // 拷贝元素 for (int i = 0; i < size; i++) { newElements[i] = elements[(i + front) % elements.length]; } // 指向新的内存空间 elements = newElements; front = 0; System.out.println("扩容成功,由" + oldCapacity + "扩展至" + newCapacity); } @Override public String toString() { return "CircleQueue{" + "front=" + front + ", size=" + size + ", elements=" + Arrays.toString(elements) + '}'; } } 复制代码
获取头部和尾部的元素
public T front(){ return elements[front]; } public T rear(){ return elements[index(front + size - 1)]; } 复制代码
从尾部入队和从头部移除与双端队列的方法一致
// 从尾部入队 public void enQueueRear(T element){ expansionCapacity(elements.length + (elements.length >> 1)); elements[(front + size) % elements.length] = element; size++; } // 从头部出队 public T deQueueFront(){ // 先获取对头的元素 T frontEle = elements[front]; // 将对头的元素置为空 elements[front] = null; // 队头要往后移动一次 // front++; front = (front + 1) % elements.length; // 长度-1 size--; // 返回队头元素 return frontEle; } 复制代码
从头部入队时，如果front是0，那么插入的位置是-1，数组中不存在-1的索引，使用-1 + 数组长度就可以变成真正数组中的索引，index方法需要增加判断
public int index(int index){ index += front; if (index < 0){ return index + elements.length; } return (front + index) % elements.length; } 复制代码
从尾部出队和从头部入队方法实现
// 从尾部出队 public T deQueueRear(){ // 获取真实索引 int rearIndex = index(size - 1); T rear = elements[rearIndex]; elements[rearIndex] = null; size--; return rear; } // 从头部入队 public void enQueueFront(T element){ expansionCapacity(elements.length + (elements.length >> 1)); front = index(front - 1); elements[front] = element; size ++; } 复制代码
新增测试类
public class CircleDequeTest { CircleDeque<Integer> deque = null; @Before public void init(){ deque = new CircleDeque<>(); for (int i = 0; i < 8; i++) { deque.enQueueRear(i + 10); } System.out.println("After Init" + deque); } @Test public void front() { System.out.println("CircleDeque Front: " + deque.front()); } @Test public void rear() { System.out.println("CircleDeque Rear: " + deque.rear()); } @Test public void enQueueRear() { deque.enQueueRear(18); System.out.println("After enQueueRear:" + deque); } @Test public void deQueueFront() { deque.deQueueFront(); System.out.println("After deQueueFront: " + deque); } @Test public void deQueueRear() { deque.deQueueRear(); System.out.println("After deQueueRear: " + deque); } @Test public void enQueueFront() { deque.enQueueFront(9); System.out.println("After enQueueFront: " + deque); } } 复制代码
执行测试
