# LEETCODE 1188. Design Bounded Blocking Queue 解题思路分析

• BoundedBlockingQueue(int capacity) 构造方法初始化队列，其中capacity代表队列长度上限。
• void enqueue(int element) 在队首增加一个element. 如果队列满，调用线程被阻塞直到队列非满。
• int dequeue() 返回队尾元素并从队列中将其删除. 如果队列为空，调用线程被阻塞直到队列非空。
• int size() 返回当前队列元素个数。

```输入:
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.```

```输入:
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.```

```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();
}```

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 se;
Semaphore sd;
int size;
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();
}```