java 数据结构基础

数据结构基础

---

• 数组
  定义：数组是一个定长的容器,数组中存储的数据类型需要是一致的
  • 无序数组：
    优点：查询快，知道索引的情况下可以快速存取
    缺点：删除慢，大小固定
  • 有序数组：
    优点：比无序数组查找快
    缺点：删除和插入慢，大小固定

---

• 栈
  定义：栈是一种只允许在一端进行插入和删除操作的特殊线性表。
  优点：提供后进先出的存取方式
  缺点：存取其他项很慢
  应用场景：十进制转N禁止、表达式求值、行编辑器等

---

• 队列
  定义：队列是一种在一端进行插入，而在另一端进行删除的特殊线性表。
  优点：提供先进先出的存取方式
  缺点：存取其他项很慢
  应用场景：Java 集合中的 Queue 继承自 Collection 接口 ，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问。除了继承 Collection 接口的一些方法，Queue 还添加了额外的 添加、删除、查询操作。
  补充：
  • 顺序队列（也就是常见的队列, 每次添加元素时，都是添加到队尾，存在“假溢出”的问题也就是明明有位置却不能添加的情况）
  • 循环队列（避免了“假溢出”的问题）
    循环队列中当front或rear=maxSize-1时我们就不能进行自增操作了，比如一个队列尾长度为4的数组datas[4]，那么当front或rear需要在0,1,2,3之间进行循环“推进”，以此达到循环队列的效果。所以我们可以使用rear = （rear+1）%maxSize ；front = （front+1）%maxSize ；公式进行指针计算，需要注意的是：队空状态的条件为：front = rear。而如果整个队列全部存满数据那么，队满的条件也是front = rear；所以循环队列需要损失一个存储空间，如下图：

---

• 链表
  定义：链表是一个线性结构，但是存储的数据可以是非线性的。链表由一个个子节点构成，每个节点有两个部分：数据域和指针域，数据域就是实际存储数据的，指针域可以有一个和两个，单链表就是单个指针域指向后一个节点，双链表就是节点有两个指针域，分别指向前一个和后一个节点。
  优点：插入、删除快，插入删除不需要移动所有节点，只需要将待插入的节点的指针域一个指向待插入位置的后一个节点，一个指向前一个节点
  缺点：查找慢，查找的时候必须遍历节点。

---

• 树
  定义：树是具有n个结点的有限集合
  • 二叉树
    优点：查找、插入、删除都快（平衡二叉树）
    缺点：删除算法复杂
  • 红-黑树
    优点：查找、删除、插入快，树总是平衡的（局部调整）
    缺点：算法复杂

---

• 哈希表
  定义：根据设定的Hash函数 - 和处理冲突的方法，将一组关键字映象 到一个有限的连续的地址集（区间）上，并以关键字在地址集中的象 作为记录在表中的存储位置，这样的表便称为Hash表 ；
  优点：已知关键字的情况下存取速度极快，插入快
  缺点：删除慢，不知道关键字的情况下存取速度很慢，对存储空间使用不充分
• 堆
  优点：插入、删除快，对最大数据的项存取很快
  缺点：对其他数据项存取很慢
• 图
  优点：对现实世界建模
  缺点：算法复杂且慢

---