class CircularQueue<T> {
    
    private Object[] data; //數據存儲數組
    private int head; //隊列頭指針
    private int tail; //隊列尾指針
    private int size; //隊列長度

    /**
     * 初始化
     *
     * @param k
     */
    public CircularQueue(int k) {
        data = new Object[k]; //數組初始化
        head = -1;
        tail = -1;
        size = k;
    }

    /**
     * 元素入隊，成功則返回true，否則false
     *
     * @param value
     * @return
     */
    public boolean put(T value) {
        if (isFull() == true) { //入隊，判斷隊滿
            return false;
        }
        if (isEmpty() == true) { //入隊，隊空，則head置0
            head = 0;
        }
        tail = (tail + 1) % size; //循環隊列，隊尾循環移動，所以使用取余的方式移動隊尾
        data[tail] = value; //將入隊元素放入隊列
        return true;
    }

    /**
     * 出隊
     *
     * @return
     */
    public T remove() {
        T result = null;
        if (isEmpty() == true) { //出隊、判斷隊空
            return result;
        }
        if (head == tail) { //隊首 隊尾重合，則當前隊列只剩唯一元素
            result = (T) data[tail];
            head = -1;
            tail = -1;
            return result;
        }
        result = (T) data[head];
        data[head] = null;
        head = (head + 1) % size;
        return result;
    }

    /**
     * 獲取隊首元素
     *
     * @return
     */
    public T head() {
        if (isEmpty() == true) {
            return null;
        }
        return (T) data[head];
    }

    /**
     * 獲取隊尾元素
     *
     * @return
     */
    public T tail() {
        if (isEmpty() == true) {
            return null;
        }
        return (T) data[tail];
    }

    /** 對空判斷
     *
     * @return
     */
    public boolean isEmpty() {
        return head == -1;
    }

    /** 對滿判斷
     *
     * @return
     */
    public boolean isFull() {
        return ((tail + 1) % size) == head; //尾指針再移動一位則與頭指針重合
    }

    public String toString(){
        StringBuilder str = new StringBuilder();
        for (Object datum : data) {
            if (datum != null) {
                str.append(datum);
            }
        }
        return str.toString();
    }

    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue<Integer>(5);
        queue.put(5);
        queue.put(3);
        queue.put(1);
        System.out.println(queue);
        System.out.println(queue.head());
        System.out.println(queue.tail());
        queue.remove();
        System.out.println(queue);
        System.out.println(queue.head());
        System.out.println(queue.tail());
    }
}