public interface Queue<E> {
    void offer(E val);//入隊(duì)
    E poll();//出隊(duì)，返回出隊(duì)的值
    E peek();//返回隊(duì)首元素
    boolean isEmpty();//判斷是否為空
}
 
 
import java.util.NoSuchElementException;
 
//基于整型的循環(huán)隊(duì)列
public class LoopQueue implements Queue<Integer>{
    private Integer[] data;
    private int head;//隊(duì)首元素
    private int tail;//隊(duì)尾元素的下一個(gè)位置
    private int size;//當(dāng)前元素個(gè)數(shù)
    public LoopQueue(int n){
        //n為希望保存的元素個(gè)數(shù)
        //在循環(huán)隊(duì)列中要浪費(fèi)一個(gè)元素空間，來判斷是否已滿，所以 +1
        data = new Integer[n + 1];
        }
 
    @Override
    //添加元素
    public void offer(Integer val) {
        if(isFull()){
            throw new ArrayIndexOutOfBoundsException("queue is full, cannot offer new val");
        }
        data[tail] = val;
        //tail向后移
        tail = (tail + 1) % data.length;
        size++;
    }
 
    @Override
    //出隊(duì)
    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queues empty!cannot poll");
        }
        Integer val = data[head];
        //head向后移動(dòng)
        head = (head + 1) % data.length;
        size--;
        return val;
    }
 
    @Override
    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queues empty!cannot poll");
        }
        return data[head];
    }
 
    @Override
    //判斷是否為空
    public boolean isEmpty() {
        return tail == head;
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front[");
        //取得最后一個(gè)元素的下標(biāo)
        int lastIndex = tail == 0 ? data.length-1 : tail-1;
        for (int i = head; i != tail; ) {
            sb.append(data[i]);
            if (i != lastIndex){
                sb.append(",");
            }
            i = (i+1) % data.length;
 
        }
        sb.append("]tail");
        return sb.toString();
    }
    //判斷隊(duì)列是否已滿
    public boolean isFull(){
        return (tail + 1) % data.length == head;
    }
}

//代碼測試
public class LoopQueueTest {
    public static void main(String[] args) {
        Queue<Integer> loopQueue = new LoopQueue(5);
        for (int i = 0; i < 5; i++) {
            loopQueue.offer(i+1);
        }
        System.out.println(loopQueue);
//        loopQueue.offer(1);
        System.out.println(loopQueue.poll());
        System.out.println(loopQueue);
    }
}