public class Queue<E> implements QueueInterface<E> {
    private Array<E> array;
    public Queue(int capacity) {
        array = new Array<>(capacity);
    }
    public Queue() {
        this(10);
    }
    @Override
    public void enqueue(E e) {
//        加入元素
        array.addLast(e);
    }
    @Override
    public E dequeue() {
//        取出第一个元素
        return array.removeFirst();
    }
    @Override
    public E getFront() {
        return array.getFirst();
    }
    @Override
    public int getSize() {
        return array.getSize();
    }
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue [");
        for(int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if(i != array.getSize() - 1) {
                res.append(",");
            }
        }
        res.append("]");
        return  res.toString();
    }
}

public class LoopQueue<E> implements QueueInterface<E> {
    private E[] arr;
    private int front;
    private int tail;
    private int size;
    public LoopQueue(int capacity) {
//        为了满足tail + 1 == front为满
        arr = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }
    public LoopQueue() {
        this(10);
    }
    @Override
    public void enqueue(E e) {
//        入队
        if((tail + 1) % arr.length == front) {
//            未删除，并且队列已满
//            throw new Error("(tail + 1) % arr.length == front, 队列已满");
            resize(getCapacity() * 2);
        }
        arr[tail] = e;
        tail = (tail + 1) % arr.length;
        size++;
    }
    public void resize(int capacity) {
        E[] newArr = (E[]) new Object[capacity + 1];
        // 巧妙地使用了size。让i来控制front向下移动。
        for(int i = 0; i < size; i++) {
//            这里就将队列中的元素按顺序加入了
            newArr[i] = arr[(i + front) % arr.length];
        }
        arr = newArr;
        front = 0;
        tail = size;
    }
    @Override
    public E dequeue() {
        if(isEmpty()) {
            throw new Error("Queue is empty");
        }
        E e = arr[front];
        arr[front] = null;
//        移动头指针。
        front = (front + 1) % arr.length;
        size--;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0)  {
            resize(getCapacity() / 2);
        }
        return e;
    }
    @Override
    public E getFront() {
        if(isEmpty()) {
            throw new Error("Queue is empty");
        }
        return arr[front];
    }
    public int getCapacity() {
        return arr.length - 1;
    }
    @Override
    public int getSize() {
        return size;
    }
    @Override
    public boolean isEmpty() {
        return false;
    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("LoopQueue capacity %d, size %d", getCapacity(), size));
        res.append(" front [");
        for(int i = front; i != tail ; i = (i + 1) % arr.length) {
            res.append(arr[i]);
            if((i + 1) % arr.length != tail) {
                res.append(",");
            }
        }
        res.append("] tail");
        return  res.toString();
    }
}