Design Bounded Blocking Queue
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
| class BoundedBlockingQueue {
private Semaphore enq;
private Semaphore deq;
ConcurrentLinkedDeque<Integer> q;
public BoundedBlockingQueue(int capacity) {
q = new ConcurrentLinkedDeque<>();
enq = new Semaphore(capacity);
deq = new Semaphore(0);
}
public void enqueue(int element) throws InterruptedException {
enq.acquire();
q.offer(element);
deq.release();
}
public int dequeue() throws InterruptedException {
deq.acquire();
int val = q.poll();
enq.release();
return val;
}
public int size() {
return q.size();
}
}
|
ConcurrentLinkedDeque而不是ConcurrentLinkedQueue是因为需要enque和deque, 所以是双向开的
ConcurrentLinkedDeque<Integer> q;而不是简单的LinkedList是因为q.offer(element);可能出现多线程同时q.offer(element),那么queue的顺序就不能保证了; 所以需要concurrent linked deque.- concurrent linked deque本身是unbounded的，这道题是想变为bounded；
semaphore.release()好比”放了一个permit后面就可以acquire来做事”，这样理解
其实有点意思；LRU Cache那道题是cache的容量满了就清掉least recently used那个；这道题并不是“清掉”那个元素，只是“赊账”，等待能做这个事情的时候再做，所以用semaphore确实是很好。