题目大意：
设计有限阻塞队列
实现一个拥有如下方法的线程安全有限阻塞队列：
- BoundedBlockingQueue(int capacity) 构造方法初始化队列，其中capacity代表队列长度上限。
- void enqueue(int element) 在队首增加一个element. 如果队列满，调用线程被阻塞直到队列非满。
- int dequeue() 返回队尾元素并从队列中将其删除. 如果队列为空，调用线程被阻塞直到队列非空。
- int size() 返回当前队列元素个数。
你的实现将会被多线程同时访问进行测试。每一个线程要么是一个只调用enqueue方法的生产者线程，要么是一个只调用dequeue方法的消费者线程。size方法将会在每一个测试用例之后进行调用。
注意，请不要使用现有的有限阻塞队列来实现本题。
示例1：
输入: 1 1 ["BoundedBlockingQueue","enqueue","dequeue","dequeue","enqueue","enqueue","enqueue","enqueue","dequeue"] [[2],[1],[],[],[0],[2],[3],[4],[]] 输出: [1,0,2,2] 解释: Number of producer threads = 1 Number of consumer threads = 1 BoundedBlockingQueue queue = new BoundedBlockingQueue(2); // initialize the queue with capacity = 2. queue.enqueue(1); // The producer thread enqueues 1 to the queue. queue.dequeue(); // The consumer thread calls dequeue and returns 1 from the queue. queue.dequeue(); // Since the queue is empty, the consumer thread is blocked. queue.enqueue(0); // The producer thread enqueues 0 to the queue. The consumer thread is unblocked and returns 0 from the queue. queue.enqueue(2); // The producer thread enqueues 2 to the queue. queue.enqueue(3); // The producer thread enqueues 3 to the queue. queue.enqueue(4); // The producer thread is blocked because the queue's capacity (2) is reached. queue.dequeue(); // The consumer thread returns 2 from the queue. The producer thread is unblocked and enqueues 4 to the queue. queue.size(); // 2 elements remaining in the queue. size() is always called at the end of each test case.
示例2：
输入: 3 4 ["BoundedBlockingQueue","enqueue","enqueue","enqueue","dequeue","dequeue","dequeue","enqueue"] [[3],[1],[0],[2],[],[],[],[3]] 输出: [1,0,2,1] 解释: Number of producer threads = 3 Number of consumer threads = 4 BoundedBlockingQueue queue = new BoundedBlockingQueue(3); // initialize the queue with capacity = 3. queue.enqueue(1); // Producer thread P1 enqueues 1 to the queue. queue.enqueue(0); // Producer thread P2 enqueues 0 to the queue. queue.enqueue(2); // Producer thread P3 enqueues 2 to the queue. queue.dequeue(); // Consumer thread C1 calls dequeue. queue.dequeue(); // Consumer thread C2 calls dequeue. queue.dequeue(); // Consumer thread C3 calls dequeue. queue.enqueue(3); // One of the producer threads enqueues 3 to the queue. queue.size(); // 1 element remaining in the queue. Since the number of threads for producer/consumer is greater than 1, we do not know how the threads will be scheduled in the operating system, even though the input seems to imply the ordering. Therefore, any of the output [1,0,2] or [1,2,0] or [0,1,2] or [0,2,1] or [2,0,1] or [2,1,0] will be accepted.
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1188
解题思路分析：
这是一道多线程题目，我首先想到了使用Semaphore来做线程管理，后来又仔细读了题目之后发现，题目要求不能使用现有的方法来实现，也就是说我们需要自己来实现类似Semaphore的线程管理。
看下解题时需要考虑到的核心思想。队列Queue是有数量上限要求的，在达到数量上限之后，我们无法再向Queue中添加元素，所有待添加元素应该等待另一个线程删除Queue中元素之后才能再次添加。反过来，当Queue中元素个数为0时，待删除的操作也需要等待，直到其他线程有元素添加进来。
我们可以实时监控Queue的元素个数，在执行插入操作时，如果Queue中元素个数已经达到上限，我们需要阻塞当前线程，直到队列中元素个数小于上限。同理，执行删除操作时，我们也要实时监控元素个数是否为0，如果队列为空，我们需要阻塞当前线程。
实现代码：
Queue<Integer> q = new LinkedList<>(); // 队列Queue
public BoundedBlockingQueue(int capacity) {
size = capacity; // 队列上限
}
public void enqueue(int element) throws InterruptedException {
synchronized(q){ // 保证Queue不会同时被多个线程操作
// 如果已经达到存储上限，阻塞当前线程
while(q.size()==size){
q.wait();
}
// 将元素添加至队列
q.offer(element);
// 通知所有线程队列已经被更新
q.notifyAll();
}
}
public int dequeue() throws InterruptedException {
synchronized(q){ // 保证Queue不会同时被多个线程操作
// 如果队列为空，阻塞当前线程
while(q.size()==0){
q.wait();
}
// 删除队列一个元素
int num = q.poll();
// 通知所有线程队列已经被更新
q.notifyAll();
// 返回删除元素
return num;
}
}
public int size() {
return q.size();
} 本题解法执行时间为7ms。
Runtime: 7 ms, faster than 98.91% of Java online submissions for Design Bounded Blocking Queue.
Memory Usage: 36 MB, less than 100.00% of Java online submissions for Design Bounded Blocking Queue.
最后附上使用Semaphore的实现方法，由于题目明确要求不能使用现有的已经封装好的方法，这里仅作为参考。
使用Semaphore实现方法：
Semaphore se;
Semaphore sd;
int size;
Queue<Integer> q = new LinkedList<>();
public BoundedBlockingQueue(int capacity) {
size = capacity;
se = new Semaphore(size);
sd = new Semaphore(0);
}
public void enqueue(int element) throws InterruptedException {
se.acquire();
q.offer(element);
sd.release();
}
public int dequeue() throws InterruptedException {
sd.acquire();
int num = q.poll();
se.release();
return num;
}
public int size() {
return q.size();
} 本解法执行时间同样为7ms。
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1188-design-bounded-blocking-queue-解题思路分析/