LeetCode 1188. 设计有限阻塞队列

Categories:

题目描述
思路分析
1. 解法一：锁 + 条件变量 + 环形数组（推荐）
相似题目

题目描述

✅ 1188. 设计有限阻塞队列

思路分析

解法一：锁 + 条件变量 + 环形数组（推荐）

核心思路：

使用环形数组保存队列元素，head 指向队首，tail 指向下一个写入位置。

通过互斥锁保证并发安全，使用 notFull 与 notEmpty 条件变量实现阻塞。

入队时队满则等待，出队时队空则等待。

复杂度分析：

时间复杂度：O(1)，入队、出队均为常数操作。

空间复杂度：O(capacity)，环形数组容量为固定大小。

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

class BoundedBlockingQueue {
    private final int[] data;
    private int head;
    private int tail;
    private int size;
    private final ReentrantLock lock;
    private final Condition notFull;
    private final Condition notEmpty;

    public BoundedBlockingQueue(int capacity) {
        this.data = new int[capacity];
        this.lock = new ReentrantLock();
        this.notFull = lock.newCondition();
        this.notEmpty = lock.newCondition();
    }

    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try {
            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
}

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()
    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()
    q.mu.Unlock()
}

func (q *BoundedBlockingQueue) Dequeue() int {
    q.mu.Lock()
    for q.size == 0 {
        q.notEmpty.Wait()
    }

    // 读取队首元素
    val := q.data[q.head]
    q.head = (q.head + 1) % q.cap
    q.size--

    q.notFull.Signal()
    q.mu.Unlock()
    return val
}

func (q *BoundedBlockingQueue) Size() int {
    q.mu.Lock()
    size := q.size
    q.mu.Unlock()
    return size
}

相似题目

题目	难度	考察点
1114. 按序打印	简单	并发控制
1115. 交替打印 FooBar	中等	条件变量
1116. 打印零与奇偶数	中等	并发控制
1195. 交替打印字符串	中等	并发控制
1226. 哲学家进餐	中等	并发控制

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/11043513