常见的数据结构

数据存储的常用结构有：栈、队列、数组、链表和红黑树。我们分别来了解一下：

一 . 栈

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其 他任何位置进行添加、查找、删除等操作。

特点：

1.先进后出

2.只能在一端进行元素的添加和删除

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/343d35e55578491e98b6b62e697177ac/clipboard.png

二  . 队列

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入， 而在表的另一端进行删除。

特点：

1.  先进先出 （即，存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。例如，小火车过山 洞，车头先进去，车尾后进去；车头先出来，车尾后出来

队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口

2. 队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/6b37a700a76048fdb7b1853932517c98/clipboard.png

三   数组

特点：

1. 增删慢（长度不可变）

2.查询快（元素有对应的索引，是一片）

四   链表

特点：

1 增删快（增删元素不会改变原有内容）

2.查询慢（智能通过上一个元素找到下一个元素）

单向列表

双向列表

五  红黑树

特点：

      查询快

名词解释：

二叉树：分支不超过两个

查找树/排序树：是一个有序的二叉树（左子树小于节点，右子树大于节点）左中右，则是从小到大的顺序

平衡树：左右子树高度差不超过1

红黑树：接近于平衡式，查询速度非常快

Map的特点：

     1 每个元素由键值队组成

     2 其中键不能重复，值可以重复

             3 可以通过键找到对应的值

1.3  Map接口中的常用方法

public V put(K key, V value) :  把指定的键与指定的值添加到Map集合中。

public V remove(Object key) : 把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的 值。

public  V containsKey(Object key):  判断指定的键是否存在

public  V containsValue(Object key):判断指定的值是否存在

public V get(Object key) 根据指定的键，在Map集合中获取对应的值。

public Set<K> keySet() : 获取Map集合中所有的键，存储到Set集合中。

public Set<Map.Entry<K,V>> entrySet() : 获取到Map集合中所有的键值对对象的集合(Set集合)。

1.4   Map集合遍历键找值方式

键找值方式：即通过元素中的键，获取键所对应的值

分析步骤：

1. 获取Map中所有的键，由于键是唯一的，所以返回一个Set集合存储所有的键。方法提示: keyset() 2. 遍历键的Set集合，得到每一个键。

3. 根据键，获取键所对应的值。方法提示: get(K key)

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/0849bfcfa0154118a7e93807285e0c0e/clipboard.png

1.5  Entry键值对对象

我们已经知道， Map 中存放的是两种对象，一种称为key(键)，一种称为value(值)，它们在值对的在 Map 中是一一对应关 系，这一对对象又称做 Map 中的一个 Entry(项) 。 Entry 将键对应关系封装成了对象。即键值对对象，这 样我们在遍历 Map 集合时，就可以从每一个键值对（ Entry ）对象中获取对应的键与对应的值。

既然Entry表示了一对键和值，那么也同样提供了获取对应键和对应值得方法：

public K   getKey() ：获取Entry对象中的键。

public V  getValue() ：获取Entry对象中的值。 在Map集合中也提供了获取所有Entry对象的方法：

public Set<Map.Entry<K,V>> entrySet() : 获取到Map集合中所有的键值对对象的集合(Set集合)。

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/0c96064a251542a6bc6c921cc3cd1395/clipboard.png

常见的数据结构

数据存储的常用结构有：栈、队列、数组、链表和红黑树。我们分别来了解一下：

一 . 栈

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其 他任何位置进行添加、查找、删除等操作。

特点：

1.先进后出

2.只能在一端进行元素的添加和删除

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/343d35e55578491e98b6b62e697177ac/clipboard.png

二  . 队列

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入， 而在表的另一端进行删除。

特点：

1.  先进先出 （即，存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。例如，小火车过山 洞，车头先进去，车尾后进去；车头先出来，车尾后出来

队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口

2. 队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/6b37a700a76048fdb7b1853932517c98/clipboard.png

三   数组

特点：

1. 增删慢（长度不可变）

2.查询快（元素有对应的索引，是一片）

四   链表

特点：

1 增删快（增删元素不会改变原有内容）

2.查询慢（智能通过上一个元素找到下一个元素）

单向列表

双向列表

五  红黑树

特点：

      查询快

名词解释：

二叉树：分支不超过两个

查找树/排序树：是一个有序的二叉树（左子树小于节点，右子树大于节点）左中右，则是从小到大的顺序

平衡树：左右子树高度差不超过1

红黑树：接近于平衡式，查询速度非常快

Map的特点：

     1 每个元素由键值队组成

     2 其中键不能重复，值可以重复

             3 可以通过键找到对应的值

1.3  Map接口中的常用方法

public V put(K key, V value) :  把指定的键与指定的值添加到Map集合中。

public V remove(Object key) : 把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的 值。

public  V containsKey(Object key):  判断指定的键是否存在

public  V containsValue(Object key):判断指定的值是否存在

public V get(Object key) 根据指定的键，在Map集合中获取对应的值。

public Set<K> keySet() : 获取Map集合中所有的键，存储到Set集合中。

public Set<Map.Entry<K,V>> entrySet() : 获取到Map集合中所有的键值对对象的集合(Set集合)。

1.4   Map集合遍历键找值方式

键找值方式：即通过元素中的键，获取键所对应的值

分析步骤：

1. 获取Map中所有的键，由于键是唯一的，所以返回一个Set集合存储所有的键。方法提示: keyset() 2. 遍历键的Set集合，得到每一个键。

3. 根据键，获取键所对应的值。方法提示: get(K key)

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/0849bfcfa0154118a7e93807285e0c0e/clipboard.png

1.5  Entry键值对对象

我们已经知道， Map 中存放的是两种对象，一种称为key(键)，一种称为value(值)，它们在值对的在 Map 中是一一对应关 系，这一对对象又称做 Map 中的一个 Entry(项) 。 Entry 将键对应关系封装成了对象。即键值对对象，这 样我们在遍历 Map 集合时，就可以从每一个键值对（ Entry ）对象中获取对应的键与对应的值。

既然Entry表示了一对键和值，那么也同样提供了获取对应键和对应值得方法：

public K   getKey() ：获取Entry对象中的键。

public V  getValue() ：获取Entry对象中的值。 在Map集合中也提供了获取所有Entry对象的方法：

public Set<Map.Entry<K,V>> entrySet() : 获取到Map集合中所有的键值对对象的集合(Set集合)。

file:///E:/%25E6%259C%2589%25E9%2581%2593%25E4%25BA%2591%25E7%25AC%2594%25E8%25AE%25B0/qq96A145228CBDB86FAC3BA2574F4C1A63/0c96064a251542a6bc6c921cc3cd1395/clipboard.png