【每日一道算法题】设计有限阻塞队列

实现一个拥有如下方法的线程安全有限阻塞队列：

BoundedBlockingQueue(int capacity) 构造方法初始化队列，其中capacity代表队列长度上限。
void enqueue(int element) 在队首增加一个element. 如果队列满，调用线程被阻塞直到队列非满。
int dequeue() 返回队尾元素并从队列中将其删除. 如果队列为空，调用线程被阻塞直到队列非空。
int size() 返回当前队列元素个数。
你的实现将会被多线程同时访问进行测试。每一个线程要么是一个只调用enqueue方法的生产者线程，
要么是一个只调用dequeue方法的消费者线程。size方法将会在每一个测试用例之后进行调用。

请不要使用内置的有限阻塞队列实现，否则面试将不会通过。

输入:
1
1
["BoundedBlockingQueue","enqueue","dequeue","dequeue","enqueue","enqueue","enqueue","enqueue","dequeue"]
[[2],[1],[],[],[0],[2],[3],[4],[]]

输出:
[1,0,2,2]

解释:
生产者线程数目 = 1
消费者线程数目 = 1

BoundedBlockingQueue queue = new BoundedBlockingQueue(2);   // 使用capacity = 2初始化队列。

queue.enqueue(1);   // 生产者线程将1插入队列。
queue.dequeue();    // 消费者线程调用dequeue并返回1。
queue.dequeue();    // 由于队列为空，消费者线程被阻塞。
queue.enqueue(0);   // 生产者线程将0插入队列。消费者线程被解除阻塞同时将0弹出队列并返回。
queue.enqueue(2);   // 生产者线程将2插入队列。
queue.enqueue(3);   // 生产者线程将3插入队列。
queue.enqueue(4);   // 生产者线程由于队列长度已达到上限2而被阻塞。
queue.dequeue();    // 消费者线程将2从队列弹出并返回。生产者线程解除阻塞同时将4插入队列。
queue.size();       // 队列中还有2个元素。size()方法在每组测试用例最后调用。

解法：

class BoundedBlockingQueue {
    int maxLength;
    LinkedList<Integer> list;
    ReentrantLock lock;
    Condition empty;
    Condition full;
    public BoundedBlockingQueue(int capacity) {
        list =  new LinkedList();
        maxLength = capacity;
        lock = new ReentrantLock();
        empty = lock.newCondition();
        full = lock.newCondition();
    }
    
    public void enqueue(int element) throws InterruptedException {
        try {
            lock.lock();
            while(list.size()==maxLength){
                full.await();
            }
            list.addFirst(element);
            empty.signal();
            } catch (InterruptedException r) {
        } finally {
            lock.unlock();
        }
    }
    
    public int dequeue() throws InterruptedException {
        int res = 0;
        try {
            lock.lock();
        while(list.size()==0){
            empty.await();
        }
        res = list.removeLast();    
        full.signal();
        
            } catch (InterruptedException r) {
        } finally {
            lock.unlock();
            return res;
        }
    }
    
    public int size() {
        return list.size();
    }
}