数组实现的环形队列

基本思想：

• 环形展开成链表，在链表上模拟环形队列；
• head 和tail只增不减，add 、remove、size都很好理解；
• 初始容量是2的n次方； PS，优秀的数据结构肯定是结构和数据都很巧妙的~

public class CirQueue {
    Integer[] container;
//head指向next坑位
    int head = 0;
//tail指向最后一个有效坑位
    int tail = -1;
    int size = 4;

    public CirQueue() {
        //初始化size最好是2^n，当head增长到特比大的时候，head和tail一块右移
        this.container = new Integer[4];
    }

    public boolean add(Integer x) {
        if (size() >= size) {
            return false;
        }
        //因为size=2^n，所以与操作最方便了
        //tail和head只增不减，但是你会发现，tail和head的低位才真正起作用。
        container[head & (size - 1)] = x;
        head++;
        if (tail == -1) {
            //初始化，tail
            tail++;
        }
        return true;
    }

    public Integer removeHead() {
        if (head <= 0) {
            //未开始
            return null;
        }
        if (head <= tail) {
            //已结束
            return null;
        }
        Integer t= container[(this.head - 1) & (size - 1)];
        container[(this.head - 1) & (size - 1)] = null;
        this.head--;
        return t;
    }

    public Integer removeTail() {
        if (tail >= head) {
            return null;
        }
        Integer tail = container[this.tail & (size - 1)];
        container[this.tail & (size - 1) & (size - 1)] = null;
        this.tail++;
        return tail;
    }

    public int size() {
        return head - tail-1;
    }

    public static void main(String[] args) {
        CirQueue cirQueue = new CirQueue();
        System.out.println(cirQueue.add(1));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(2));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(3));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(4));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(5));

        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.removeHead());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.removeTail());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());

        System.out.println(cirQueue.add(6));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(7));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());

        System.out.println(cirQueue.removeHead());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.removeHead());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.removeHead());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.removeHead());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());

        System.out.println(cirQueue.add(8));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(9));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(10));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.add(11));
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());

        System.out.println(cirQueue.removeTail());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.removeTail());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
        System.out.println(cirQueue.removeHead());
        System.out.println(Arrays.toString(cirQueue.container));
        System.out.println(cirQueue.size());
    }
}