D の Java

# 阻塞队列 - 单锁实现 - 2 中代码的漏洞 3 声明：只是做了一个很小的改动 但是 作用却非常的大，这是一个经验！！！ 考虑代码中的漏洞 漏洞在哪里呢？其实就在 判断 isFull 的 if 判断语句 那段代码中 为什么呢？if 怎么会有错呢？它不就是判断 队列是否 满了 ，如果满了 添加代码 不能立刻 执行 我得先让代码阻塞 将来队列不满了，我将它唤醒，唤醒后继续执行后面的添加代码。if 能有什么错呢？ 答：我们通过如下表格来进行分析，表格的 从上到下 顺序就是按照 时间顺序执行的 操作前 offer(4) offer(5) poll() 操作后 [1 2 3] 队列满，进入...

# 目前队列存在的问题 很多场景要求分离生产者，消费者两个角色，它们得由不同的线程来担当，而之前的实现根本没有考虑线程安全问题 队列为空，那么在之前的实现里会返回 null，如果就是硬要拿到一个元素呢？只能不断循环尝试 队列为满，那么再之前的实现里会返回 false，如果就是硬要塞入一个元素呢？只能不断循环尝试 所谓的生产者就是一段代码它主要调用的是 offer 方法，为队列提供元素的这个称之为 生产者 所谓的消费者就是另一段代码它主要调用的是 poll 方法，从队列中获取元素的这个称之为 消费者 # 案例代码： public class...

# 红黑树 - 概述 红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少 红黑树和 AVL 树的区别主要在于它们判断平衡的依据不一样： 之前学习的 AVL 树就是看左右子树的高度差，是不是超过了 1，超过了表示是不平衡的 红黑树判断一颗树是不是平衡 红黑树与 AVL 树相比的优势： 插入和删除时旋转次数更少 # 红黑树特性 所有节点都有两种颜色：红 与 黑 所有 null 视为 黑色 红色节点不能相邻 根节点是黑色 从根到任意一个叶子节点，路径中的黑色节点数一样 (黑色完美平衡) 第五个规则说明的是，无论到 2,4,7,9,11...

# 红黑树 - 实现 # 概述 # 历史 红黑树是一种自平衡二叉查找树，最早由一位名叫 Rudolf Bayer 的德国计算机科学家于 1972 年发明。然而，最初的树形结构不是现在的红黑树，而是一种称为 B 树的结构，它是一种多叉树，可用于在磁盘上存储大量数据。 在 1980 年代早期，计算机科学家 Leonard Adleman 和 Daniel Sleator...

# 实现动态数组 简单的动态数组类 DynamicArray ，以下是对其概述思想的介绍： 初始状态和基本参数： size ：表示动态数组的逻辑大小，即当前元素的个数。 capacity ：表示动态数组的容量，即数组的实际大小。 array ：是用于存储元素的数组。 添加元素： addLast(int element) 方法用于向数组的最后位置添加元素。它实际上调用了 add(int index, int element) 方法，并将 index 参数设置为当前的逻辑大小 size 。 add(int index, int element)...

# 优先级队列 - 有序数组实现 见名知意，它是 将 优先级 越高的 元素 越往 队列顶部 排放，最高优先级的元素 就在 队列 的顶部。 当出队列时就是将队列顶部的元素 (优先级最高的元素) 出队列 出队 变得简单了，但是 入队就相对于比较复杂了，比如说 我们要 入队一个 3 那么就需要 跟 队列中的 元素进行比较 然后找到自己适合的位置 入队就行了。 步骤如下： 1 需要先将 数组的 容量 进行扩增 2 让 入栈元素的 优先级 跟 i 指针指向的元素的优先级 进行对比，8 比 3 大 所以 将 8 向上移动一位 3 然后 i 指向下一个元素 再进行比较，5 也比 3 大 所以 5...

# 优先级队列 - 堆实现 - 小顶堆实现 如下有三个链表 分别 使用指针 p 指向 头部 p 1 -> 4 -> 5 -> null p 1 -> 3 -> 4 -> null p 2 -> 6 -> null 我们分别把 各个链表 的头部 元素 放到 小顶堆中 p 1 -> 4 -> 5 -> null p 1 -> 3 -> 4 -> null p 2 -> 6...

# 二叉树 - 深度优先遍历 对于 二叉树 而言它的 深度优先遍历 而 又可以分成 三种 分别是: pre-order: 前序遍历 in-order: 中序遍历 post-order: 后序遍历 而这三种遍历方式 它们 又有 各自的规则，除了各自规则以外 它们有一个共同特点，就是要 遍历的过程中 深入到 叶子节点 也就是深入到 离 跟节点 更远的 叶子节点 # 下面演示 每一种遍历 是怎样工作的: 下面是一个使用数组来表示的二叉树 树中的每一个节点 有两种颜色 一种就是 灰色的 表示这个节点在遍历的时候还没有访问过，还有一种是 绿色的 表示这个节点是被访问过了 # 我们先看遍历规则: #...

# 二叉搜索树的概述 之前我们已经学过了基础的数据结构了比如说：数组，链表，队列。在这些数据结构中如果我想去从中查找一个元素，这个效率高不高呢？答：并不高！都是线性时间 也就是 O (n) 如果我的需求是必须快速查找，那么我们就需要引入一种新的算法或者数据结构了 你可能会想到之前学过的 二分查找法，它能不能提高查询效率呢？ 答案：可以的！它可以达到 对数 时间，也就是 Olog (n) 不过它有限制：必须是针对一个已排序的数组 进行二分查找，但是话说回来 我们对一个数组 做排序 成本还是比较高的 先去排序再去查找，好像有点得不偿失。 那么有没有一个 折中的办法呢？答：有！就是我们换一种数据结构...

# avl 树 - 概述 前面学习过二叉搜索树就知道，如果二叉搜索树长的不平衡，就会影响到它的查找效率 我们看如下图的 不平衡的 二叉树 比如我想查询 1 的元素，那我就需要从根节点开始一路向左找，才能找到 1 的元素。而它的比较次数是 O (n) 我们怎么解决这个问题呢？我们有个办法就是旋转让上面的二叉树重新变得左右平衡 也就是让 上面的二叉树 整体向右旋转一下 这时 就比 刚才的 二叉树 平衡了一些了， 此时在查询 1 元素效率就会好一点了，而且呢。旋转也不会破坏二叉搜索树的性质 那新的问题又来了：如果判断给的二叉搜索树 是不平衡的然后让...