实现阻塞队列

题目描述
阻塞队列是一种支持阻塞操作的队列，常用于生产者-消费者模型。当队列为空时，消费者线程尝试取元素会被阻塞，直到队列非空；当队列已满时，生产者线程尝试添加元素会被阻塞，直到队列有空位。需要实现一个线程安全的阻塞队列，支持put（添加元素）和take（取出元素）方法。

解题过程

1. 核心思路分析
阻塞队列需满足：

• 线程安全：多线程并发操作时数据需一致。
• 阻塞机制：通过条件变量（如ReentrantLock中的Condition）实现等待/唤醒。
• 循环数组：使用数组模拟队列，通过指针循环利用空间。

2. 基础结构定义
使用数组存储数据，维护队头（head）和队尾（tail）指针，以及队列当前元素数量（count）：

class BlockingQueue<T> {
    private final Object[] data;
    private int head = 0, tail = 0, count = 0;
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notEmpty = lock.newCondition();  // 非空条件
    private final Condition notFull = lock.newCondition();   // 非满条件

    public BlockingQueue(int capacity) {
        this.capacity = capacity;
        data = new Object[capacity];
    }
}

3. put方法实现（添加元素）

• 获取锁后检查队列是否已满，若满则等待notFull条件。
• 将元素放入队尾，更新指针和数量。
• 唤醒等待notEmpty的消费者线程。

public void put(T item) throws InterruptedException {
    lock.lock();
    try {
        while (count == capacity) {  // 必须用while防止虚假唤醒
            notFull.await();         // 队列已满，阻塞生产者
        }
        data[tail] = item;
        tail = (tail + 1) % capacity; // 循环指针
        count++;
        notEmpty.signal();           // 唤醒可能等待的消费者
    } finally {
        lock.unlock();
    }
}

4. take方法实现（取出元素）

• 获取锁后检查队列是否为空，若空则等待notEmpty条件。
• 从队头取出元素，更新指针和数量。
• 唤醒等待notFull的生产者线程。

public T take() throws InterruptedException {
    lock.lock();
    try {
        while (count == 0) {         // 必须用while防止虚假唤醒
            notEmpty.await();        // 队列为空，阻塞消费者
        }
        T item = (T) data[head];
        head = (head + 1) % capacity; // 循环指针
        count--;
        notFull.signal();            // 唤醒可能等待的生产者
        return item;
    } finally {
        lock.unlock();
    }
}

5. 关键细节说明

• 循环指针：通过取模运算实现head和tail的循环移动，避免数组越界。
• 条件变量使用：
  • await()会释放锁，被唤醒后重新获取锁。
  • 必须用while而非if：防止虚假唤醒（spurious wakeup）导致条件重检失败。
• 线程安全：所有操作受锁保护，确保原子性。

6. 扩展优化

• 超时机制：可添加poll(timeout)和offer(timeout)方法，使用Condition.awaitNanos()实现限时等待。
• 公平性：ReentrantLock可设置为公平锁，避免线程饥饿。

总结
阻塞队列的核心是锁+条件变量的协同使用，通过循环数组高效管理数据，确保生产者-消费者模型的正确性与效率。实现时需注意线程安全、循环指针边界处理以及条件变量的正确使用方式。