获取双端队列头和尾的元素
public T front(){ return list.get(0); } public T rear(){ return list.get(list.size() - 1); } 复制代码
测试类
public class DequeTest { Deque<Integer> deque = null; @Before public void init(){ deque = new Deque<>(); deque.enQueueRear(10); deque.enQueueRear(20); deque.enQueueRear(30); System.out.println("Init Queue：" + deque); } @Test public void enQueueRear() { deque.enQueueRear(40); System.out.println("After enQueueRear: " + deque); } @Test public void deQueueFront() { deque.enQueueFront(0); System.out.println("After deQueueFront: " + deque); } @Test public void enQueueFront() { deque.enQueueFront(40); System.out.println("After enQueueFront: " + deque); } @Test public void deQueueRear() { deque.deQueueRear(); System.out.println("After deQueueRear: " + deque); } @Test public void front() { System.out.println("Front:" + deque.front()); } @Test public void rear() { System.out.println("Rear:" + deque.rear()); } } 复制代码
给Deque类增加toString方法
@Override public String toString() { return "Deque{" + "list=" + list + '}'; } 复制代码
执行测试类中所有的测试方法
四、循环队列
循环队列底层使用数组实现，拥有队头（front）属性，指定数组中的某一个索引为队列的头部，front指的是数组中的索引，为int类型，front不一定是索引0的位置
删除元素演示
循环队列在队头删除元素的时候，需要将front向后移动一个位置，再次删除一个元素，front就在向后移动一个位置，front的范围始终小于数组的容量
添加元素演示
添加元素时往队尾添加元素，front的位置始终不变，当右边的没有空位时就循环到数组左边空位添加元素，新增加的元素的索引使用小于数组的容量
当数组的左边也没有空位时再添加就需要进行动态扩容，循环队列中的循环是指添加元素时循环。
循环队列所拥有的方法与普通队列一致
循环队列实现
public class CircleQueue<T> { private int size; private T[] elements; public static final int DEFAULT_CAPACITY = 10; // 构造函数，定义数组的长度 public CircleQueue(){ elements = (T[]) new Object[DEFAULT_CAPACITY]; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } } 复制代码
获取队列头元素
public T front(){ return elements[front]; } 复制代码
在尾部添加元素，添加元素的索引小于数组容量
public void enQueue(T element){ elements[(front + size) % elements.length] = element; size++; } 复制代码
移除队列头部元素，front所在的范围小于数组容量
public T deQueue(){ // 先获取对头的元素 T frontEle = elements[front]; // 将对头的元素置为空 elements[front] = null; // 队头要往后移动一次 // front++; front = (front + 1) % elements.length; // 长度-1 size--; // 返回队头元素 return frontEle; } 复制代码
清楚队列中的元素，遍历所有的元素，置为null
public void clear(){ for (int i = 0; i < elements.length; i++) { elements[i] = null; } size = 0; front = 0; } 复制代码
增加测试类
public class CircleQueueTest { CircleQueue<Integer> queue = null; @Before public void init(){ queue = new CircleQueue<>(); queue.enQueue(11); queue.enQueue(22); queue.enQueue(33); System.out.println("Init CircleQueue: " + queue); } @Test public void front() { System.out.println("CircleQueue Front: " + queue.front()); } @Test public void enQueue() { queue.enQueue(55); System.out.println("After enQueue: " + queue); } @Test public void deQueue() { queue.deQueue(); System.out.println("After deQueue: " + queue); } } 复制代码
增加toString方法
@Override public String toString() { return "CircleQueue{" + "front=" + front + ", size=" + size + ", elements=" + Arrays.toString(elements) + '}'; } 复制代码
执行所有的测试方法
特殊情况测试
@Test public void deQueueAndEnQueue() { 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); }
