网站301在哪做,能源科技网站建设,工商查询系统,做短租类型的网站文章目录 数组概述动态数组二维数组局部性原理越界检查 链表概述单向链表单向链表#xff08;带哨兵#xff09;双向链表#xff08;带哨兵#xff09;环形链表#xff08;带哨兵#xff09; 队列概述链表实现环形数组实现 栈概述链表实现数组实现应用 双端队列概述链表实… 文章目录 数组概述动态数组二维数组局部性原理越界检查 链表概述单向链表单向链表带哨兵双向链表带哨兵环形链表带哨兵 队列概述链表实现环形数组实现 栈概述链表实现数组实现应用 双端队列概述链表实现数组实现 优先级队列无序数组实现有序数组实现堆实现 阻塞队列单锁实现双锁实现 堆二叉树存储遍历广度优先深度优先递归实现非递归实现 参考课程 https://www.bilibili.com/video/BV1Lv4y1e7HL/?share_sourcecopy_webvd_source4edb1fc2a124166c9f72a5feababcb2a 数组
概述
定义
在计算机科学中数组是由一组元素值或变量组成的数据结构每个元素有至少一个索引或键来标识 In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key 因为数组内的元素是连续存储的所以数组中元素的地址可以通过其索引计算出来例如
int[] array {1,2,3,4,5}知道了数组的数据起始地址 B a s e A d d r e s s BaseAddress BaseAddress就可以由公式 B a s e A d d r e s s i ∗ s i z e BaseAddress i * size BaseAddressi∗size 计算出索引 i i i 元素的地址 i i i 即索引在 Java、C 等语言都是从 0 开始 s i z e size size 是每个元素占用字节例如 i n t int int 占 4 4 4 d o u b l e double double 占 8 8 8
小测试
byte[] array {1,2,3,4,5}已知 array 的数据的起始地址是 0x7138f94c8那么元素 3 的地址是什么 答0x7138f94c8 2 * 1 0x7138f94ca 空间占用
Java 中数组结构为
8 字节 markword4 字节 class 指针压缩 class 指针的情况4 字节 数组大小决定了数组最大容量是 2 32 2^{32} 232数组元素 对齐字节java 中所有对象大小都是 8 字节的整数倍不足的要用对齐字节补足
例如
int[] array {1, 2, 3, 4, 5};的大小为 40 个字节组成如下
8 4 4 5*4 4(alignment)随机访问性能
即根据索引查找元素时间复杂度是 O ( 1 ) O(1) O(1)
动态数组
java 版本
public class DynamicArray implements IterableInteger {private int size 0; // 逻辑大小private int capacity 8; // 容量private int[] array {};/*** 向最后位置 [size] 添加元素** param element 待添加元素*/public void addLast(int element) {add(size, element);}/*** 向 [0 .. size] 位置添加元素** param index 索引位置* param element 待添加元素*/public void add(int index, int element) {checkAndGrow();// 添加逻辑if (index 0 index size) {// 向后挪动, 空出待插入位置System.arraycopy(array, index,array, index 1, size - index);}array[index] element;size;}private void checkAndGrow() {// 容量检查if (size 0) {array new int[capacity];} else if (size capacity) {// 进行扩容, 1.5 1.618 2capacity capacity 1;int[] newArray new int[capacity];System.arraycopy(array, 0,newArray, 0, size);array newArray;}}/*** 从 [0 .. size) 范围删除元素** param index 索引位置* return 被删除元素*/public int remove(int index) { // [0..size)int removed array[index];if (index size - 1) {// 向前挪动System.arraycopy(array, index 1,array, index, size - index - 1);}size--;return removed;}/*** 查询元素** param index 索引位置, 在 [0..size) 区间内* return 该索引位置的元素*/public int get(int index) {return array[index];}/*** 遍历方法1** param consumer 遍历要执行的操作, 入参: 每个元素*/public void foreach(ConsumerInteger consumer) {for (int i 0; i size; i) {// 提供 array[i]// 返回 voidconsumer.accept(array[i]);}}/*** 遍历方法2 - 迭代器遍历*/Overridepublic IteratorInteger iterator() {return new IteratorInteger() {int i 0;Overridepublic boolean hasNext() { // 有没有下一个元素return i size;}Overridepublic Integer next() { // 返回当前元素,并移动到下一个元素return array[i];}};}/*** 遍历方法3 - stream 遍历** return stream 流*/public IntStream stream() {return IntStream.of(Arrays.copyOfRange(array, 0, size));}
}这些方法实现都简化了 index 的有效性判断假设输入的 index 都是合法的 注意点
在java中数组的复制其底层基本都是使用的System中的arraycopy方法我们在编写第一个遍历方法的时候需要用户传入一个函数式接口而我们要选取一个什么样接口呢可以从以下两个方面考虑 能给函数式接口提供什么函数式接口能返回什么总结进什么出什么 Iterator.next()方法是先向后移动游标然后返回游标所指的元素。重点关注一下iterator接口的实现
插入或删除性能
头部位置时间复杂度是 O ( n ) O(n) O(n)
中间位置时间复杂度是 O ( n ) O(n) O(n)
尾部位置时间复杂度是 O ( 1 ) O(1) O(1)均摊来说
二维数组
int[][] array {{11, 12, 13, 14, 15},{21, 22, 23, 24, 25},{31, 32, 33, 34, 35},
};内存图如下 二维数组占 32 个字节其中 array[0]array[1]array[2] 三个元素分别保存了指向三个一维数组的引用 三个一维数组各占 40 个字节 它们在内层布局上是连续的
更一般的对一个二维数组 A r r a y [ m ] [ n ] Array[m][n] Array[m][n] m m m 是外层数组的长度可以看作 row 行 n n n 是内层数组的长度可以看作 column 列当访问 A r r a y [ i ] [ j ] Array[i][j] Array[i][j] 0 ≤ i m , 0 ≤ j n 0\leq i \lt m, 0\leq j \lt n 0≤im,0≤jn时就相当于 先找到第 i i i 个内层数组行再找到此内层数组中第 j j j 个元素列
小测试
Java 环境下不考虑类指针和引用压缩此为默认情况有下面的二维数组
byte[][] array {{11, 12, 13, 14, 15},{21, 22, 23, 24, 25},{31, 32, 33, 34, 35},
};已知 array 对象起始地址是 0x1000那么 23 这个元素的地址是什么 答 起始地址 0x1000外层数组大小16字节对象头 3元素 * 每个引用4字节 4 对齐字节 32 0x20第一个内层数组大小16字节对象头 5元素 * 每个byte1字节 3 对齐字节 24 0x18第二个内层数组16字节对象头 0x10待查找元素索引为 2最后结果 0x1000 0x20 0x18 0x10 2*1 0x104a 局部性原理
这里只讨论空间局部性
cpu 读取内存速度慢数据后会将其放入高速缓存速度快当中如果后来的计算再用到此数据在缓存中能读到的话就不必读内存了缓存的最小存储单位是缓存行cache line一般是 64 bytes一次读的数据少了不划算啊因此最少读 64 bytes 填满一个缓存行因此读入某个数据时也会读取其临近的数据这就是所谓空间局部性
对效率的影响
比较下面 ij 和 ji 两个方法的执行效率
int rows 1000000;
int columns 14;
int[][] a new int[rows][columns];StopWatch sw new StopWatch();
sw.start(ij);
ij(a, rows, columns);
sw.stop();
sw.start(ji);
ji(a, rows, columns);
sw.stop();
System.out.println(sw.prettyPrint());ij 方法一行行的遍历
public static void ij(int[][] a, int rows, int columns) {long sum 0L;for (int i 0; i rows; i) {for (int j 0; j columns; j) {sum a[i][j];}}System.out.println(sum);
}ji 方法一列列的遍历
public static void ji(int[][] a, int rows, int columns) {long sum 0L;for (int j 0; j columns; j) {for (int i 0; i rows; i) {sum a[i][j];}}System.out.println(sum);
}执行结果
0
0
StopWatch : running time 96283300 ns
---------------------------------------------
ns % Task name
---------------------------------------------
016196200 017% ij
080087100 083% ji可以看到 ij 的效率比 ji 快很多为什么呢
缓存是有限的当新数据来了后一些旧的缓存行数据就会被覆盖如果不能充分利用缓存的数据就会造成效率低下
以 ji 执行为例第一次内循环要读入 [ 0 , 0 ] [0,0] [0,0] 这条数据由于局部性原理读入 [ 0 , 0 ] [0,0] [0,0] 的同时也读入了 [ 0 , 1 ] . . . [ 0 , 13 ] [0,1] ... [0,13] [0,1]...[0,13]如图所示 但很遗憾第二次内循环要的是 [ 1 , 0 ] [1,0] [1,0] 这条数据缓存中没有于是再读入了下图的数据 这显然是一种浪费因为 [ 0 , 1 ] . . . [ 0 , 13 ] [0,1] ... [0,13] [0,1]...[0,13] 包括 [ 1 , 1 ] . . . [ 1 , 13 ] [1,1] ... [1,13] [1,1]...[1,13] 这些数据虽然读入了缓存却没有及时用上而缓存的大小是有限的等执行到第九次内循环时 缓存的第一行数据已经被新的数据 [ 8 , 0 ] . . . [ 8 , 13 ] [8,0] ... [8,13] [8,0]...[8,13] 覆盖掉了以后如果再想读比如 [ 0 , 1 ] [0,1] [0,1]又得到内存去读了
同理可以分析 ij 函数则能充分利用局部性原理加载到的缓存数据
举一反三 I/O 读写时同样可以体现局部性原理 数组可以充分利用局部性原理那么链表呢 答链表不行因为链表的元素并非相邻存储
越界检查
java 中对数组元素的读写都有越界检查类似于下面的代码
bool is_within_bounds(int index) const
{ return 0 index index length();
}代码位置openjdk\src\hotspot\share\oops\arrayOop.hpp
只不过此检查代码不需要由程序员自己来调用JVM 会帮我们调用
链表
概述
定义
在计算机科学中链表是数据元素的线性集合其每个元素都指向下一个元素元素存储上并不连续 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. 可以分类为 单向链表每个元素只知道其下一个元素是谁 双向链表每个元素知道其上一个元素和下一个元素 循环链表通常的链表尾节点 tail 指向的都是 null而循环链表的 tail 指向的是头节点 head
链表内还有一种特殊的节点称为哨兵Sentinel节点也叫做哑元 Dummy节点它不存储数据通常用作头尾用来简化边界判断如下图所示 随机访问性能
根据 index 查找时间复杂度 O ( n ) O(n) O(n)
插入或删除性能
起始位置 O ( 1 ) O(1) O(1)结束位置如果已知 tail 尾节点是 O ( 1 ) O(1) O(1)不知道 tail 尾节点是 O ( n ) O(n) O(n)中间位置根据 index 查找时间 O ( 1 ) O(1) O(1)
单向链表
根据单向链表的定义首先定义一个存储 value 和 next 指针的类 Node和一个描述头部节点的引用
public class SinglyLinkedList {private Node head; // 头部节点private static class Node { // 节点类int value;Node next;public Node(int value, Node next) {this.value value;this.next next;}}
}Node 定义为内部类是为了对外隐藏实现细节没必要让类的使用者关心 Node 结构定义为 static 内部类是因为 Node 不需要与 SinglyLinkedList 实例相关多个 SinglyLinkedList实例能共用 Node 类定义
头部添加
public class SinglyLinkedList {// ...public void addFirst(int value) {this.head new Node(value, this.head);}
}如果 this.head null新增节点指向 null并作为新的 this.head如果 this.head ! null新增节点指向原来的 this.head并作为新的 this.head 注意赋值操作执行顺序是从右到左
while 遍历
public class SinglyLinkedList {// ...public void loop() {Node curr this.head;while (curr ! null) {// 做一些事curr curr.next;}}
}for 遍历
public class SinglyLinkedList {// ...public void loop() {for (Node curr this.head; curr ! null; curr curr.next) {// 做一些事}}
}以上两种遍历都可以把要做的事以 Consumer 函数的方式传递进来 Consumer 的规则是一个参数无返回值因此像 System.out::println 方法等都是 Consumer调用 Consumer 时将当前节点 curr.value 作为参数传递给它
迭代器遍历
public class SinglyLinkedList implements IterableInteger {// ...private class NodeIterator implements IteratorInteger {Node curr head;public boolean hasNext() {return curr ! null;}public Integer next() {int value curr.value;curr curr.next;return value;}}public IteratorInteger iterator() {return new NodeIterator();}
}hasNext 用来判断是否还有必要调用 nextnext 做两件事 返回当前节点的 value指向下一个节点 NodeIterator 要定义为非 static 内部类是因为它与 SinglyLinkedList 实例相关是对某个 SinglyLinkedList 实例的迭代
递归遍历
public class SinglyLinkedList implements IterableInteger {// ...public void loop() {recursion(this.head);}private void recursion(Node curr) {if (curr null) {return;}// 前面做些事recursion(curr.next);// 后面做些事}
}尾部添加
public class SinglyLinkedList {// ...private Node findLast() {if (this.head null) {return null;}Node curr;for (curr this.head; curr.next ! null; ) {curr curr.next;}return curr;}public void addLast(int value) {Node last findLast();if (last null) {addFirst(value);return;}last.next new Node(value, null);}
}注意找最后一个节点终止条件是 curr.next null分成两个方法是为了代码清晰而且 findLast() 之后还能复用
尾部添加多个
public class SinglyLinkedList {// ...public void addLast(int first, int... rest) {Node sublist new Node(first, null);Node curr sublist;for (int value : rest) {curr.next new Node(value, null);curr curr.next;}Node last findLast();if (last null) {this.head sublist;return;}last.next sublist;}
}先串成一串 sublist再作为一个整体添加
根据索引获取
public class SinglyLinkedList {// ...private Node findNode(int index) {int i 0;for (Node curr this.head; curr ! null; curr curr.next, i) {if (index i) {return curr;}}return null;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format(index [%d] 不合法%n, index));}public int get(int index) {Node node findNode(index);if (node ! null) {return node.value;}throw illegalIndex(index);}
}同样分方法可以实现复用
插入
public class SinglyLinkedList {// ...public void insert(int index, int value) {if (index 0) {addFirst(value);return;}Node prev findNode(index - 1); // 找到上一个节点if (prev null) { // 找不到throw illegalIndex(index);}prev.next new Node(value, prev.next);}
}插入包括下面的删除都必须找到上一个节点
删除
public class SinglyLinkedList {// ...public void remove(int index) {if (index 0) {if (this.head ! null) {this.head this.head.next;return;} else {throw illegalIndex(index);}}Node prev findNode(index - 1);Node curr;if (prev ! null (curr prev.next) ! null) {prev.next curr.next;} else {throw illegalIndex(index);}}
}第一个 if 块对应着 removeFirst 情况最后一个 if 块对应着至少得两个节点的情况 不仅仅判断上一个节点非空还要保证当前节点非空
单向链表带哨兵
观察之前单向链表的实现发现每个方法内几乎都有判断head是否为null这样的代码能不能简化呢
用一个不参与数据存储的特殊 Node 作为哨兵它一般被称为哨兵或哑元拥有哨兵节点的链表称为带头链表
public class SinglyLinkedListSentinel {// ...private Node head new Node(Integer.MIN_VALUE, null);
}具体存什么值无所谓因为不会用到它的值
加入哨兵节点后代码会变得比较简单先看几个工具方法
public class SinglyLinkedListSentinel {// ...// 根据索引获取节点private Node findNode(int index) {int i -1;for (Node curr this.head; curr ! null; curr curr.next, i) {if (i index) {return curr;}}return null;}// 获取最后一个节点private Node findLast() {Node curr;for (curr this.head; curr.next ! null; ) {curr curr.next;}return curr;}
}findNode 与之前类似只是 i 初始值设置为 -1 对应哨兵实际传入的 index 也是 [ − 1 , ∞ ) [-1, \infty) [−1,∞)findLast 绝不会返回 null 了就算没有其它节点也会返回哨兵作为最后一个节点
这样代码简化为
public class SinglyLinkedListSentinel {// ...public void addLast(int value) {Node last findLast();/*改动前if (last null) {this.head new Node(value, null);return;}*/last.next new Node(value, null);}public void insert(int index, int value) {/*改动前if (index 0) {this.head new Node(value, this.head);return;}*/// index 传入 0 时返回的是哨兵Node prev findNode(index - 1);if (prev ! null) {prev.next new Node(value, prev.next);} else {throw illegalIndex(index);}}public void remove(int index) {/*改动前if (index 0) {if (this.head ! null) {this.head this.head.next;return;} else {throw illegalIndex(index);}}*/// index 传入 0 时返回的是哨兵Node prev findNode(index - 1);Node curr;if (prev ! null (curr prev.next) ! null) {prev.next curr.next;} else {throw illegalIndex(index);}}public void addFirst(int value) {/*改动前this.head new Node(value, this.head);*/this.head.next new Node(value, this.head.next);// 也可以视为 insert 的特例, 即 insert(0, value);}
}对于删除前面说了【最后一个 if 块对应着至少得两个节点的情况】现在有了哨兵就凑足了两个节点
双向链表带哨兵
public class DoublyLinkedListSentinel implements IterableInteger {private final Node head;private final Node tail;public DoublyLinkedListSentinel() {head new Node(null, 666, null);tail new Node(null, 888, null);head.next tail;tail.prev head;}private Node findNode(int index) {int i -1;for (Node p head; p ! tail; p p.next, i) {if (i index) {return p;}}return null;}public void addFirst(int value) {insert(0, value);}public void removeFirst() {remove(0);}public void addLast(int value) {Node prev tail.prev;Node added new Node(prev, value, tail);prev.next added;tail.prev added;}public void removeLast() {Node removed tail.prev;if (removed head) {throw illegalIndex(0);}Node prev removed.prev;prev.next tail;tail.prev prev;}public void insert(int index, int value) {Node prev findNode(index - 1);if (prev null) {throw illegalIndex(index);}Node next prev.next;Node inserted new Node(prev, value, next);prev.next inserted;next.prev inserted;}public void remove(int index) {Node prev findNode(index - 1);if (prev null) {throw illegalIndex(index);}Node removed prev.next;if (removed tail) {throw illegalIndex(index);}Node next removed.next;prev.next next;next.prev prev;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format(index [%d] 不合法%n, index));}Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p head.next;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}static class Node {Node prev;int value;Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}
}环形链表带哨兵
双向环形链表带哨兵这时哨兵既作为头也作为尾 参考实现
public class DoublyLinkedListSentinel implements IterableInteger {Overridepublic IteratorInteger iterator() {return new Iterator() {Node p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic Integer next() {int value p.value;p p.next;return value;}};}static class Node {Node prev;int value;Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}private final Node sentinel new Node(null, -1, null); // 哨兵public DoublyLinkedListSentinel() {sentinel.next sentinel;sentinel.prev sentinel;}/*** 添加到第一个* param value 待添加值*/public void addFirst(int value) {Node next sentinel.next;Node prev sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 添加到最后一个* param value 待添加值*/public void addLast(int value) {Node prev sentinel.prev;Node next sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 删除第一个*/public void removeFirst() {Node removed sentinel.next;if (removed sentinel) {throw new IllegalArgumentException(非法);}Node a sentinel;Node b removed.next;a.next b;b.prev a;}/*** 删除最后一个*/public void removeLast() {Node removed sentinel.prev;if (removed sentinel) {throw new IllegalArgumentException(非法);}Node a removed.prev;Node b sentinel;a.next b;b.prev a;}/*** 根据值删除节点* p假定 value 在链表中作为 key, 有唯一性/p* param value 待删除值*/public void removeByValue(int value) {Node removed findNodeByValue(value);if (removed ! null) {Node prev removed.prev;Node next removed.next;prev.next next;next.prev prev;}}private Node findNodeByValue(int value) {Node p sentinel.next;while (p ! sentinel) {if (p.value value) {return p;}p p.next;}return null;}}队列
概述
计算机科学中queue 是以顺序的方式维护的一组数据集合在一端添加数据从另一端移除数据。习惯来说添加的一端称为尾移除的一端称为头就如同生活中的排队买商品 In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence 先定义一个简化的队列接口
public interface QueueE {/*** 向队列尾插入值* param value 待插入值* return 插入成功返回 true, 插入失败返回 false*/boolean offer(E value);/*** 从对列头获取值, 并移除* return 如果队列非空返回对头值, 否则返回 null*/E poll();/*** 从对列头获取值, 不移除* return 如果队列非空返回对头值, 否则返回 null*/E peek();/*** 检查队列是否为空* return 空返回 true, 否则返回 false*/boolean isEmpty();/*** 检查队列是否已满* return 满返回 true, 否则返回 false*/boolean isFull();
}链表实现
下面以单向环形带哨兵链表方式来实现队列 代码
public class LinkedListQueueEimplements QueueE, IterableE {private static class NodeE {E value;NodeE next;public Node(E value, NodeE next) {this.value value;this.next next;}}private NodeE head new Node(null, null);private NodeE tail head;private int size 0;private int capacity Integer.MAX_VALUE;{tail.next head;}public LinkedListQueue() {}public LinkedListQueue(int capacity) {this.capacity capacity;}Overridepublic boolean offer(E value) {if (isFull()) {return false;}NodeE added new Node(value, head);tail.next added;tail added;size;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}NodeE first head.next;head.next first.next;if (first tail) {tail head;}size--;return first.value;}Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}Overridepublic boolean isEmpty() {return head tail;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p head.next;Overridepublic boolean hasNext() {return p ! head;}Overridepublic E next() {E value p.value;p p.next;return value;}};}
}环形数组实现
好处
对比普通数组起点和终点更为自由不用考虑数据移动“环”意味着不会存在【越界】问题数组性能更佳环形数组比较适合实现有界队列、RingBuffer 等
、
下标计算
例如数组长度是 5当前位置是 3 向前走 2 步此时下标为 ( 3 2 ) % 5 0 (3 2)\%5 0 (32)%50 ( c u r s t e p ) % l e n g t h (cur step) \% length (curstep)%length
cur 当前指针位置step 前进步数length 数组长度 注意 如果 step 1也就是一次走一步可以在 length 时重置为 0 即可 判断空 判断满 满之后的策略可以根据业务需求决定
例如我们要实现的环形队列满之后就拒绝入队
代码
public class ArrayQueueE implements QueueE, IterableE{private int head 0;private int tail 0;private final E[] array;private final int length;SuppressWarnings(all)public ArrayQueue(int capacity) {length capacity 1;array (E[]) new Object[length];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail] value;tail (tail 1) % length;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E value array[head];head (head 1) % length;return value;}Overridepublic E peek() {if (isEmpty()) {return null;}return array[head];}Overridepublic boolean isEmpty() {return tail head;}Overridepublic boolean isFull() {return (tail 1) % length head;}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E value array[p];p (p 1) % array.length;return value;}};}
}判断空、满方法2
引入 size
public class ArrayQueue2E implements QueueE, IterableE {private int head 0;private int tail 0;private final E[] array;private final int capacity;private int size 0;SuppressWarnings(all)public ArrayQueue2(int capacity) {this.capacity capacity;array (E[]) new Object[capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail] value;tail (tail 1) % capacity;size;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E value array[head];head (head 1) % capacity;size--;return value;}Overridepublic E peek() {if (isEmpty()) {return null;}return array[head];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E value array[p];p (p 1) % capacity;return value;}};}
}判断空、满方法3 head 和 tail 不断递增用到索引时再用它们进行计算两个问题 如何保证 head 和 tail 自增超过正整数最大值的正确性 如何让取模运算性能更高 答案让 capacity 为 2 的幂
public class ArrayQueue3E implements QueueE, IterableE {private int head 0;private int tail 0;private final E[] array;private final int capacity;SuppressWarnings(all)public ArrayQueue3(int capacity) {if ((capacity capacity - 1) ! 0) {throw new IllegalArgumentException(capacity 必须为 2 的幂);}this.capacity capacity;array (E[]) new Object[this.capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail capacity - 1] value;tail;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E value array[head capacity - 1];head;return value;}Overridepublic E peek() {if (isEmpty()) {return null;}return array[head capacity - 1];}Overridepublic boolean isEmpty() {return tail - head 0;}Overridepublic boolean isFull() {return tail - head capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E value array[p capacity - 1];p;return value;}};}
}栈
概述
计算机科学中stack 是一种线性的数据结构只能在其一端添加数据和移除数据。习惯来说这一端称之为栈顶另一端不能操作数据的称之为栈底就如同生活中的一摞书
先提供一个栈接口
public interface StackE {/*** 向栈顶压入元素* param value 待压入值* return 压入成功返回 true, 否则返回 false*/boolean push(E value);/*** 从栈顶弹出元素* return 栈非空返回栈顶元素, 栈为空返回 null*/E pop();/*** 返回栈顶元素, 不弹出* return 栈非空返回栈顶元素, 栈为空返回 null*/E peek();/*** 判断栈是否为空* return 空返回 true, 否则返回 false*/boolean isEmpty();/*** 判断栈是否已满* return 满返回 true, 否则返回 false*/boolean isFull();
}链表实现
public class LinkedListStackE implements StackE, IterableE {private final int capacity;private int size;private final NodeE head new Node(null, null);public LinkedListStack(int capacity) {this.capacity capacity;}Overridepublic boolean push(E value) {if (isFull()) {return false;}head.next new Node(value, head.next);size;return true;}Overridepublic E pop() {if (isEmpty()) {return null;}NodeE first head.next;head.next first.next;size--;return first.value;}Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}Overridepublic boolean isEmpty() {return head.next null;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p head.next;Overridepublic boolean hasNext() {return p ! null;}Overridepublic E next() {E value p.value;p p.next;return value;}};}static class NodeE {E value;NodeE next;public Node(E value, NodeE next) {this.value value;this.next next;}}
}数组实现
public class ArrayStackE implements StackE, IterableE{private final E[] array;private int top 0;SuppressWarnings(all)public ArrayStack(int capacity) {this.array (E[]) new Object[capacity];}Overridepublic boolean push(E value) {if (isFull()) {return false;}array[top] value;return true;}Overridepublic E pop() {if (isEmpty()) {return null;}return array[--top];}Overridepublic E peek() {if (isEmpty()) {return null;}return array[top-1];}Overridepublic boolean isEmpty() {return top 0;}Overridepublic boolean isFull() {return top array.length;}Overridepublic IteratorE iterator() {return new IteratorE() {int p top;Overridepublic boolean hasNext() {return p 0;}Overridepublic E next() {return array[--p];}};}
}应用
模拟如下方法调用
public static void main(String[] args) {System.out.println(main1);System.out.println(main2);method1();method2();System.out.println(main3);
}public static void method1() {System.out.println(method1);method3();
}public static void method2() {System.out.println(method2);
}public static void method3() {System.out.println(method3);
}模拟代码
public class CPU {static class Frame {int exit;public Frame(int exit) {this.exit exit;}}static int pc 1; // 模拟程序计数器 Program counterstatic ArrayStackFrame stack new ArrayStack(100); // 模拟方法调用栈public static void main(String[] args) {stack.push(new Frame(-1));while (!stack.isEmpty()) {switch (pc) {case 1 - {System.out.println(main1);pc;}case 2 - {System.out.println(main2);pc;}case 3 - {stack.push(new Frame(pc 1));pc 100;}case 4 - {stack.push(new Frame(pc 1));pc 200;}case 5 - {System.out.println(main3);pc stack.pop().exit;}case 100 - {System.out.println(method1);stack.push(new Frame(pc 1));pc 300;}case 101 - {pc stack.pop().exit;}case 200 - {System.out.println(method2);pc stack.pop().exit;}case 300 - {System.out.println(method3);pc stack.pop().exit;}}}}
}双端队列
概述
双端队列、队列、栈对比
定义特点队列一端删除头另一端添加尾First In First Out栈一端删除和添加顶Last In First Out双端队列两端都可以删除、添加优先级队列优先级高者先出队延时队列根据延时时间确定优先级并发非阻塞队列队列空或满时不阻塞并发阻塞队列队列空时删除阻塞、队列满时添加阻塞 注1 Java 中 LinkedList 即为典型双端队列实现不过它同时实现了 Queue 接口也提供了栈的 push pop 等方法 注2 不同语言操作双端队列的方法命名有所不同参见下表 操作JavaJavaScriptCleetCode 641尾部插入offerLastpushpush_backinsertLast头部插入offerFirstunshiftpush_frontinsertFront尾部移除pollLastpoppop_backdeleteLast头部移除pollFirstshiftpop_frontdeleteFront尾部获取peekLastat(-1)backgetRear头部获取peekFirstat(0)frontgetFront 吐槽一下 leetCode 命名比较 low 常见的单词还有 enqueue 入队、dequeue 出队 接口定义
public interface DequeE {boolean offerFirst(E e);boolean offerLast(E e);E pollFirst();E pollLast();E peekFirst();E peekLast();boolean isEmpty();boolean isFull();
}链表实现
/*** 基于环形链表的双端队列* param E 元素类型*/
public class LinkedListDequeE implements DequeE, IterableE {Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}size;NodeE a sentinel;NodeE b sentinel.next;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}size;NodeE a sentinel.prev;NodeE b sentinel;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}NodeE a sentinel;NodeE polled sentinel.next;NodeE b polled.next;a.next b;b.prev a;size--;return polled.value;}Overridepublic E pollLast() {if (isEmpty()) {return null;}NodeE polled sentinel.prev;NodeE a polled.prev;NodeE b sentinel;a.next b;b.prev a;size--;return polled.value;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return sentinel.next.value;}Overridepublic E peekLast() {if (isEmpty()) {return null;}return sentinel.prev.value;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic E next() {E value p.value;p p.next;return value;}};}static class NodeE {NodeE prev;E value;NodeE next;public Node(NodeE prev, E value, NodeE next) {this.prev prev;this.value value;this.next next;}}NodeE sentinel new Node(null, null, null);int capacity;int size;public LinkedListDeque(int capacity) {sentinel.next sentinel;sentinel.prev sentinel;this.capacity capacity;}
}数组实现
/*** 基于循环数组实现, 特点* ul* litail 停下来的位置不存储, 会浪费一个位置/li* /ul* param E*/
public class ArrayDeque1E implements DequeE, IterableE {/*ht0 1 2 3b a*/Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}head dec(head, array.length);array[head] e;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}array[tail] e;tail inc(tail, array.length);return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}E e array[head];array[head] null;head inc(head, array.length);return e;}Overridepublic E pollLast() {if (isEmpty()) {return null;}tail dec(tail, array.length);E e array[tail];array[tail] null;return e;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return array[head];}Overridepublic E peekLast() {if (isEmpty()) {return null;}return array[dec(tail, array.length)];}Overridepublic boolean isEmpty() {return head tail;}Overridepublic boolean isFull() {if (tail head) {return tail - head array.length - 1;} else if (tail head) {return head - tail 1;} else {return false;}}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E e array[p];p inc(p, array.length);return e;}};}E[] array;int head;int tail;SuppressWarnings(unchecked)public ArrayDeque1(int capacity) {array (E[]) new Object[capacity 1];}static int inc(int i, int length) {if (i 1 length) {return 0;}return i 1;}static int dec(int i, int length) {if (i - 1 0) {return length - 1;}return i - 1;}
}数组实现中如果存储的是基本类型那么无需考虑内存释放例如 但如果存储的是引用类型应当设置该位置的引用为 null以便内存及时释放 优先级队列
无序数组实现
要点
入队保持顺序出队前找到优先级最高的出队相当于一次选择排序
public class PriorityQueue1E extends Priority implements QueueE {Priority[] array;int size;public PriorityQueue1(int capacity) {array new Priority[capacity];}Override // O(1)public boolean offer(E e) {if (isFull()) {return false;}array[size] e;return true;}// 返回优先级最高的索引值private int selectMax() {int max 0;for (int i 1; i size; i) {if (array[i].priority() array[max].priority()) {max i;}}return max;}Override // O(n)public E poll() {if (isEmpty()) {return null;}int max selectMax();E e (E) array[max];remove(max);return e;}private void remove(int index) {if (index size - 1) {System.arraycopy(array, index 1,array, index, size - 1 - index);}array[--size] null; // help GC}Overridepublic E peek() {if (isEmpty()) {return null;}int max selectMax();return (E) array[max];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size array.length;}
}有序数组实现
要点
入队后排好序优先级最高的排列在尾部出队只需删除尾部元素即可
public class PriorityQueue2E extends Priority implements QueueE {Priority[] array;int size;public PriorityQueue2(int capacity) {array new Priority[capacity];}// O(n)Overridepublic boolean offer(E e) {if (isFull()) {return false;}insert(e);size;return true;}// 一轮插入排序private void insert(E e) {int i size - 1;while (i 0 array[i].priority() e.priority()) {array[i 1] array[i];i--;}array[i 1] e;}// O(1)Overridepublic E poll() {if (isEmpty()) {return null;}E e (E) array[size - 1];array[--size] null; // help GCreturn e;}Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[size - 1];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size array.length;}
}堆实现
计算机科学中堆是一种基于树的数据结构通常用完全二叉树实现。堆的特性如下
在大顶堆中任意节点 C 与它的父节点 P 符合 P . v a l u e ≥ C . v a l u e P.value \geq C.value P.value≥C.value而小顶堆中任意节点 C 与它的父节点 P 符合 P . v a l u e ≤ C . v a l u e P.value \leq C.value P.value≤C.value最顶层的节点没有父亲称之为 root 根节点 In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the “top” of the heap (with no parents) is called the root node 例1 - 满二叉树Full Binary Tree特点每一层都是填满的 例2 - 完全二叉树Complete Binary Tree特点最后一层可能未填满靠左对齐 例3 - 大顶堆 例4 - 小顶堆 完全二叉树可以使用数组来表示 特征
如果从索引 0 开始存储节点数据 节点 i i i 的父节点为 f l o o r ( ( i − 1 ) / 2 ) floor((i-1)/2) floor((i−1)/2)当 i 0 i0 i0 时节点 i i i 的左子节点为 2 i 1 2i1 2i1右子节点为 2 i 2 2i2 2i2当然它们得 s i z e size size 如果从索引 1 开始存储节点数据 节点 i i i 的父节点为 f l o o r ( i / 2 ) floor(i/2) floor(i/2)当 i 1 i 1 i1 时节点 i i i 的左子节点为 2 i 2i 2i右子节点为 2 i 1 2i1 2i1同样得 s i z e size size
代码
public class PriorityQueue4E extends Priority implements QueueE {Priority[] array;int size;public PriorityQueue4(int capacity) {array new Priority[capacity];}Overridepublic boolean offer(E offered) {if (isFull()) {return false;}int child size;int parent (child - 1) / 2;while (child 0 offered.priority() array[parent].priority()) {array[child] array[parent];child parent;parent (child - 1) / 2;}array[child] offered;return true;}private void swap(int i, int j) {Priority t array[i];array[i] array[j];array[j] t;}Overridepublic E poll() {if (isEmpty()) {return null;}swap(0, size - 1);size--;Priority e array[size];array[size] null;shiftDown(0); return (E) e;}void shiftDown(int parent) {int left 2 * parent 1;int right left 1;int max parent;if (left size array[left].priority() array[max].priority()) {max left;}if (right size array[right].priority() array[max].priority()) {max right;}if (max ! parent) {swap(max, parent);shiftDown(max);}}Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[0];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size array.length;}
}阻塞队列
之前的队列在很多场景下都不能很好地工作例如
大部分场景要求分离向队列放入生产者、从队列拿出消费者两个角色、它们得由不同的线程来担当而之前的实现根本没有考虑线程安全问题队列为空那么在之前的实现里会返回 null如果就是硬要拿到一个元素呢只能不断循环尝试队列为满那么再之前的实现里会返回 false如果就是硬要塞入一个元素呢只能不断循环尝试
因此我们需要解决的问题有
用锁保证线程安全用条件变量让等待非空线程与等待不满线程进入等待状态而不是不断循环尝试让 CPU 空转
有同学对线程安全还没有足够的认识下面举一个反例两个线程都要执行入队操作几乎在同一时刻
public class TestThreadUnsafe {private final String[] array new String[10];private int tail 0;public void offer(String e) {array[tail] e;tail;}Overridepublic String toString() {return Arrays.toString(array);}public static void main(String[] args) {TestThreadUnsafe queue new TestThreadUnsafe();new Thread(()- queue.offer(e1), t1).start();new Thread(()- queue.offer(e2), t2).start();}
}执行的时间序列如下假设初始状态 tail 0在执行过程中由于 CPU 在两个线程之间切换造成了指令交错
线程1线程2说明array[tail]e1线程1 向 tail 位置加入 e1 这个元素但还没来得及执行 tailarray[tail]e2线程2 向 tail 位置加入 e2 这个元素覆盖掉了 e1tailtail 自增为1tailtail 自增为2最后状态 tail 为 2数组为 [e2, null, null …]
糟糕的是由于指令交错的顺序不同得到的结果不止以上一种宏观上造成混乱的效果
单锁实现
Java 中要防止代码段交错执行需要使用锁有两种选择
synchronized 代码块属于关键字级别提供锁保护功能少ReentrantLock 类功能丰富
以 ReentrantLock 为例
ReentrantLock lock new ReentrantLock();public void offer(String e) {lock.lockInterruptibly();try {array[tail] e;tail;} finally {lock.unlock();}
}只要两个线程执行上段代码时锁对象是同一个就能保证 try 块内的代码的执行不会出现指令交错现象即执行顺序只可能是下面两种情况之一
线程1线程2说明lock.lockInterruptibly()t1对锁对象上锁array[tail]e1lock.lockInterruptibly()即使 CPU 切换到线程2但由于t1已经对该对象上锁因此线程2卡在这儿进不去tail切换回线程1 执行后续代码lock.unlock()线程1 解锁array[tail]e2线程2 此时才能获得锁执行它的代码tail
另一种情况是线程2 先获得锁线程1 被挡在外面要明白保护的本质本例中是保护的是 tail 位置读写的安全
事情还没有完上面的例子是队列还没有放满的情况考虑下面的代码这回锁同时保护了 tail 和 size 的读写安全
ReentrantLock lock new ReentrantLock();
int size 0;public void offer(String e) {lock.lockInterruptibly();try {if(isFull()) {// 满了怎么办?}array[tail] e;tail;size;} finally {lock.unlock();}
}private boolean isFull() {return size array.length;
}之前是返回 false 表示添加失败前面分析过想达到这么一种效果
在队列满时不是立刻返回而是当前线程进入等待什么时候队列不满了再唤醒这个等待的线程从上次的代码处继续向下运行
ReentrantLock 可以配合条件变量来实现代码进化为
ReentrantLock lock new ReentrantLock();
Condition tailWaits lock.newCondition(); // 条件变量
int size 0;public void offer(String e) {lock.lockInterruptibly();try {while (isFull()) {tailWaits.await(); // 当队列满时, 当前线程进入 tailWaits 等待}array[tail] e;tail;size;} finally {lock.unlock();}
}private boolean isFull() {return size array.length;
}条件变量底层也是个队列用来存储这些需要等待的线程当队列满了就会将 offer 线程加入条件队列并暂时释放锁将来我们的队列如果不满了由 poll 线程那边得知可以调用 tailWaits.signal() 来唤醒 tailWaits 中首个等待的线程被唤醒的线程会再次抢到锁从上次 await 处继续向下运行
思考为何要用 while 而不是 if设队列容量是 3
操作前offer(4)offer(5)poll()操作后[1 2 3]队列满进入tailWaits 等待[1 2 3][1 2 3]取走 1队列不满唤醒线程[2 3][2 3]抢先获得锁发现不满放入 5[2 3 5][2 3 5]从上次等待处直接向下执行[2 3 5 ?]
关键点
从 tailWaits 中唤醒的线程会与新来的 offer 的线程争抢锁谁能抢到是不一定的如果后者先抢到就会导致条件又发生变化这种情况称之为虚假唤醒唤醒后应该重新检查条件看是不是得重新进入等待
最后的实现代码
/*** 单锁实现* param E 元素类型*/
public class BlockingQueue1E implements BlockingQueueE {private final E[] array;private int head 0;private int tail 0;private int size 0; // 元素个数SuppressWarnings(all)public BlockingQueue1(int capacity) {array (E[]) new Object[capacity];}ReentrantLock lock new ReentrantLock();Condition tailWaits lock.newCondition();Condition headWaits lock.newCondition();Overridepublic void offer(E e) throws InterruptedException {lock.lockInterruptibly();try {while (isFull()) {tailWaits.await();}array[tail] e;if (tail array.length) {tail 0;}size;headWaits.signal();} finally {lock.unlock();}}Overridepublic void offer(E e, long timeout) throws InterruptedException {lock.lockInterruptibly();try {long t TimeUnit.MILLISECONDS.toNanos(timeout);while (isFull()) {if (t 0) {return;}t tailWaits.awaitNanos(t);}array[tail] e;if (tail array.length) {tail 0;}size;headWaits.signal();} finally {lock.unlock();}}Overridepublic E poll() throws InterruptedException {lock.lockInterruptibly();try {while (isEmpty()) {headWaits.await();}E e array[head];array[head] null; // help GCif (head array.length) {head 0;}size--;tailWaits.signal();return e;} finally {lock.unlock();}}private boolean isEmpty() {return size 0;}private boolean isFull() {return size array.length;}
}public void offer(E e, long timeout) throws InterruptedException 是带超时的版本可以只等待一段时间而不是永久等下去类似的 poll 也可以做带超时的版本这个留给大家了 注意 JDK 中 BlockingQueue 接口的方法命名与我的示例有些差异 方法 offer(E e) 是非阻塞的实现阻塞实现方法为 put(E e)方法 poll() 是非阻塞的实现阻塞实现方法为 take() 双锁实现
单锁的缺点在于
生产和消费几乎是不冲突的唯一冲突的是生产者和消费者它们有可能同时修改 size冲突的主要是生产者之间多个 offer 线程修改 tail冲突的还有消费者之间多个 poll 线程修改 head
如果希望进一步提高性能可以用两把锁
一把锁保护 tail另一把锁保护 head
ReentrantLock headLock new ReentrantLock(); // 保护 head 的锁
Condition headWaits headLock.newCondition(); // 队列空时需要等待的线程集合ReentrantLock tailLock new ReentrantLock(); // 保护 tail 的锁
Condition tailWaits tailLock.newCondition(); // 队列满时需要等待的线程集合先看看 offer 方法的初步实现
Override
public void offer(E e) throws InterruptedException {tailLock.lockInterruptibly();try {// 队列满等待while (isFull()) {tailWaits.await();}// 不满则入队array[tail] e;if (tail array.length) {tail 0;}// 修改 size 有问题size;} finally {tailLock.unlock();}
}上面代码的缺点是 size 并不受 tailLock 保护tailLock 与 headLock 是两把不同的锁并不能实现互斥的效果。因此size 需要用下面的代码保证原子性
AtomicInteger size new AtomicInteger(0); // 保护 size 的原子变量size.getAndIncrement(); // 自增
size.getAndDecrement(); // 自减代码修改为
Override
public void offer(E e) throws InterruptedException {tailLock.lockInterruptibly();try {// 队列满等待while (isFull()) {tailWaits.await();}// 不满则入队array[tail] e;if (tail array.length) {tail 0;}// 修改 sizesize.getAndIncrement();} finally {tailLock.unlock();}
}对称地可以写出 poll 方法
Override
public E poll() throws InterruptedException {E e;headLock.lockInterruptibly();try {// 队列空等待while (isEmpty()) {headWaits.await();}// 不空则出队e array[head];if (head array.length) {head 0;}// 修改 sizesize.getAndDecrement();} finally {headLock.unlock();}return e;
}下面来看一个难题就是如何通知 headWaits 和 tailWaits 中等待的线程比如 poll 方法拿走一个元素通知 tailWaits我拿走一个不满了噢你们可以放了因此代码改为
Override
public E poll() throws InterruptedException {E e;headLock.lockInterruptibly();try {// 队列空等待while (isEmpty()) {headWaits.await();}// 不空则出队e array[head];if (head array.length) {head 0;}// 修改 sizesize.getAndDecrement();// 通知 tailWaits 不满有问题tailWaits.signal();} finally {headLock.unlock();}return e;
}问题在于要使用这些条件变量的 await() signal() 等方法需要先获得与之关联的锁上面的代码若直接运行会出现以下错误
java.lang.IllegalMonitorStateException那有同学说加上锁不就行了吗于是写出了下面的代码 发现什么问题了两把锁这么嵌套使用非常容易出现死锁如下所示 因此得避免嵌套两段加锁的代码变成了下面平级的样子 性能还可以进一步提升 代码调整后 offer 并没有同时获取 tailLock 和 headLock 两把锁因此两次加锁之间会有空隙这个空隙内可能有其它的 offer 线程添加了更多的元素那么这些线程都要执行 signal()通知 poll 线程队列非空吗 每次调用 signal() 都需要这些 offer 线程先获得 headLock 锁成本较高要想法减少 offer 线程获得 headLock 锁的次数可以加一个条件当 offer 增加前队列为空即从 0 变化到不空才由此 offer 线程来通知 headWaits其它情况不归它管 队列从 0 变化到不空会唤醒一个等待的 poll 线程这个线程被唤醒后肯定能拿到 headLock 锁因此它具备了唤醒 headWaits 上其它 poll 线程的先决条件。如果检查出此时有其它 offer 线程新增了元素不空但不是从0变化而来那么不妨由此 poll 线程来唤醒其它 poll 线程
这个技巧被称之为级联通知cascading notifies类似的原因
在 poll 时队列从满变化到不满才由此 poll 线程来唤醒一个等待的 offer 线程目的也是为了减少 poll 线程对 tailLock 上锁次数剩下等待的 offer 线程由这个 offer 线程间接唤醒
最终的代码为
public class BlockingQueue2E implements BlockingQueueE {private final E[] array;private int head 0;private int tail 0;private final AtomicInteger size new AtomicInteger(0);ReentrantLock headLock new ReentrantLock();Condition headWaits headLock.newCondition();ReentrantLock tailLock new ReentrantLock();Condition tailWaits tailLock.newCondition();public BlockingQueue2(int capacity) {this.array (E[]) new Object[capacity];}Overridepublic void offer(E e) throws InterruptedException {int c;tailLock.lockInterruptibly();try {while (isFull()) {tailWaits.await();}array[tail] e;if (tail array.length) {tail 0;} c size.getAndIncrement();// a. 队列不满, 但不是从满-不满, 由此offer线程唤醒其它offer线程if (c 1 array.length) {tailWaits.signal();}} finally {tailLock.unlock();}// b. 从0-不空, 由此offer线程唤醒等待的poll线程if (c 0) {headLock.lock();try {headWaits.signal();} finally {headLock.unlock();}}}Overridepublic E poll() throws InterruptedException {E e;int c;headLock.lockInterruptibly();try {while (isEmpty()) {headWaits.await(); }e array[head]; if (head array.length) {head 0;}c size.getAndDecrement();// b. 队列不空, 但不是从0变化到不空由此poll线程通知其它poll线程if (c 1) {headWaits.signal();}} finally {headLock.unlock();}// a. 从满-不满, 由此poll线程唤醒等待的offer线程if (c array.length) {tailLock.lock();try {tailWaits.signal();} finally {tailLock.unlock();}}return e;}private boolean isEmpty() {return size.get() 0;}private boolean isFull() {return size.get() array.length;}}双锁实现的非常精巧据说作者 Doug Lea 花了一年的时间才完善了此段代码
堆
以大顶堆为例相对于之前的优先级队列增加了堆化等方法
public class MaxHeap {int[] array;int size;public MaxHeap(int capacity) {this.array new int[capacity];}/*** 获取堆顶元素** return 堆顶元素*/public int peek() {return array[0];}/*** 删除堆顶元素** return 堆顶元素*/public int poll() {int top array[0];swap(0, size - 1);size--;down(0);return top;}/*** 删除指定索引处元素** param index 索引* return 被删除元素*/public int poll(int index) {int deleted array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素* param replaced 新元素*/public void replace(int replaced) {array[0] replaced;down(0);}/*** 堆的尾部添加元素** param offered 新元素* return 是否添加成功*/public boolean offer(int offered) {if (size array.length) {return false;}up(offered);size;return true;}// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child size;while (child 0) {int parent (child - 1) / 2;if (offered array[parent]) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}public MaxHeap(int[] array) {this.array array;this.size array.length;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 size / 2 - 1for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left parent * 2 1;int right left 1;int max parent;if (left size array[left] array[max]) {max left;}if (right size array[right] array[max]) {max right;}if (max ! parent) { // 找到了更大的孩子swap(max, parent);down(max);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}public static void main(String[] args) {int[] array {1, 2, 3, 4, 5, 6, 7};MaxHeap maxHeap new MaxHeap(array);System.out.println(Arrays.toString(maxHeap.array));}
}建堆
Floyd 建堆算法作者也是之前龟兔赛跑判环作者 找到最后一个非叶子节点从后向前对每个节点执行下潜
一些规律
一棵满二叉树节点个数为 2 h − 1 2^h-1 2h−1如下例中高度 h 3 h3 h3 节点数是 2 3 − 1 7 2^3-17 23−17非叶子节点范围为 [ 0 , s i z e / 2 − 1 ] [0, size/2-1] [0,size/2−1]
算法时间复杂度分析 下面看交换次数的推导设节点高度为 3
本层节点数高度下潜最多交换次数高度-14567 这层41023这层2211这层132
每一层的交换次数为 节点个数 ∗ 此节点交换次数 节点个数*此节点交换次数 节点个数∗此节点交换次数总的交换次数为 4 ∗ 0 2 ∗ 1 1 ∗ 2 8 2 ∗ 0 8 4 ∗ 1 8 8 ∗ 2 8 2 1 ∗ 0 8 2 2 ∗ 1 8 2 3 ∗ 2 \begin{aligned} 4 * 0 2 * 1 1 * 2 \\ \frac{8}{2}*0 \frac{8}{4}*1 \frac{8}{8}*2 \\ \frac{8}{2^1}*0 \frac{8}{2^2}*1 \frac{8}{2^3}*2\\ \end{aligned} 4∗02∗11∗228∗048∗188∗2218∗0228∗1238∗2
即 ∑ i 1 h ( 2 h 2 i ∗ ( i − 1 ) ) \sum_{i1}^{h}(\frac{2^h}{2^i}*(i-1)) i1∑h(2i2h∗(i−1))
在 https://www.wolframalpha.com/ 输入
Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}]推导出 2 h − h − 1 2^h -h -1 2h−h−1 其中 2 h ≈ n 2^h \approx n 2h≈n h ≈ log 2 n h \approx \log_2{n} h≈log2n因此有时间复杂度 O ( n ) O(n) O(n)
二叉树
二叉树是这么一种树状结构每个节点最多有两个孩子左孩子和右孩子
重要的二叉树结构
完全二叉树complete binary tree是一种二叉树结构除最后一层以外每一层都必须填满填充时要遵从先左后右平衡二叉树balance binary tree是一种二叉树结构其中每个节点的左右子树高度相差不超过 1
存储
存储方式分为两种
定义树节点与左、右孩子引用TreeNode使用数组前面讲堆时用过若以 0 作为树的根索引可以通过如下方式计算 父 floor((子 - 1) / 2)左孩子 父 * 2 1右孩子 父 * 2 2
遍历
遍历也分为两种
广度优先遍历Breadth-first order尽可能先访问距离根最近的节点也称为层序遍历深度优先遍历Depth-first order对于二叉树可以进一步分成三种要深入到叶子节点 pre-order 前序遍历对于每一棵子树先访问该节点然后是左子树最后是右子树in-order 中序遍历对于每一棵子树先访问左子树然后是该节点最后是右子树post-order 后序遍历对于每一棵子树先访问左子树然后是右子树最后是该节点
广度优先 本轮开始时队列本轮访问节点[1]1[2, 3]2[3, 4]3[4, 5, 6]4[5, 6]5[6, 7, 8]6[7, 8]7[8]8[]
初始化将根节点加入队列循环处理队列中每个节点直至队列为空每次循环内处理节点后将它的孩子节点即下一层的节点加入队列 注意 以上用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树 对于数组表现的二叉树则直接遍历数组即可自然为层序遍历的顺序 深度优先 栈暂存已处理前序遍历中序遍历[1]1 ✔️ 左 右1[1, 2]2✔️ 左 右1✔️ 左 右2[1, 2, 4]4✔️ 左✔️ 右✔️2✔️ 左 右1✔️ 左 右44[1, 2]2✔️ 左✔️ 右✔️1✔️ 左 右2[1]1✔️ 左✔️ 右1[1, 3]3✔️ 左 右1✔️ 左✔️ 右3[1, 3, 5]5✔️ 左✔️ 右✔️3✔️ 左 右1✔️ 左✔️ 右55[1, 3]3✔️ 左✔️ 右1✔️ 左✔️ 右3[1, 3, 6]6✔️ 左✔️ 右✔️3✔️ 左✔️ 右1✔️ 左✔️ 右66[1, 3]3✔️ 左✔️ 右✔️1✔️ 左✔️ 右[1]1✔️ 左✔️ 右✔️[]
递归实现
/*** h3前序遍历/h3* param node 节点*/
static void preOrder(TreeNode node) {if (node null) {return;}System.out.print(node.val \t); // 值preOrder(node.left); // 左preOrder(node.right); // 右
}/*** h3中序遍历/h3* param node 节点*/
static void inOrder(TreeNode node) {if (node null) {return;}inOrder(node.left); // 左System.out.print(node.val \t); // 值inOrder(node.right); // 右
}/*** h3后序遍历/h3* param node 节点*/
static void postOrder(TreeNode node) {if (node null) {return;}postOrder(node.left); // 左postOrder(node.right); // 右System.out.print(node.val \t); // 值
}非递归实现
前序遍历
LinkedListStackTreeNode stack new LinkedListStack();
TreeNode curr root;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);System.out.println(curr);curr curr.left;} else {TreeNode pop stack.pop();curr pop.right;}}中序遍历
LinkedListStackTreeNode stack new LinkedListStack();
TreeNode curr root;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);curr curr.left;} else {TreeNode pop stack.pop();System.out.println(pop);curr pop.right;}
}后序遍历
LinkedListStackTreeNode stack new LinkedListStack();
TreeNode curr root;
TreeNode pop null;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);curr curr.left;} else {TreeNode peek stack.peek();if (peek.right null || peek.right pop) {pop stack.pop();System.out.println(pop);} else {curr peek.right;}}
}对于后序遍历向回走时需要处理完右子树才能 pop 出栈。如何知道右子树处理完成呢 如果栈顶元素的 r i g h t ≡ n u l l right \equiv null right≡null 表示没啥可处理的可以出栈 如果栈顶元素的 r i g h t ≠ n u l l right \neq null rightnull 那么使用 lastPop 记录最近出栈的节点即表示从这个节点向回走如果栈顶元素的 r i g h t l a s t P o p rightlastPop rightlastPop 此时应当出栈
对于前、中两种遍历实际以上代码从右子树向回走时并未走完全程stack 提前出栈了后序遍历以上代码是走完全程了
统一写法
下面是一种统一的写法依据后序遍历修改
LinkedListTreeNode stack new LinkedList();TreeNode curr root; // 代表当前节点
TreeNode pop null; // 最近一次弹栈的元素
while (curr ! null || !stack.isEmpty()) {if (curr ! null) {colorPrintln(前: curr.val, 31);stack.push(curr); // 压入栈为了记住回来的路curr curr.left;} else {TreeNode peek stack.peek();// 右子树可以不处理, 对中序来说, 要在右子树处理之前打印if (peek.right null) {colorPrintln(中: peek.val, 36);pop stack.pop();colorPrintln(后: pop.val, 34);}// 右子树处理完成, 对中序来说, 无需打印else if (peek.right pop) {pop stack.pop();colorPrintln(后: pop.val, 34);}// 右子树待处理, 对中序来说, 要在右子树处理之前打印else {colorPrintln(中: peek.val, 36);curr peek.right;}}
}public static void colorPrintln(String origin, int color) {System.out.printf(\033[%dm%s\033[0m%n, color, origin);
}一张图演示三种遍历 红色前序遍历顺序绿色中序遍历顺序蓝色后续遍历顺序
