数据结构面试（一）

Queue

什么是队列

队列是数据结构中??重要的?种类型，它?持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们?活中的排队类似。

队列的种类

• 单队列（单队列就是常?的队列, 每次添加元素时，都是添加到队尾，存在“假溢出”的问题也就是明明有位置却不能添加的情况）
• 循环队列（避免了“假溢出”的问题）

Java 集合框架中的队列 Queue

Java 集合中的 Queue 继承? Collection 接? ，Deque, LinkedList, PriorityQueue,BlockingQueue 等类都实现了它。 Queue ?来存放 等待处理元素 的集合，这种场景?般?于缓冲、
并发访问。 除了继承 Collection 接?的?些?法，Queue 还添加了额外的 添加、删除、查询操作。

推荐?章

Java 集合深?理解（9）：Queue 队列

Set

Set 继承于 Collection 接?，是?个不允许出现重复元素，并且?序的集合，主要 HashSet 和TreeSet 两?实现类。
在判断重复元素的时候，HashSet 集合会调? hashCode()和 equal()?法来实现；TreeSet 集合会调?compareTo?法来实现。

补充：有序集合与?序集合说明

• 有序集合：集合?的元素可以根据 key 或 index 访问 (List、Map)
• ?序集合：集合?的元素只能遍历。（Set）

HashSet 和 TreeSet 底层数据结构

• HashSet 是哈希表结构，主要利? HashMap 的 key 来存储元素，计算插?元素的 hashCode 来获取元素在集合中的位置；
• TreeSet 是红?树结构，每?个元素都是树中的?个节点，插?的元素都会进?排序；

List

什么是List

在 List 中，?户可以精确控制列表中每个元素的插?位置，另外?户可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。 与 Set 不同，List 通常允许重复的元素。 另外 List 是有序集合? Set 是?序集合。

List的常?实现类

ArrayList 是?个数组队列，相当于动态数组。它由数组实现，随机访问效率?，随机插?、随机删除效率低。
LinkedList 是?个双向链表。它也可以被当作堆栈、队列或双端队列进?操作。LinkedList随机访问效率低，但随机插?、随机删除效率?。
Vector 是?量队列，和ArrayList?样，它也是?个动态数组，由数组实现。但是ArrayList是?线程安全的，?Vector是线程安全的。
Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。相关阅读：java数据结构与算法之栈（Stack）设计与实现

ArrayList 和 LinkedList 源码学习

Map

树

结点的层次（level）：从0开始，如上图的层数是2；
兄弟（sibling）：有同一个父节点的，如上E和F是兄弟，但是E和G不是兄弟节点。
数的深度（depth）或高度：最大层次数称为树的深度。如上：深度为2
结点的度（degree）：拥有子树的数目称之为节点的度。如上：A和D的度是3；

二叉树

每个结点的度不超过2；并且每个孩子还有左孩子和有孩子之分。

完全二叉树

完全?叉树：叶节点只能出现在最下层和次下层，并且最下??层的结点都集中在该层最左边的若?位
置的?叉树。

满二叉树

?个?叉树，如果每?个层的结点数都达到最?值，则这个?叉树就是满?叉树。也就是说，如果?个?叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满?叉树。

堆

数据结构之堆的定义

堆是具有以下性质的完全?叉树：每个结点的值都?于或等于其左右孩?结点的值，称为?顶堆；或者每个结点的值都?于或等于其左右孩?结点的值，称为?顶堆。

?叉查找树（BST）

红黑数

红?树特点:

1. 每个节点?红即?；
2. 根节点总是??的；
3. 每个叶?节点都是??的空节点（NIL节点）；
4. 如果节点是红?的，则它的?节点必须是??的（反之不?定）；
5. 从根节点到叶节点或空?节点的每条路径，必须包含相同数?的??节点（即相同的???度）。
   红?树的应?：
   TreeMap、TreeSet以及JDK1.8的HashMap底层都?到了红?树。
   为什么要?红?树？
   简单来说红?树就是为了解决?叉查找树的缺陷，因为?叉查找树在某些情况下会退化成?个线性结构。详细了解可以查看 漫画：什么是红?树？（也介绍到了?叉查找树，?常推荐）

• 寻找红?树的操作?册（?章排版以及思路真的不错）
• 红?树深?剖析及Java实现（美团点评技术团队）

B-，B+，B*树

BFS及DFS

BFS及DFS的Java实现

数据结构面试（一）

原文：https://www.cnblogs.com/liufei2/p/14674161.html