// 基于數(shù)組實(shí)現(xiàn)一個(gè)循環(huán)鏈表
public class CircleArrayQueue<T> {

    // 定義數(shù)組用于存放數(shù)據(jù)
    private T[] arr;
    private int head;  // 記錄隊(duì)列頭
    private int tail;  // 記錄隊(duì)列尾
    private int size;  // 數(shù)組大小
    // 循環(huán)鏈表初始化
    public CircleArrayQueue(int cap){
        this.arr = (T[])new Object[cap];
        this.head = 0;
        this.tail = 0;
        this.size = cap;
    }
    // 入隊(duì)方法
    public void offer(T data){
        // 判斷循環(huán)隊(duì)列是否已滿，滿了就直接return
        if((tail + 1) % size == head){
            return;
        }
        arr[tail] = data;     // 向尾加入元素
        tail = (tail + 1) % size; // 將尾指針后移1，考慮端點(diǎn)情況處理
    }
    // 出隊(duì)方法
    public T poll(){
        // 循環(huán)隊(duì)列為空則直接返回null
        if(isEmpty()){
            return null;
        }
        T pollData = arr[head];   // 找到出隊(duì)元素
        arr[head] = null;         // 清除出隊(duì)位置的元素
        head = (head + 1) % size; // 將尾指針后移1，考慮端點(diǎn)情況處理
        return pollData;
    }
    // 判斷循環(huán)隊(duì)列是否為空
    public boolean isEmpty(){
        return head == tail;
    }
    // 測(cè)試
    public static void main(String[] args) {
        CircleArrayQueue<String> arrayQueue = new CircleArrayQueue<>(5);
        arrayQueue.offer("a");
        arrayQueue.offer("b");
        arrayQueue.offer("c");
        arrayQueue.offer("d");
        arrayQueue.offer("e");
        arrayQueue.offer("f");
        System.out.println(arrayQueue);
        String poll1 = arrayQueue.poll();
        System.out.println("出隊(duì)元素：" + poll1);
        String poll2 = arrayQueue.poll();
        System.out.println("出隊(duì)元素：" + poll2);
    }
}