常见数据结构种类

常见数据结构种类

数据存储的常用结构有：栈、队列、数组、链表和红黑树

a.队列（queue）
– 先进先出，后进后出。
– 场景：各种排队。叫号系统。
– 有很多集合可以实现队列。

b.栈（stack）
– 后进先出，先进后出
– 压栈 == 入栈
– 弹栈 == 出栈
– 场景：手枪的弹夹。

c.数组
– 数组是内存中的连续存储区域。
– 分成若干等分的小区域（每个区域大小是一样的）
– 元素存在索引
– 特点：查询元素快（根据索引快速计算出元素的地址，然后立即去定位）
增删元素慢（创建新数组，迁移元素）

d.链表
– 元素不是内存中的连续区域存储。
– 元素是游离存储的。每个元素会记录下个元素的地址。
– 特点：查询元素慢
增删元素快（针对于首尾元素，速度极快，一般是双链表）

e.红黑树
二叉树：binary tree 永远只有一个根节点,是每个结点不超过2个节点的树（tree） 。
查找二叉树,排序二叉树：小的左边，大的右边，但是可能树很高，性能变差。
为了做排序和搜索会进行左旋和右旋实现平衡查找二叉树，让树的高度差不大于1
红黑树（就是基于红黑规则实现了自平衡的排序二叉树）：
树尽量的保证到了很矮小，但是又排好序了，性能最高的树。红黑树的增删查改性能都好！！！

树->二叉树->二叉排序树（二叉查找树）->平衡二叉树->红黑树

这些结构，其实Java早就通过代码实现了，我们要知道有这些结构即可!