[LeetCode] 1188. 设计有限阻塞队列(Medium)Java语言题解

1.题目相关

①题目及示例

Alt text
Alt text

②相关标签

  • 多线程

③题目地址


2.解题方法

  • 使用 LinkedList 集合模拟阻塞队列
  • 存储当前队列元素个数的变量是 AtomicInteger 类型(来保证原子性)

①synchronized 关键字 + this 锁对象

  • 使用 synchronized 关键字对入队和出队操作加锁
  • 使用 Object 对象的 wait 方法 和 notify 方法控制两个线程的相互等待和唤醒操作

②lock + condition

  • 使用 lock 对入队和出队操作加锁
  • 使用 condition 控制两个线程的相互等待和唤醒操作

3.代码详解

①synchronized 关键字 + this 锁对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 1.synchronized关键字+this锁对象
class BoundedBlockingQueue {
// 用线程安全的集合实现一个阻塞队列
private LinkedList<Integer> list = new LinkedList<>();
// 存储当前队列元素个数
AtomicInteger size = new AtomicInteger(0);
// 存储队列长度上限
private volatile int capacity;

public BoundedBlockingQueue(int capacity) {
this.capacity = capacity;
}

public void enqueue(int element) throws InterruptedException {
synchronized (this) {
// 如果队列满,调用线程被阻塞直到队列非满。
while (size.get() >= capacity) {
// 线程阻塞时会释放锁
this.wait();
}
// 在队首增加一个element
list.addFirst(element);
// 当前队列元素个数加一
size.incrementAndGet();
// 通知消费者线程可以继续消费了
this.notify();
}
}

public int dequeue() throws InterruptedException {
synchronized (this) {
// 如果队列空,调用线程被阻塞直到队列非空。
while (size.get() == 0) {
// 线程阻塞时会释放锁
this.wait();
}
// 返回队尾元素并从队列中将其删除
int value = list.getLast();
list.removeLast();
// 当前队列元素个数减一
size.decrementAndGet();
// 通知生产者线程可以继续生产了
this.notify();
return value;
}
}

public int size() {
return size.get();
}
}

②lock + condition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 2.lock+condition
class BoundedBlockingQueue {
// 用线程安全的集合实现一个阻塞队列
private LinkedList<Integer> list = new LinkedList<>();
// 存储当前队列元素个数
AtomicInteger size = new AtomicInteger(0);
// 存储队列长度上限
private volatile int capacity;
// 可重入锁
private Lock lock = new ReentrantLock();
Condition procuder = lock.newCondition();
Condition consumer = lock.newCondition();

public BoundedBlockingQueue(int capacity) {
this.capacity = capacity;
}

public void enqueue(int element) throws InterruptedException {
try {
lock.lock();
// 如果队列满,调用线程被阻塞直到队列非满。
while (size.get() >= capacity) {
// 线程阻塞时会释放锁
procuder.await();
}
// 在队首增加一个element
list.addFirst(element);
// 当前队列元素个数加一
size.incrementAndGet();
// 通知消费者线程可以继续消费了
consumer.signal();
} finally {
lock.unlock();
}
}

public int dequeue() throws InterruptedException {
try {
lock.lock();
// 如果队列空,调用线程被阻塞直到队列非空。
while (size.get() == 0) {
// 线程阻塞时会释放锁
consumer.await();
}
// 返回队尾元素并从队列中将其删除
int value = list.getLast();
list.removeLast();
// 当前队列元素个数减一
size.decrementAndGet();
// 通知生产者线程可以继续生产了
procuder.signal();
return value;
} finally {
lock.unlock();
}
}

public int size() {
return size.get();
}
}

附录

0%