黑马数据结构讲义
基础数据结构-081-优先级队列-堆实现-1
堆实现优先级队列课程文档
一、堆的实现方式
- 堆本质上是基于树结构实现的数据结构
- 常用实现方式：完全二叉树（Complete Binary Tree）
二、完全二叉树定义
结构特征：
- 每个节点最多有两个子节点（二叉树特性）
- 除最后一层外，所有层都完全填满
- 最后一层节点必须从左向右连续填充
- 当完全填满时（所有层都填满）仍视为完全二叉树
示例说明：
100
/ \
19 36
/ \ / \
17 3 25 1
/ \
2 7• 第0层（根节点层）必然填满
• 前n-1层必须完全填满
• 最后一层节点从左向右连续排列
三、大顶堆与小顶堆
- 大顶堆（Max Heap）
• 性质：任意节点值 ≥ 其子节点值
• 示例：
100
/ \
36 19
/ \ / \
25 11 17 3
/ \
2 7• 验证规则：
• 根节点100 > 子节点36,19
• 节点36 > 子节点25,11
• 节点19 > 子节点17,3
• 节点17 > 子节点2,7
- 小顶堆（Min Heap）
• 性质：任意节点值 ≤ 其子节点值
• 修正后的示例：
1
/ \
3 6
/ \ / \
9 5 10 7• 验证规则：
• 根节点1 < 子节点3,6
• 节点3 < 子节点9,5
• 节点6 < 子节点10,7
四、完全二叉树的数组存储
存储规则（从索引0开始）：
索引：0 1 2 3 4 5 6 7 8
数值：100 19 36 17 3 25 1 2 7节点关系公式
父节点索引计算：
• 已知子节点索引i（i>0）• 父节点索引 = ⌊(i-1)/2⌋
子节点索引计算：
• 已知父节点索引i• 左子节点 = 2i + 1
• 右子节点 = 2i + 2
示例验证：
• 节点25（索引5）：
• 父节点索引 = ⌊(5-1)/2⌋ = 2 → 值36
• 节点17（索引3）：
• 左子节点 = 2*3+1 = 7 → 值2
• 右子节点 = 2*3+2 = 8 → 值7
边界条件
• 根节点（索引0）无父节点
• 计算子节点时需要验证索引是否超出数组范围（size为数组长度）
五、堆的特性总结
- 非线性数据结构，但可线性存储于数组
- 插入新节点时遵循完全二叉树填充规则
- 大/小顶堆维护堆序性保证高效取极值操作
- 数组存储方式实现O(1)时间复杂度访问父子节点
附：公式符号说明
• ⌊x⌋ 表示对x向下取整
• 索引从0开始的计算体系
• 数组size表示当前存储元素数量
基础数据结构-082-优先级队列-堆实现-2
大顶堆实现优先级队列技术文档
一、实现原理
大顶堆特性：
• 完全二叉树结构• 父节点值 >= 子节点值
• 根节点（数组索引0）始终是最大元素
核心优势：
• 入队/出队时间复杂度：O(log n)• 直接访问堆顶元素（O(1)时间复杂度）
二、入队操作（offer方法）
算法步骤
将新元素插入数组末尾（索引size位置）
执行上浮调整（Heapify Up）：
public boolean offer(E e) { if (isFull()) return false; int child = size++; // 记录新元素初始位置 int parent = (child - 1) / 2; // 父节点索引计算公式 // 上浮调整 while (child > 0 && e.priority > elements[parent].priority) { elements[child] = elements[parent]; // 父节点下移 child = parent; parent = (child - 1) / 2; } elements[child] = e; // 最终位置 return true; }调整过程示例
插入元素200时的调整过程：200与父节点4比较 → 交换
200与父节点19比较 → 交换
200与父节点100比较 → 交换
200到达根节点，调整完成
三、出队操作（poll方法）
算法步骤
交换堆顶与末尾元素
执行下沉调整（Heapify Down）：
public E poll() { if (isEmpty()) return null; swap(0, size-1); // 交换首尾元素 E removed = elements[--size]; // 下沉调整 int parent = 0; while (true) { int left = 2 * parent + 1; int right = 2 * parent + 2; int max = parent; if (left < size && elements[left].priority > elements[max].priority) { max = left; } if (right < size && elements[right].priority > elements[max].priority) { max = right; } if (max == parent) break; swap(parent, max); parent = max; } return removed; }调整过程示例
取出堆顶元素后的调整：末尾元素7交换到堆顶
比较左右子节点（19和36）→ 选择36交换
比较新位置的子节点（17和25）→ 选择25交换
到达叶子节点，调整完成
四、核心方法对比
| 操作 | 时间复杂度 | 关键步骤 |
|---|---|---|
| 入队offer | O(log n) | 末尾插入 + 上浮调整 |
| 出队poll | O(log n) | 首尾交换 + 下沉调整 |
| 查看peek | O(1) | 直接返回elements[0] |
五、关键公式
父节点索引计算：
parent = (child - 1) / 2子节点索引计算：
• 左子节点：2 * parent + 1• 右子节点：
2 * parent + 2
六、优势总结
- 插入删除效率优于有序数组实现（O(n) → O(log n)）
- 无需完整排序即可快速获取最大值
- 内存连续存储，缓存友好
注：文档已修正原录音中的术语错误（如"poor"→poll，"PK"→比较操作），优化代码示例中的边界条件处理，确保算法正确性。
基础数据结构-083-优先级队列-堆实现-3
堆数据结构出队操作详解
一、核心操作步骤
1.1 元素出队流程
交换堆顶与尾部元素
• 将堆顶元素（索引0）与最后一个有效元素（索引size-1）进行交换• 示例代码实现：
swap(0, size-1);移除尾部元素
• 缩小堆大小：size--• 暂存并返回移除的优先级最高元素：
E removed = (E) array[size]; array[size] = null; // 帮助垃圾回收 return removed;堆顶元素下潜（下沉）
• 从新堆顶开始与其子节点比较• 循环条件：父节点 < 子节点中的较大者
• 终止条件：父节点 >= 所有子节点 或 无子节点
1.2 下潜算法实现
private void down(int parent) {
int max = parent;
int left = 2 * parent + 1;
int right = left + 1;
// 左子节点比较
if (left < size && priorityCompare(left, max) > 0) {
max = left;
}
// 右子节点比较
if (right < size && priorityCompare(right, max) > 0) {
max = right;
}
// 需要交换时递归下潜
if (max != parent) {
swap(parent, max);
down(max); // 递归处理新位置
}
}二、完整代码实现
2.1 交换方法（关键工具函数）
private void swap(int i, int j) {
Object temp = array[i];
array[i] = array[j];
array[j] = temp;
}2.2 出队主逻辑
public E poll() {
if (isEmpty()) return null;
// 交换堆顶与末尾
swap(0, size-1);
// 移除并处理元素
size--;
E result = (E) array[size];
array[size] = null; // GC辅助
// 执行下潜
down(0);
return result;
}2.3 查看堆顶元素
public E peek() {
return isEmpty() ? null : (E) array[0];
}三、算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 入队(offer) | O(log n) | O(1) |
| 出队(poll) | O(log n) | O(1) |
| 查看(peek) | O(1) | O(1) |
四、实现优势对比
4.1 不同实现方式对比
| 实现方式 | 入队复杂度 | 出队复杂度 | 适用场景 |
|---|---|---|---|
| 无序数组 | O(1) | O(n) | 低频出队操作 |
| 有序数组 | O(n) | O(1) | 高频出队低频入队 |
| 堆实现（当前方案） | O(log n) | O(log n) | 高频率入队出队操作 |
五、关键要点说明
堆结构调整
• 每次出队后只需调整O(log n)次比较• 保证堆始终满足：父节点 >= 子节点
下潜终止条件
• 当父节点大于等于所有子节点时• 当节点到达叶子节点层级时
垃圾回收优化
• 显式将移除位置置为null• 防止内存泄漏
六、测试用例示例
@Test
public void testPriorityQueue() {
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.offer(5);
queue.offer(1);
assert(queue.poll() == 5);
assert(queue.peek() == 3);
assert(queue.poll() == 3);
assert(queue.poll() == 1);
assert(queue.isEmpty());
}七、常见问题处理
空队列处理
• poll()和peek()需进行null检查• 返回null或抛出异常根据设计需求决定
元素比较策略
• 需实现优先级比较方法• 示例比较逻辑：
private int priorityCompare(int i, int j) { return ((Comparable<E>) array[i]).compareTo((E) array[j]); }数组扩容策略
• 当size达到数组容量时自动扩容• 建议扩容系数为1.5-2倍
基础数据结构-084-优先级队列-e01-合并多个有序链表1
力扣23题《合并K个升序链表》小顶堆解法详解
概述
本课程讲解如何通过小顶堆（最小堆）实现多个有序链表的合并，该解法相比分治法具有更优的时间复杂度（O(Nlogk)）。本文对课程录音进行整理，修正文字转换错误并优化技术表述。
算法思路
核心思想
初始化阶段：将所有链表的头节点加入小顶堆
循环处理：
• 取出堆顶元素（当前最小值）加入结果链表• 将被取出节点的后继节点加入堆中
终止条件：当堆为空时完成合并
示例演示
给定三个链表：
1->4->5
1->3->4
2->6操作流程：
- 初始堆元素：1(1号链表)、1(2号链表)、2
- 取出1(1号链表)，加入4(1号链表)
- 取出1(2号链表)，加入3(2号链表)
- 取出2，加入6
- 依次处理后续节点直至堆空
小顶堆实现关键代码
数据结构定义
class MinHeap {
private ListNode[] array;
private int size;
public MinHeap(int capacity) {
array = new ListNode[capacity];
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
}节点上浮（offer方法）
public void offer(ListNode node) {
int child = size++;
array[child] = node;
// 上浮逻辑
while (child > 0) {
int parent = (child - 1) >>> 1;
if (array[child].val >= array[parent].val) break;
swap(child, parent);
child = parent;
}
}节点下潜（poll方法）
public ListNode poll() {
swap(0, size-1);
size--;
ListNode result = array[size];
array[size] = null;
// 下潜逻辑
int parent = 0;
while (true) {
int left = parent*2 + 1;
int right = left + 1;
int min = parent;
if (left < size && array[left].val < array[min].val) {
min = left;
}
if (right < size && array[right].val < array[min].val) {
min = right;
}
if (min == parent) break;
swap(parent, min);
parent = min;
}
return result;
}算法实现要点
堆容量优化：初始容量设为链表数量k，动态扩容非必需
节点比较：直接使用ListNode的val值进行比较
时间复杂度：
• 堆初始化：O(k)• 每次poll和offer操作：O(logk)
• 总时间复杂度：O(Nlogk)（N为总节点数）
与分治法对比
| 方法 | 时间复杂度 | 空间复杂度 | 实现难度 |
|---|---|---|---|
| 分治法 | O(Nlogk) | O(1) | 中等 |
| 小顶堆（本方法） | O(Nlogk) | O(k) | 较易 |
常见问题解答
如何处理相同值节点？
堆中按插入顺序维护，不影响最终排序结果链表指针何时后移？
仅在节点被取出后移动指针，确保每次只处理有效节点空链表处理策略？
初始化时自动跳过空链表，无需特殊处理堆的动态扩容问题？
力扣测试用例规模可控，初始设为k可避免扩容
本解法通过小顶堆有效维护了当前各链表的最小节点，是处理多路归并问题的经典方法。建议结合分治解法对比学习，加深对时间复杂度分析的理解。
基础数据结构-084-优先级队列-e01-合并多个有序链表2
合并K个升序链表算法详解
一、问题描述
给定一个包含K个升序链表的数组lists[]，要求将这些链表合并为一个新的升序链表并返回。
二、算法思路
核心思想
使用小顶堆（最小堆）数据结构实现高效的最小值获取，通过维护堆大小为链表数量K来优化空间复杂度。
关键步骤
初始化小顶堆
• 堆容量设置为链表数组长度lists.length• 遍历所有链表，将每个链表的头节点入堆（过滤空链表）
构建结果链表
• 使用哨兵节点(sentinel)简化链表操作• 循环从堆顶取出最小值，直到堆为空：
- 将取出节点加入结果链表尾部
- 若该节点有后继节点，将后继节点加入堆
空间优化
• 仅维护K个节点的堆结构（而非所有元素）• 保证空间复杂度为O(K)而非O(N)
三、完整代码实现
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
MinHeap heap = new MinHeap(k);
// 初始化堆：将各链表头节点入堆
for (ListNode node : lists) {
if (node != null) {
heap.offer(node);
}
}
// 构建结果链表
ListNode sentinel = new ListNode(-1);
ListNode tail = sentinel;
while (!heap.isEmpty()) {
ListNode min = heap.poll();
tail.next = min;
tail = tail.next;
if (min.next != null) {
heap.offer(min.next);
}
}
return sentinel.next;
}
// 小顶堆实现（内部类）
static class MinHeap {
private final ListNode[] heap;
private int size;
public MinHeap(int capacity) {
heap = new ListNode[capacity];
}
public void offer(ListNode node) {
int i = size++;
siftUp(i, node);
}
public ListNode poll() {
if (size == 0) return null;
ListNode removed = heap[0];
ListNode last = heap[--size];
siftDown(0, last);
return removed;
}
public boolean isEmpty() {
return size == 0;
}
private void siftUp(int k, ListNode node) {
while (k > 0) {
int parent = (k-1)/2;
if (node.val >= heap[parent].val) break;
heap[k] = heap[parent];
k = parent;
}
heap[k] = node;
}
private void siftDown(int k, ListNode node) {
int half = size/2;
while (k < half) {
int child = 2*k + 1;
ListNode c = heap[child];
int right = child + 1;
if (right < size && c.val > heap[right].val) {
c = heap[child = right];
}
if (node.val <= c.val) break;
heap[k] = c;
k = child;
}
heap[k] = node;
}
}
}四、算法分析
时间复杂度
• 建堆操作：O(K)
• 每次堆操作：O(logK)
• 总时间复杂度：O(NlogK)（N为总节点数）
空间复杂度
• 堆空间：O(K)
• 结果链表：O(1)（原地修改指针）
五、关键问题解答
Q：为什么不将所有链表元素一次性全部入堆？
A：虽然将所有元素入堆可以实现相同功能，但会导致：
- 空间复杂度升至O(N)
- 建堆时间复杂度升至O(NlogN)
- 当K远小于N时（如K=10，N=10^6），维护K大小的堆空间优势明显
Q：如何处理空链表输入？
A：在初始化阶段通过if (node != null)过滤空链表，避免无效节点入堆
六、测试案例
输入链表：
1->4->5
1->3->4
2->6合并过程：
- 初始入堆节点：1(1st)、1(2nd)、2
- 依次取出：1→1→2→3→4→4→5→6
最终结果：
1->1->2->3->4->4->5->6七、扩展思考
当K较大时（如K=10^5），分治策略（两两合并）与堆策略的对比：
• 分治时间复杂度：O(NlogK)
• 堆策略时间复杂度：O(NlogK)
• 实际选择取决于具体实现和内存限制，堆方法更易实现且代码简洁
基础数据结构-085-阻塞队列-问题提出
多线程环境下队列的线程安全问题及解决方案
课程概述
本课程重点分析队列在多线程环境下的线程安全问题，通过生产者-消费者模型演示未考虑线程安全时可能出现的异常情况，并提出解决方案。
核心概念
生产者-消费者模型
• 生产者：通过offer方法向队列添加元素的线程
• 消费者：通过poll方法从队列获取元素的线程
• 问题场景：生产者和消费者可能运行在不同线程，共享同一队列
现有实现存在的问题
- 线程安全问题
// 简化版队列实现（存在线程安全问题）
class UnsafeQueue {
private String[] elements = new String[10];
private int tail = 0;
public boolean offer(String e) {
elements[tail] = e; // 步骤1：赋值操作
tail++; // 步骤2：指针递增
return true;
}
}多线程问题复现流程：
| 时间序列 | 线程T1操作 | 线程T2操作 | 队列状态 |
|---|---|---|---|
| t1 | elements[0] = "E1" | - | ["E1", null,...] |
| t2 | (未执行tail++) | elements[0] = "E2" | ["E2", null,...] |
| t3 | - | tail++ → 1 | ["E2", null,...] |
| t4 | tail++ → 2 | - | ["E2", null,...] |
最终结果：元素"E1"被覆盖，tail=2但有效数据仅1个
- 阻塞处理问题
• poll方法：队列空时立即返回null，需循环重试（CPU空转）
• offer方法：队列满时直接返回false，无法阻塞等待
问题验证（Debug示例）
- 设置线程级断点观察并发操作
- 演示线程切换导致的数据覆盖现象
- 最终队列状态验证：
elements = ["E2", null, ...] // 预期应为["E1", "E2", ...] tail = 2 // 正确但数据不一致
解决方案
线程安全实现
class SafeQueue {
private final Object lock = new Object();
private String[] elements = new String[10];
private int tail = 0;
public boolean offer(String e) {
synchronized(lock) {
elements[tail] = e;
tail++;
return true;
}
}
}改进方向
阻塞机制：
• 队列满时offer阻塞等待• 队列空时
poll阻塞等待条件变量：
• 使用wait()/notify()实现高效等待容量控制：
• 添加队列容量限制• 实现动态扩容机制
关键知识点总结
- 原子操作：赋值与指针递增必须保持原子性
- 可见性问题：多线程环境下变量值的可见性保证
- 锁机制：使用synchronized实现互斥访问
- 生产-消费协调：后续可扩展为阻塞队列实现
后续课程预告
• 实现线程安全的阻塞队列
• 条件变量的具体应用
• 队列容量动态扩容机制
• 性能优化与锁粒度控制
（文档已修正原录音中的术语错误，包括："县城"→"线程"，"pol方法"→"poll方法"，"PVE方法"→"poll/take方法"，"alpha方法"→"offer方法"等，并优化了技术表述的准确性）
基础数据结构-086-阻塞队列-单锁实现-1
Java 多线程锁机制详解
一、锁机制简介
在多线程编程中，为了防止代码交错执行导致的数据不一致问题，Java 提供了两种锁实现方案：
synchronized关键字（内置锁）ReentrantLock类（可重入锁）
二、synchronized 与 ReentrantLock 对比
| 特性 | synchronized | ReentrantLock |
|---|---|---|
| 实现级别 | JVM 关键字级实现 | JDK 类库实现 |
| 功能特性 | 基础锁机制 | 支持可中断、超时、公平锁等 |
| 锁释放 | 自动释放 | 必须显式调用 unlock() |
| 可重入性 | 支持 | 支持 |
| 等待可中断 | 不支持 | 支持 lockInterruptibly() |
三、ReentrantLock 使用步骤
- 创建锁对象
private final ReentrantLock lock = new ReentrantLock();- 标准使用模板
lock.lock(); // 在 try 代码块外获取锁
try {
// 受保护的临界区代码
} finally {
lock.unlock(); // 确保锁释放
}- 关键方法说明
•lock()：阻塞式获取锁
• unlock()：释放锁
• lockInterruptibly()：可中断式获取锁
四、异常处理机制
必须使用 try-finally 结构保证锁的释放：
lock.lock();
try {
// 可能抛出异常的代码
criticalSection();
} finally {
lock.unlock();
}这种结构确保：
• 正常执行时必然释放锁
• 代码异常时仍会释放锁
• 线程终止前保证锁释放
五、锁的排他性验证
通过线程调试演示：
- 线程 T1 成功获取锁后执行临界区代码
- 线程 T2 在 lock() 处阻塞等待
- T1 执行 unlock() 后，T2 被唤醒并获取锁
- 两个线程的临界区代码呈现串行执行效果
六、可中断锁机制
- 使用场景
当需要实现：
• 等待锁时可响应中断
• 设置获取锁的超时时间
• 避免无限期阻塞
- 实现方式
try {
lock.lockInterruptibly();
try {
// 临界区代码
} finally {
lock.unlock();
}
} catch (InterruptedException e) {
// 处理中断异常
Thread.currentThread().interrupt();
}- 与 lock() 的区别
lock() lockInterruptibly() 响应中断 否 是 阻塞特性 不可中断等待 可中断等待 异常处理 无检查异常 抛出 InterruptedException
七、重要概念说明
- 可重入性：同一线程可重复获取已持有的锁
- 公平性：通过构造方法参数设置（默认非公平）
new ReentrantLock(true); // 创建公平锁 - 等待队列：未获锁线程进入队列等待
- 锁状态：通过 isLocked() 方法查询
八、最佳实践建议
- 锁对象声明为 final 防止意外修改
- 避免在临界区内执行阻塞操作
- 锁的获取和释放必须成对出现
- 推荐使用 tryLock() 实现超时控制
- 监控锁等待时间避免死锁
九、锁的性能考量
• 低竞争场景：synchronized 性能更优
• 高竞争场景：ReentrantLock 提供更好的吞吐量
• 使用建议：优先考虑 synchronized，需要高级功能时使用 ReentrantLock
通过合理使用锁机制，可以有效解决多线程环境下的资源竞争问题，保证线程安全性和数据一致性。开发者需要根据具体场景选择合适的锁实现，并注意避免死锁、锁饥饿等并发问题的发生。
基础数据结构-087-阻塞队列-单锁实现-2
以下是整理后的课程文档（已修正错别字并优化表述）：
并发队列实现详解
一、核心实现逻辑
- 队列状态判断
• 新增size变量用于辅助判断队列状态
• 初始值：size = 0
• 判断逻辑：
boolean isFull() {
return size == array.length;
}
boolean isEmpty() {
return size == 0;
}- offer 方法优化
public boolean offer(E e) {
lock.lock();
try {
// 队列满时的处理
while (isFull()) {
tailWait.await(); // 当前线程进入阻塞
}
// 添加元素逻辑
array[tail] = e;
size++;
// 处理尾指针循环
if (++tail == array.length) {
tail = 0;
}
return true;
} finally {
lock.unlock();
}
}- 条件变量使用
// 创建条件变量
private Condition tailWait = lock.newCondition();
// 唤醒机制（在poll方法中）
public E poll() {
lock.lock();
try {
// ... 取元素逻辑
// 取出元素后唤醒等待添加的线程
tailWait.signal();
return element;
} finally {
lock.unlock();
}
}二、关键机制解析
阻塞唤醒原理
队列满时阻塞：
• 调用tailWait.await()将当前线程加入条件队列• 自动释放锁并进入 WAITING 状态
唤醒机制：
• 当其他线程取出元素（poll）后调用tailWait.signal()• 注意：signal() 必须在持有锁时调用
环形数组实现
• 尾指针循环逻辑：
if (++tail == array.length) {
tail = 0;
}• 实现数组空间的循环利用
三、测试案例演示
场景：队列满时阻塞与唤醒
初始化队列：
// 创建容量为10的队列 BlockingQueue<String> queue = new ArrayBlockingQueue<>(10); // 添加10个元素填满队列 for (int i = 0; i < 10; i++) { queue.offer("E" + i); }添加第11个元素（线程T1）：
new Thread(() -> { System.out.println("开始添加第11个元素..."); queue.offer("E10"); // 在此处阻塞 System.out.println("添加成功！"); }, "T1").start();唤醒线程（线程T2）：
new Thread(() -> { System.out.println("开始唤醒..."); lock.lock(); try { tailWait.signal(); } finally { lock.unlock(); } }, "T2").start();
四、实现注意事项
线程安全：
• 所有状态修改必须在加锁状态下进行• 使用
try-finally保证锁的释放虚假唤醒防护：
• 推荐使用while(isFull())而非if判断• 防止被意外唤醒时状态未改变
性能优化：
• 使用两个条件变量（生产/消费分开）• 批量唤醒机制（signalAll()）
死锁预防：
• 保证锁的获取顺序一致性• 避免嵌套获取多个锁
五、扩展知识
- 条件变量特性
• 每个 Condition 维护独立的等待队列
• signal() 随机唤醒单个线程
• signalAll() 唤醒所有等待线程
- 与synchronized对比
特性 synchronized Lock + Condition 等待队列数量 1 多个 中断响应 不支持 支持 超时控制 有限支持 完善支持 公平性 非公平 可配置
本实现完整展示了基于ReentrantLock和Condition实现的线程安全队列核心机制，可用于理解Java并发包中BlockingQueue的实现原理。
基础数据结构-088-阻塞队列-单锁实现-3
阻塞队列多线程条件变量问题解析
问题背景
在实现阻塞队列时，使用if条件判断队列状态会导致"虚假唤醒"问题。当多个线程竞争锁时，被唤醒的线程可能未重新检查队列状态，导致数据不一致。
问题复现
代码漏洞示例
// 有漏洞的代码片段
public void offer(E e) throws InterruptedException {
lock.lock();
try {
if (size == array.length) { // 问题点：应使用while循环
tailWait.await();
}
array[tail] = e;
tail = (tail + 1) % array.length;
size++;
headWait.signal();
} finally {
lock.unlock();
}
}执行时序分析
| 时间线 | 线程操作 | 队列状态 | 关键操作 |
|---|---|---|---|
| T1 | offer(4) | [1,2,3]（满） | 进入tailWait等待 |
| T2 | poll()取出元素1 | [2,3]（未满） | 唤醒tailWait线程 |
| T3 | offer(5)抢占锁成功 | [2,3] | 直接插入元素5 |
| T4 | 原offer(4)恢复执行 | [2,3,5]（满） | 未重新检查size，导致溢出插入错误 |
问题本质：虚假唤醒
- 条件变量特性：被唤醒的线程需要与新到达的线程竞争锁
- 状态变化：在等待期间队列状态可能被其他线程修改
- 非原子恢复：被唤醒线程直接从await()后继续执行，未重新检查条件
解决方案
将if条件判断改为while循环：
// 修复后的代码
public void offer(E e) throws InterruptedException {
lock.lock();
try {
while (size == array.length) { // 正确做法
tailWait.await();
}
array[tail] = e;
tail = (tail + 1) % array.length;
size++;
headWait.signal();
} finally {
lock.unlock();
}
}while循环优势
- 重新检查机制：每次获得锁后强制检查当前状态
- 防止状态过期：确保执行时条件仍然成立
- 线程安全保证：处理多线程竞争时的状态一致性
阻塞队列完整实现
类结构定义
public class ArrayBlockingQueue<E> implements BlockingQueue<E> {
private final E[] array;
private int head;
private int tail;
private int size;
private final ReentrantLock lock = new ReentrantLock();
private final Condition headWait = lock.newCondition(); // poll等待条件
private final Condition tailWait = lock.newCondition(); // offer等待条件
@SuppressWarnings("unchecked")
public ArrayBlockingQueue(int capacity) {
array = (E[]) new Object[capacity];
}
}方法实现规范
- offer方法
@Override
public void offer(E e) throws InterruptedException {
lock.lock();
try {
while (size == array.length) {
tailWait.await();
}
array[tail] = e;
tail = (tail + 1) % array.length;
size++;
headWait.signal();
} finally {
lock.unlock();
}
}- poll方法
@Override
public E poll() throws InterruptedException {
lock.lock();
try {
while (size == 0) {
headWait.await();
}
E e = array[head];
array[head] = null; // 帮助GC
head = (head + 1) % array.length;
size--;
tailWait.signal();
return e;
} finally {
lock.unlock();
}
}设计要点
线程安全保证
• 使用ReentrantLock实现互斥访问• 通过size字段准确跟踪队列状态
阻塞控制机制
• 队列满时：offer线程进入tailWait等待• 队列空时：poll线程进入headWait等待
唤醒策略
• 插入成功后唤醒poll等待队列• 删除成功后唤醒offer等待队列
循环数组实现
• 使用head/tail指针实现环形缓冲区• 模运算处理数组边界
常见问题解答
Q：为什么不能用if代替while？
A：当线程被唤醒时，队列状态可能已被其他线程修改，while循环确保每次操作前都进行最新状态检查。
Q：signal()和signalAll()的区别？
A：signal()随机唤醒一个等待线程，signalAll()唤醒全部。在精确的条件控制下，signal()效率更高。
Q：为什么需要两个条件变量？
A：将生产者和消费者的等待队列分离，避免无效唤醒。当队列状态变化时，只唤醒对应类型的线程。
基础数据结构-089-阻塞队列-单锁实现-4
线程安全队列实现文档
核心方法实现说明
- 辅助方法
1.1 isEmpty()
public boolean isEmpty() {
return size == 0;
}• 功能：判断队列是否为空
• 实现：当队列大小(size)等于0时返回true
1.2 isFull()
public boolean isFull() {
return size == array.length;
}• 功能：判断队列是否已满
• 实现：当队列大小(size)等于数组长度时返回true
- offer() 方法实现
2.1 加锁机制
public boolean offer(E e) throws InterruptedException {
lock.lockInterruptibly();
try {
// ...
} finally {
lock.unlock();
}
}• 使用 lockInterruptibly() 获取可中断锁
• 必须通过 try-finally 保证锁的释放
2.2 等待队列不满
while (isFull()) {
notFull.await();
}• 使用 while 循环防止虚假唤醒
• 当队列满时，在 notFull 条件变量上等待
2.3 添加元素逻辑
array[tail] = e;
tail = (tail + 1) % array.length;
size++;- 将元素放入尾部位置
- 更新尾指针：采用取模运算实现循环数组
- 队列大小自增
2.4 唤醒消费线程
notEmpty.signal();• 添加成功后唤醒在 notEmpty 条件变量上等待的消费线程
- poll() 方法实现
3.1 加锁机制
public E poll() throws InterruptedException {
lock.lockInterruptibly();
try {
// ...
} finally {
lock.unlock();
}
}• 使用与 offer() 相同的锁机制
3.2 等待队列非空
while (isEmpty()) {
notEmpty.await();
}• 使用 while 循环防止虚假唤醒
• 当队列空时，在 notEmpty 条件变量上等待
3.3 获取元素逻辑
E result = array[head];
array[head] = null; // Help GC
head = (head + 1) % array.length;
size--;- 获取头部元素
- 显式置空数组位置帮助垃圾回收
- 更新头指针：采用取模运算实现循环数组
- 队列大小自减
3.4 唤醒生产线程
notFull.signal();• 移除成功后唤醒在 notFull 条件变量上等待的生产线程
关键设计要点
线程安全保证
• 使用 ReentrantLock 保证操作的原子性• 通过两个条件变量(notEmpty/notFull)实现精准唤醒
循环数组实现
tail = (tail + 1) % array.length head = (head + 1) % array.length• 通过取模运算实现数组循环使用
虚假唤醒防护
while (condition) { await(); }• 必须使用 while 循环检查条件，不能用 if
资源释放优化
array[head] = null; // Help GC• 显式释放引用加速垃圾回收
信号通知机制
• 生产者唤醒消费者，消费者唤醒生产者• 避免无效的线程唤醒操作
完整类结构示意
public class BlockingQueue<E> {
private final E[] array;
private int head;
private int tail;
private int size;
private final ReentrantLock lock;
private final Condition notEmpty;
private final Condition notFull;
// 构造函数及核心方法...
}本实现通过精确的锁控制和条件变量管理，在保证线程安全的同时实现了高效的生产者-消费者模式，适用于需要高吞吐量的并发场景。
基础数据结构-090-阻塞队列-单锁实现-5
带超时功能的 offer 方法实现详解
方法作用
在队列满时提供有限等待机制
相比单参数offer方法的改进：
• 原方法：线程无限期等待，直到被其他线程唤醒• 新方法：添加超时参数，超过指定时间自动放弃等待
• 返回值语义：
◦ true：元素添加成功
◦ false：超时或队列仍满时添加失败
实现原理
核心技术点
使用Condition的awaitNanos()替代await()
时间单位转换：
long t = TimeUnit.MILLISECONDS.toNanos(timeout);处理虚假唤醒：
• 每次循环更新剩余等待时间• 使用返回值跟踪剩余纳秒数
完整实现逻辑
public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException {
Objects.requireNonNull(e);
long t = unit.toNanos(timeout); // 时间单位转换
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (isFull()) {
if (t <= 0L) // 检查剩余时间
return false;
t = notFull.awaitNanos(t); // 更新剩余等待时间
}
add(e); // 实际添加元素的方法
notEmpty.signal();
return true;
} finally {
lock.unlock();
}
}关键机制解析
时间处理流程：
• 将用户输入时间转换为纳秒• 每次等待后更新剩余时间(t)
• 当t ≤ 0时放弃等待
虚假唤醒处理：
• 循环检查队列状态• 即使被提前唤醒仍会继续等待剩余时间
线程协作：
• 添加成功后触发notEmpty信号• 与poll方法形成协作机制
测试案例
场景1：超时失败
BlockingQueue<String> queue = new ArrayBlockingQueue<>(3);
queue.offer("任务1");
queue.offer("任务2");
queue.offer("任务3");
long start = System.currentTimeMillis();
boolean result = queue.offer("任务4", 5000, TimeUnit.MILLISECONDS); // 等待5秒
long end = System.currentTimeMillis();
System.out.println("添加结果：" + result); // 输出：false
System.out.println("实际等待：" + (end - start) + "ms"); // ≈5000ms
System.out.println("队列状态：" + queue); // 仍包含任务1-3场景2：提前唤醒成功
// 在另一个线程中
new Thread(() -> {
try {
Thread.sleep(2000);
String item = queue.poll(); // 2秒后取出元素
System.out.println("取出：" + item);
} catch (InterruptedException e) { /* 处理异常 */ }
}).start();
// 主线程操作同场景1
// 输出结果：
// 添加结果：true
// 实际等待：≈2000ms
// 队列状态：[任务2, 任务3, 任务4]扩展实现建议
对称实现poll方法的超时版本：
public E poll(long timeout, TimeUnit unit) { // 实现逻辑与offer方法镜像对称 // 使用notEmpty.awaitNanos() }注意事项：
• 保持锁的获取/释放严格配对• 正确处理中断异常
• 确保状态判断的原子性
性能优化建议
时间精度处理：
• 高并发场景考虑微秒级精度• 合理设置超时阈值
监控建议：
• 统计等待超时发生率• 监控队列平均等待时间
容量规划：
• 根据超时设置合理规划队列容量• 结合业务流量进行压力测试
注：本文档已修正原始录音中的术语错误（如"poor线程"→"poll线程"），并规范了技术术语表达。代码示例采用Java语法，实际实现需根据具体编程语言特性调整。