Java 程序员必须掌握的 8 道数据结构面试题，你会几道？( 二 ) _Java

Dequeue()?——移除队列头部的元素
isEmpty()——如果队列为空，则返回true
Top()?——返回队列的第一个元素
面试中关于队列的常见问题
使用队列表示栈
对队列的前k个元素倒序
使用队列生成从1到n的二进制数
链表
链表是另一个重要的线性数据结构，乍一看可能有点像数组，但在内存分配、内部结构以及数据插入和删除的基本操作方面均有所不同。关注Java技术栈微信公众号，回复"面试"获取更多博主精心整理的面试题。
链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。链表还包含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。
链表一般用于实现文件系统、哈希表和邻接表。
这是链表内部结构的展示：

文章插图
链表包括以下类型：
单链表（单向）
双向链表（双向）
链表的基本操作：
InsertAtEnd - 在链表的末尾插入指定元素
InsertAtHead - 在链接列表的开头/头部插入指定元素
Delete - 从链接列表中删除指定元素
【Java 程序员必须掌握的 8 道数据结构面试题，你会几道？】DeleteAtHead - 删除链接列表的第一个元素
Search - 从链表中返回指定元素
isEmpty - 如果链表为空，则返回true
面试中关于链表的常见问题
反转链表
检测链表中的循环
返回链表倒数第N个节点
删除链表中的重复项
图
图是一组以网络形式相互连接的节点。节点也称为顶点。一对节点（x，y）称为边（edge），表示顶点x连接到顶点y 。边可以包含权重/成本，显示从顶点x到y所需的成本。

文章插图
图的类型
无向图
有向图
在程序语言中，图可以用两种形式表示：
邻接矩阵
邻接表
常见图遍历算法
广度优先搜索
深度优先搜索
面试中关于图的常见问题
实现广度和深度优先搜索
检查图是否为树
计算图的边数
找到两个顶点之间的最短路径
树
树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。树类似于图，但区分树和图的重要特征是树中不存在环路。
树形结构被广泛应用于人工智能和复杂算法，它可以提供解决问题的有效存储机制。
这是一个简单树的示意图，以及树数据结构中使用的基本术语：

文章插图
Root - 根节点
Parent - 父节点
Child - 子节点
Leaf - 叶子节点
Sibling - 兄弟节点
想要学习Java高架构、分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频免费获取架构群：835544715
点击链接加入群聊【JAVA高级架构】：https://jq.qq.com/?_wv=1027&k=5dbERkY
以下是树形结构的主要类型：
N元树
平衡树
二叉树
二叉搜索树
AVL树
红黑树
2-3树
其中，二叉树和二叉搜索树是最常用的树。
面试中关于树结构的常见问题：
求二叉树的高度
在二叉搜索树中查找第k个最大值
查找与根节点距离k的节点
在二叉树中查找给定节点的祖先节点
字典树（Trie）
字典树，也称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。它能够提供快速检索，主要用于搜索字典中的单词，在搜索引擎中自动提供建议，甚至被用于IP的路由。
以下是在字典树中存储三个单词“top”，“so”和“their”的例子：

文章插图
这些单词以顶部到底部的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“theirs”的底部。
面试中关于字典树的常见问题
计算字典树中的总单词数
打印存储在字典树中的所有单词
使用字典树对数组的元素进行排序
使用字典树从字典中形成单词
构建T9字典（字典树+ DFS ）
哈希表
哈希法（Hashing）是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“键（key）”）中的过程。因此，对象以键值对的形式存储，这些键值对的集合被称为“字典” 。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构，但最常用的数据结构是哈希表。