LeetCode 1188. 设计有限阻塞队列
题目描述
题意分析
实现容量固定的线程安全先进先出队列。入队时若已满，调用必须等待直到出现空位；出队时若为空，必须等待直到有元素，不能直接返回失败或占位值。
size返回一次受同步保护的当前元素数。多个生产者和消费者可能同时调用接口，因此不仅要保证元素顺序，还要保证不会超出容量、从空队列读值，或让并发读写观察到不一致的头尾位置与数量。
解法：锁 + 条件变量 + 环形数组
核心思路
[!blue]
用定长环形数组保存队列，
head指向下一个要取出的元素，tail指向下一个要写入的位置，移动时对容量取模。size表示有效元素数，范围始终是零到容量；因为空和满时都可能出现head == tail，必须结合数量区分两者。一把互斥锁同时保护数组读写、头尾下标和数量。线程取得锁后先检查是否能执行；入队写尾部并增加数量，出队读头部并减少数量，这几项更新在同一临界区完成。其他线程只能在拿到同一把锁后检查，所以不会看到中间某一项刚更新、其他项还没有跟上的状态。
队列满时，生产者等待
notFull；队列空时，消费者等待notEmpty。条件等待会把释放锁和进入等待连成一个操作，让对侧线程有机会改变队列；被唤醒后，必须重新取得同一把锁才能继续。若只是持锁反复检查，对侧无法入队或出队，条件就永远不会改变。唤醒只表示条件可能成立，不是预留了一个元素或空位。Java 还允许虚假唤醒；Go 的条件等待由通知唤醒，但同样不保证醒来后优先抢到锁，其他同侧调用可能已经占用了资源。因此两种实现都必须在循环里复检满或空，只有当前持锁检查仍满足时才执行操作。这与 Java Condition 和 Go Cond 的等待语义一致。
入队完整更新后，通知一个等待非空的消费者；出队完整更新后，通知一个等待非满的生产者。两类等待者分开，才能把刚产生的一份资源通知给能使用它的对侧。所有退出路径通过
finally或defer解锁；size也用同一把锁读取，得到的是读取时刻的有效快照。Go 的两个条件对象持有
&q.mu，构造函数因此返回队列指针，之后也不能复制这个队列值。否则新对象中被加锁的互斥量可能与条件对象仍引用的旧锁不同，破坏整套同步关系。
解题步骤
- 初始化容量对应的数组、头尾下标和数量，创建互斥锁及绑定它的非满、非空两个条件。
- 入队取得锁后，循环等待队列非满；写入尾部、环形推进尾指针并增加数量，再通知非空条件。
- 出队取得锁后，循环等待队列非空；取出头部、环形推进头指针并减少数量，再通知非满条件。
- 完成或异常退出时都释放锁；出队返回刚取出的值。
- 查询数量时同样加锁读取，再解锁返回。
代码实现
class BoundedBlockingQueue {
private final int[] data;
private int head;
private int tail;
private int size;
private final java.util.concurrent.locks.ReentrantLock lock;
private final java.util.concurrent.locks.Condition notFull;
private final java.util.concurrent.locks.Condition notEmpty;
public BoundedBlockingQueue(int capacity) {
this.data = new int[capacity];
this.lock = new java.util.concurrent.locks.ReentrantLock();
// 两个条件变量必须派生自同一把锁。
this.notFull = lock.newCondition();
this.notEmpty = lock.newCondition();
}
public void enqueue(int element) throws InterruptedException {
lock.lock();
try {
// 必须用 while：应对虚假唤醒，以及醒来后空位被同侧线程抢走。
while (size == data.length) {
notFull.await();
}
data[tail] = element;
tail = (tail + 1) % data.length;
size++;
// 状态更新完成后再唤醒对侧。
notEmpty.signal();
} finally {
lock.unlock();
}
}
public int dequeue() throws InterruptedException {
lock.lock();
try {
// 消费者同样循环复检，醒来时元素可能已被其他消费者取走。
while (size == 0) {
notEmpty.await();
}
int val = data[head];
head = (head + 1) % data.length;
size--;
notFull.signal();
return val;
} finally {
lock.unlock();
}
}
// 只读查询也必须和入队、出队使用同一把锁。
public int size() {
lock.lock();
try {
return size;
} finally {
lock.unlock();
}
}
}
import "sync"
type BoundedBlockingQueue struct {
cap int
data []int
head int
tail int
size int
mu sync.Mutex
notFull *sync.Cond
notEmpty *sync.Cond
}
// 必须返回指针：Cond 持有 &q.mu，返回值拷贝会让锁与条件变量指向不同的对象。
func Constructor(capacity int) *BoundedBlockingQueue {
q := &BoundedBlockingQueue{
cap: capacity,
data: make([]int, capacity),
}
q.notFull = sync.NewCond(&q.mu)
q.notEmpty = sync.NewCond(&q.mu)
return q
}
func (q *BoundedBlockingQueue) Enqueue(element int) {
q.mu.Lock()
defer q.mu.Unlock()
// 必须用 for：醒来后重新抢锁时，空位可能已被同侧 goroutine 抢走。
for q.size == q.cap {
q.notFull.Wait()
}
q.data[q.tail] = element
q.tail = (q.tail + 1) % q.cap
q.size++
// 状态更新完成后再唤醒对侧。
q.notEmpty.Signal()
}
func (q *BoundedBlockingQueue) Dequeue() int {
q.mu.Lock()
defer q.mu.Unlock()
// 消费者同样循环复检，醒来时元素可能已被其他消费者取走。
for q.size == 0 {
q.notEmpty.Wait()
}
val := q.data[q.head]
q.head = (q.head + 1) % q.cap
q.size--
q.notFull.Signal()
return val
}
// 只读查询也必须和入队、出队使用同一把锁。
func (q *BoundedBlockingQueue) Size() int {
q.mu.Lock()
defer q.mu.Unlock()
return q.size
}
复杂度分析
- 时间复杂度：构造初始化数组为 $O(capacity)$。成功入队、出队的实际数据更新及一次数量读取为 $O(1)$；等待、锁竞争和重新唤醒可能持续多久，取决于其他调用，不能承诺整次调用恒定时间。
- 空间复杂度：队列自身保存 $O(capacity)$ 个槽位，锁和条件对象数量固定；等待线程的运行时开销不计入数组存储。
关键点总结
[!green]
- 环形数组保持 FIFO，数量区分头尾重合时的空与满。
- 条件检查和状态更新都使用同一把锁，等待期间则必须释放锁。
- 被通知后重新加锁并循环检查，通知不代表资源已经归当前线程所有。
- 等待本侧需要的条件，完成后通知对侧，所有返回路径保证解锁。
- Go 的条件对象和互斥量必须保持绑定在同一个队列实例上。
易错点总结
[!yellow]
- 用
if代替循环等待，醒来后可能在队列再次变满或变空时继续错误操作。- 持锁空转等待，阻止对侧线程取得锁改变条件，造成无法推进。
- 只给修改方法加锁，却无同步地读取数量，仍会和并发写入发生竞争。
- Java 等待被中断后没有通过
finally解锁，会把其他调用永久挡在锁外。- 入队后通知非满、出队后通知非空，唤醒了不能利用新状态的错误一侧。
- 复制 Go 队列值后继续使用，会让条件等待和普通操作可能锁住不同的互斥量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 622. 设计循环队列 | 中等 | 普通有界队列满或空时直接报告失败，本题需要阻塞并在条件变化时唤醒等待线程。 |
| 1115. 交替打印 FooBar | 中等 | 同样通过等待与通知控制可执行时机，本题条件由队列容量和元素数决定，而非固定交替。 |