public class ArrayQueue<T> extends AbstractList<T>{ //定义必要的属性，容量、数组、头指针、尾指针 private int capacity; private int T[] queue; private int head; private int tail; //进行初始化，注意容量和数组的大小都需要+1；head和tail全都初始化为零 public ArrayQueue(int capacity){ this.capacity = capacity + 1; this.queue = newArray(capacity + 1); this.head = 0; this.tail = 0; } //用于建立数组，为泛型，通过指定的数据类型强制转变，生成需要的数组 private T[] newArray(int size){ return (T[]) new Object[size]; } //扩容 //首先需要计算一下原有的数组大小为多少，即size的值 //判断扩容大小和原有数组大小的值，如果扩容小了即报错，不能进行扩容 //之后将扩容容量+1 //接着新建数组，进行数组值的复制，并且重新更新容量，数组，头部，尾部 public void resize(int newcapacity){ int size = size(); if(newcapacity < size) throw new IndexOutOfBoundsException("Resizing would lose data"); newcapacity++; if(newcapacity == this.capacity){ return; } T[] newqueue = newArray(newcapacity); for(int i=0;i<size;i++){ newqueue[i] = get(i); } this.capacity = newcapacity; this.queue = newqueue; this.head = 0; this.tail = size; } //数组的大小，tail指针一直指向下一个地址，同理数组的大小需要加1 private int size(){ int diff = tail - head; if(diff < 0){ diff += capacity;//相当于取模，尾指针移动到头指针了 } return diff; } //用于resize中重数组中获取值 public T get(int i){ int size = size(); if(i < 0 || i >= size){ final String msg = "Index" + i + ", queue size" + size; throw new IndexOutOfBoundsException(msg); } int index = (head + i) % capacity; return queue[index]; } //添加元素，先添加元素，再移动尾指针，需要判断是否满了 public boolean add(T o){ queue[tail] = o; int newtail = (tail + 1) % capacity; if(newtail == head){ throw new IndexOutOfBoundsException("Queue full"); } tail = newTail; return true; } //删除元素，相当于出队，先删除头元素，之后移动头指针 public T remove(int i){ if(i != 0){ throw new IllegalArgumentException("Can only remove head of queue"); } if(head == tail){ throw new IndexOutOfBoundsException("Queue empty"); } T removed = queue[head]; head = (head + 1) % capacity; return removed; } }