スズトキヅキ's Vignette

1
/**
2
 * LeetCode 1188. 设计有限阻塞队列 (Design Bounded Blocking Queue)
3
 * 题目要求：
4
 * 1. 实现一个线程安全的有限阻塞队列，包含以下方法：
5
 *    - BoundedBlockingQueue(int capacity)：构造函数，初始化队列最大容量
6
 *    - void enqueue(int element)：入队操作，队列满时阻塞线程，直到队列有空闲空间
7
 *    - int dequeue()：出队操作，返回并移除队尾元素；队列空时阻塞线程，直到队列有元素
8
 *    - int size()：返回当前队列元素个数（线程安全）
9
 * 2. 测试场景：多线程并发访问，线程分为仅调用enqueue的生产者、仅调用dequeue的消费者
10
 * 3. 约束：
11
 *    - 1 <= capacity <= 30
12
 *    - 1 <= 生产者线程数 <= 8
13
 *    - 1 <= 消费者线程数 <= 8
14
 */

1
class BoundedBlockingQueue {
2
private:
3
    int _capacity;               // 队列最大容量
4
    vector<int> _q;              // 底层存储容器
5
    mutex mtx;                   // 保护临界区的互斥锁
6
    mutex log_mtx;               // 日志打印锁，避免输出错乱
7

8

9
public:
10
    // 构造函数：初始化队列容量
11
    BoundedBlockingQueue(int capacity) : _capacity(capacity) {
12
        _q.reserve(capacity); // 预留空间，减少vector扩容开销
13
    }
14

15
    // 入队：队列满时阻塞（无条件变量，用优化版忙等）
16
    void enqueue(int element) {
17
        while (true) {
18
            // 第一步：加锁检查队列是否有空间
19
            {
20
                lock_guard<mutex> lock(mtx);
21
                if (_q.size() < _capacity) {
22
                    // 有空间，执行入队
23
                    _q.push_back(element);
24
                    return; // 入队成功，退出
25
                }
26
            } // 锁自动释放，避免阻塞其他线程
27

28
            // 第二步：队列满，短暂休眠后重试（优化忙等，减少CPU占用）
29
            this_thread::sleep_for(chrono::milliseconds(1)); // 1ms休眠，替代yield
30
        }
31
    }
32

33
    // 出队：队列空时阻塞（无条件变量，用优化版忙等）
34
    int dequeue() {
35
        while (true) {
36
            // 第一步：加锁检查队列是否有元素
37
            {
38
                lock_guard<mutex> lock(mtx);
39
                if (!_q.empty()) {
40
                    // 有元素，执行出队（取队尾+移除队尾，符合题目要求）
41
                    int val = _q.back();
42
                    _q.pop_back(); // 真正移除元素，修复你之前的核心错误
43
                    return val; // 出队成功，退出
44
                }
45
            } // 锁自动释放
46

47
            // 第二步：队列空，短暂休眠后重试
48
            this_thread::sleep_for(chrono::milliseconds(1));
49
        }
50
    }
51

52
    // 返回队列大小（线程安全）
53
    int size() {
54
        lock_guard<mutex> lock(mtx); // RAII加锁，自动释放
55
        return _q.size(); // 直接返回真实大小，无需自定义计数
56
    }
57
};
58

59
// ===================== 测试代码（无修改） =====================
60
atomic<int> produced_count(0);
61
atomic<int> consumed_count(0);
62

63
const int QUEUE_CAPACITY = 5;    // 队列容量
64
const int PRODUCER_NUM = 3;      // 生产者线程数
65
const int CONSUMER_NUM = 2;      // 消费者线程数
66
const int TOTAL_ELEMENTS = 20;   // 总生产元素数
67

68
// 生产者函数
69
void producer(BoundedBlockingQueue& queue) {
70
    while (produced_count < TOTAL_ELEMENTS) {
71
        int val = produced_count++;
72
        queue.enqueue(val);
73
        this_thread::sleep_for(chrono::milliseconds(50)); // 模拟生产耗时
74
    }
75
}
76

77
// 消费者函数
78
void consumer(BoundedBlockingQueue& queue) {
79
    while (consumed_count < TOTAL_ELEMENTS) {
80
        int val = queue.dequeue();
81
        consumed_count++;
82
        this_thread::sleep_for(chrono::milliseconds(100)); // 模拟消费耗时
83
    }
84
}
85

86
int main() {
87
    BoundedBlockingQueue queue(QUEUE_CAPACITY);
88

89
    // 创建生产者线程
90
    vector<thread> producers;
91
    for (int i = 0; i < PRODUCER_NUM; ++i) {
92
        producers.emplace_back(producer, ref(queue));
93
    }
94

95
    // 创建消费者线程
96
    vector<thread> consumers;
97
    for (int i = 0; i < CONSUMER_NUM; ++i) {
98
        consumers.emplace_back(consumer, ref(queue));
99
    }
100

101
    // 等待所有线程完成
102
    for (auto& t : producers) t.join();
103
    for (auto& t : consumers) t.join();
104

105
    // 输出最终测试结果
106
    cout << "===== 最终测试结果 =====" << endl;
107
    bool is_success = (produced_count == TOTAL_ELEMENTS)
108
        && (consumed_count == TOTAL_ELEMENTS)
109
        && (queue.size() == 0);
110

111
    if (is_success) {
112
        cout << "✅ 测试通过：所有元素正常生产并消费，队列最终为空" << endl;
113
    }
114
    else {
115
        cout << "❌ 测试失败：" << endl;
116
        cout << "  - 计划生产/消费数：" << TOTAL_ELEMENTS << endl;
117
        cout << "  - 实际生产数：" << produced_count << endl;
118
        cout << "  - 实际消费数：" << consumed_count << endl;
119
        cout << "  - 队列最终大小：" << queue.size() << endl;
120
    }
121

122
    return 0;
123
}