/**
1. 本题是ringbuffer的多线程版, 不再解释ringbuffer的内容, 只说下怎么加锁
2. 由于offer 和 offer, poll 和 poll, offer 和 poll 都是可能产生线程安全问题, 所以 offer 和 poll 要共用一把可重入锁
3. offer的情况:
    3.1 如果队列满了, offer线程就要一直等待, 直到队列被其他线程poll后产生空余时被唤醒, 注意要while, 因为被唤醒后可能其他的offer线程把空间又占用
    3.2 如果队列没满, 插入元素后, 队列中已经有了元素可以poll, 尝试唤醒poll线程
    3.3 用finally解锁,防止异常情况导致死锁
4. poll的情况是与offer对称的
*/

class BoundedBlockingQueue {

    private int[] data;
    private int head, tail, size;

    private final ReentrantLock lock;
    private Condition canPoll;
    private Condition canOffer;

    public BoundedBlockingQueue(int capacity) {
        this.size = capacity + 1;
        this.head = 0;
        this.tail = 0;
        data = new int[capacity + 1];

        lock = new ReentrantLock();
        canPoll = lock.newCondition();
        canOffer = lock.newCondition();
    }

    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try{
            while(next(tail) == head)  canOffer.await();
            data[tail] = element;
            tail = next(tail);
            canPoll.signal();
        } finally{
            lock.unlock();
        }
    }

    public int next(int x) { return (x + 1) % size;}

    public int dequeue() throws InterruptedException {
        lock.lock();
        try{
            while (tail == head) canPoll.await();
            int result = data[head];
            head = next(head);
            canOffer.signal();
            return result;
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        return head <= tail ? tail - head : tail + size - head;
    }
}