定义队列接口
package ArrayQueue; public interface Queue<E> { //1、入队 void enqueue(E e); //2、出队 E dequeue(); //3、查询队首元素 E getFront(); //4、查询队尾元素 E getRear(); //5、查询队列存放多少个元素的个数 int getSize(); //6、查询队列是否为空 boolean isEmpty(); }实现队列方法
package ArrayQueue; public class LoopQueue<E>implements Queue<E> { E[]array; int front,rear,size; //初始化数组 public LoopQueue(int capacity) { array=(E[])new Object[capacity+1]; front =0; rear =0; size=0; } public LoopQueue() { this(10); } // 获取队列的容量 >方便一下阔容 public int getCapacity() { // TODO Auto-generated method stub return array.length-1; } // 扩容 private void resize(int newCapacity) { /* * 扩容要做事，新键数组，数组迭代更换;同时跟新头部和尾部 */ E []newArray=(E[])new Object[newCapacity+1]; for(int i=0;i<size;i++) { newArray[i]=array[(i+front)%array.length]; } array=newArray; front =0; //同时更新一下头部为0 rear=size; //尾部为size; } // 入队 @Override public void enqueue(E e) { // TODO Auto-generated method stub // 如果队尾+1等于头部 证明队列为满 需要扩容 if((rear+1)%array.length==front) { resize(getCapacity()*2); } // 增加元素 array[rear]=e; // 维护rear ,size rear =(rear+1)%array.length; size++; } @Override public E dequeue() { // TODO Auto-generated method stub if(isEmpty()) { throw new IllegalArgumentException("no elements"); } // 将待出队的队首元素存放在临时变量res中 E res=array[front]; array[front]=null; front=(front+1)%array.length; size--; if(size==getCapacity()/4&&getCapacity()/2!=0) { resize(getCapacity()/2); } return res; } @Override public E getFront() { // TODO Auto-generated method stub return array[front]; } // 查询队尾元素 @Override public E getRear() { // TODO Auto-generated method stub return array[rear]; } // 查询队列总元素个数 @Override public int getSize() { // TODO Auto-generated method stub return size; } // 查询队列是否为空 @Override public boolean isEmpty() { // TODO Auto-generated method stub return front==rear; } //重写toString @Override public String toString() { StringBuilder res=new StringBuilder(); res.append(String.format("LoopQueue:size=%d,capacity=%d", size,getCapacity())); res.append("\nfront["); //遍历队列 重新调整队列 for(int i=front;i!=rear;i=(i+1)%array.length) { res.append(array[i]); if(i!=rear-1) { res.append(","); } } res.append("]rear"); return res.toString(); } }进行测试
package ArrayQueue; import java.util.Random; public class LoopQueueTest { public static void main(String[] args) { LoopQueue<Integer> q=new LoopQueue<Integer>(); for(int i=1;i<=15;i++) { q.enqueue(i); } for(int i=1;i<=5;i++) { q.dequeue(); } System.out.println(q); System.out.println("查询队列是否为空:"+q.isEmpty()); System.out.println("队列总元素:"+q.getSize()); System.out.println("队列总容量:"+q.getCapacity()); System.out.println("查询队首元素:"+q.getFront()); } } 测试显示：