在Kotlin中，标准库是否支持堆栈、队列、堆、树等数据结构？

Question

在Kotlin中，标准库是否支持堆栈、队列、堆、树等数据结构？

作为一个最熟悉 Python 但在进入 Kotlin 之前没有使用过 Java 的人，我想到了这个问题。

例如，如果想使用 Kotlin 进行竞争性编程，或者不想重新发明轮子来实现通用数据结构，标准库是否支持这些？或者由于 Kotlin 的某些设计原因不支持它们？至少我在文档中找不到这些。那么如果在 JVM 上使用 Kotlin，人们通常会使用 Java 库中的实现吗？

Answer 1

在这种情况下，Kotlin 主要重用了 Java 的 Collection API，因此您可以自由地使用它。Collection API有4个主要接口：

1. 列表- 元素的有序序列。
2. Set - 没有重复项的集合。
3. 队列- 设计用于在处理之前保存元素的集合。您可以利用它的 FIFO 接口。还扩展了Deque接口，支持两端元素的插入和删除。
4. Map - 将键映射到值的对象。

该接口的实现可以满足大部分需求。

比如LinkedList双向链表数据结构的经典实现；它还实现了Deque. 内部使用数组ArrayList实现接口；List由于数组的索引访问效率本质，它的元素访问速度要快得多（访问第一个或最后一个元素的情况除外，因为它们是相同的），但插入确实会花费您在非最后插入或插入时的成本当超出内部数组的容量时，因为它应该重新初始化并重新填充，这对时间和空间来说都是一个打击。Java的内部System#arraycopy速度相对较快。

Stack 和 Queue 都可以用 来实现ArrayDeque，这又是一个数组支持的实现，但在本例中是Deque.

TreeMap内部使用红黑树算法；TreeSet内部使用TreeMap是您需要单个元素而不是关联。

对于基于哈希表的实现，您可以分别HashMap用于关联和HashSet单一元素（与基于树的实现的重用情况相同）。

对于所有其他事情（也是线程安全的 - 专为并发或简单的锁定应用装饰器而设计），您实际上可以搜索这些接口的适当实现 - 标准库足够大。

Answer 2

添加到上面的答案，Java对Heap的实现是PriorityQueue，适当地传递一个比较器，你可以在Kotlin中使用它没有问题。

文档：https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

检查更多：https ://www.geeksforgeeks.org/priority-queue-class-in-java-2/