八大数据结构

目录

时空复杂度

数组

一维数组

二维数组

链表

单向链表

双向链表

循环链表

队列

顺序队列

循环队列

队列的数组实现

队列的链表实现

栈

进栈

出栈

哈希表

树

无序树

有序树

二叉树

红黑树

B 树

树的遍历

堆

图

---

---

由简入繁 从繁至简 大道至简 人生亦简 简单到复杂是前半生的阅历 复杂到简单是后半生的修行 愿你阅尽霜华 内心依旧温暖如春

时空复杂度

时间复杂度(运行时间)和空间复杂度(占用空间)是衡量算法好坏的重要指标。时间复杂度用大写的O来表示，具体复杂的程度用括号里面的常量或者对数函数表示。

O(1)：最低复杂度，耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）。

O(n)：数据量增大几倍，耗时也增大几倍，比如遍历算法，要找到一个数组里面最大的一个数，就要把n个变量都扫描对比一遍，操作次数为n，算法复杂度是O(n)。例：100把钥匙贴上编号，用绳子串起来，要找出10号房间的钥匙，就需要一个一个去查找，钥匙越多，查找的次数就越多。

O(n^2)：n的2次方，表示数据量增大n倍时，耗时增大n的平方倍。比如冒泡排序排一个数组要双层循环，对于n个变量的数组，需要交换变量位置n^2次（n乘以n次），算法复杂度就是O(n^2)。例子：有100层楼每层有100个房间，把每层100个房间钥匙用绳子串起来，那就是100个钥匙串，要拿到某一把钥匙，就要先找到哪一层楼，再找到这一层钥匙的编号。

O(log n)：当数据量增加n倍时，耗时只增加logn倍(log是以2为底的，当数据量增加256倍时，耗时只增加8倍)。二分查找也叫折半查找，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。它的复杂度是O(log n)。

O(n log n)：就是n乘以log n，当数据增大256倍时，耗时增大256乘以8=2048倍。归并排序就是O(n log n)的时间复杂度。例：IO次数取决于B树的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m 1)N，即N=(m 1)h,当数据量N一定的情况下，m越大，h越小。m=磁盘块的大小/数据项的大小，磁盘块的大小大概是一个数据页的大小，固定的，数据项占的空间越小，单个磁盘块容纳的数量越多，树的高度越低

数组

数据结构是计算机存储、组织数据的一种方式，相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究的内容是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。数据结构和算法是解决特定问题(遇到问题时用什么数据结构和算法去解决)、深度优化程序性能的基础。常见的存储结构有线性存储结构 元素之间的关系是一对一的，如栈、队列。非线性存储结构 每个元素可能连接0或者多个元素，如树、图。

一维数组

数组采用连续的存储单元，由有限个相同类型的元素组成的有序集合 具有查询快、插入慢的特点。效率上：读取O(1)、更新O(1)、插入O(n)、删除O(n)、扩容O(n

1.  
   数组在JAVA语言中是用来存储固定大小同类型元素的容器,如下：
2.  
   public class Demo1 {
3.  
   public static void main(String[] args) {
4.  
   //定义一个数组,存储五个元素,每个元素对应着一个索引,从0开始，0,1,2,3,4分别对应着78,93,97,84,63
5.  
   int[] scores = {78,93,97,84,63};
6.  
   //输出数组中的第二个元素
7.  
   System.out.println("数组中的第2个元素为：" scores[1]);
8.  
   }
9.  
   }

1.  
   声明：
2.  
    
3.  
   语法：数据类型[ ] 数组名，数据类型 数组名[ ],数组名可以是任意合法的变量名。如：
4.  
   int[] scores;
5.  
   int scores[];
6.  
   String[] names;
7.  
    
8.  
   初始化：
9.  
    
10.  
    指定数组最多可存储元素个数，分配存储空间.
11.  
    语法:数组名 = new 数据类型[数组长度]，数组长度就是数组中能存放元素的个数。如：
12.  
    scores = new int[5];//长度为5的整数数组。
13.  
    names = new String[10];//长度为10的字符串数组。
14.  
     
15.  
    赋值：
16.  
     
17.  
    分配空间后就可以向数组中存放数据了，数组中元素都是通过下标来访问的。往数组中存放数据:
18.  
    scores[0] = 66;
19.  
    scores[1] = 77;
20.  
    Java中还提供了另外一种创建数组的方式：
21.  
    int[] scores = {66,77}; //声明、分配空间、赋值合并完成。
22.  
     
23.  
    例子：
24.  
     
25.  
    public static void main(String args[]) {
26.  
    int data[] = null; //声明
27.  
    data = new int[3]; //初始化一个长度为3的数组
28.  
    data[0] = 10; //赋值
29.  
    data[1] = 20;
30.  
    data[2] = 30;
31.  
    }

引用传递的本质，同一块堆内存空间可以被不同的栈内存所指向。 

1.  
   public class ArrayDemo {
2.  
   public static void main(String args[]) {
3.  
   int data[] = null;
4.  
   data = new int[3]; //开辟一个长度为3的数组
5.  
   int temp[] = null; //声明对象
6.  
   data[0] = 10;
7.  
   data[1] = 20;
8.  
   data[2] = 30;
9.  
   temp = data; //int temp[] = data;
10.  
    temp[0] = 99;
11.  
    for(int i = 0; i < temp.length; i ) {
12.  
    System.out.println(data[i]);
13.  
    }
14.  
    }
15.  
    }

 上述程序如果输出data[3],则会抛出异常

二维数组

 一维数组索引访问数据：

 二维数组索引访问数据：数组名称[行索引][列索引] 

二维数组初始化

•  数组的动态初始化：数据类型 对象数组[][] = new 数据类型[行个数][列个数];
• 数组的静态初始化：数据类型 对象数组[][] = new 数据类型[行个数][列个数]{{值, 值,…}, {值, 值,…},…};

1.  
   //定义一个二维数组：
2.  
    
3.  
   public class ArrayDemo {
4.  
   public static void main(String args[]) {
5.  
   //此时的数组并不是一个等列数组
6.  
   int data[][] = new int[][] {
7.  
   {1, 2, 3}, {4, 5}, {6, 7, 8, 9}};
8.  
   //如果在进行输出的时候一定要使用双重循环，
9.  
   //外部的循环控制输出的行数，而内部的循环控制输出列数
10.  
    for(int i = 0; i < data.length; i ) {
11.  
    for(int j = 0; j < data[i].length; j ) {
12.  
    System.out.print("data[" i "][" j "]=" data[i][j] "、");
13.  
    }
14.  
    System.out.println();
15.  
    }
16.  
    }
17.  
    }

链表

链表采用不连续的存储单元，由若干个节点组成，每个节点由一个元素和一个指向另一个节点的引用组成， 具有查询慢、插入快的特点。效率上：读取O(n)、更新O(1)、插入O(1)、删除O(1) 。

链表的数据存储在节点(Node)中,是一种递归的数据结构

1.  
   Public Class Node{
2.  
   E e;
3.  
   Node next;
4.  
   }

单向链表

单向链表每一个节点分为两部分，一部分是存放数据的data，另一部分是指向下一节点的next。

通过观察链表的数据结构可以发现：

• 最后一个节点的 next 指向 NULL ，这个节点是最后一个节点

• 不像数组一下子（指时间短暂或动作迅速）（指时间短暂或动作迅速）必须new出来一片空间，无需考虑空间不够用或浪费

• 需要多少个数据，就能生成多少个节点挂接起来

链表具有动态的能力(在内存足够的情况下)，不需要去处理固定容量的问题。但是缺失了高效的random access（随机访问）的能力。无法与数组一样，通过一个索引（index）直接获取对应的元素。在底层机制中数组开辟的空间在内存中是连续分布的，我们可以直接寻找索引对应的偏移，直接计算出数据存储的内存地址。链表用next连接，每个节点存储地址不同，只能通过next顺藤摸瓜找到我们要找的元素。

对于链表这种数据结构而言，在链表头或者链尾添加元素都非常方便。将元素插入链表的中间位置也十分简单，不过得注意插入的顺序

1.  
   Node insertNode = new Node(e);
2.  
   insertNode.next = prevNode.next;
3.  
   prevNode.next = insertNode;

对于链表的删除元素操作，需要找到目标节点的前驱节点。

1.  
   prev.next = delNode.next
2.  
   delNode.next = null

链表的查找操作：

单链表删除节点 删除"节点30" 删除之前："节点20"的后继节点为"节点30"，而"节点30"的后继节点为"节点40"。删除之后："节点20"的后继节点为"节点40"

单链表增加节点 在"节点10"与"节点20"之间添加"节点15"添加之前："节点10" 的后继节点为"节点20"。添加之后："节点10" 的后继节点为"节点15"，而"节点15" 的后继节点为"节点20"。

1.  
    
2.  
   前一个结点:pre
3.  
   要插入结点(node)的下一个结点:node.next
4.  
   pre的下一个结点:pre.next
5.  
    
6.  
   package LinkedList;
7.  
    
8.  
   public class Linked <T>{
9.  
    
10.  
    private class Node{
11.  
    private T t;
12.  
    private Node next;
13.  
    public Node(T t,Node next){
14.  
    this.t = t;
15.  
    this.next = next;
16.  
    }
17.  
    public Node(T t){
18.  
    this(t,null);
19.  
    }
20.  
    }
21.  
    private Node head; //头结点
22.  
    private int size; //链表元素个数
23.  
    //构造函数
24.  
    public Linked(){
25.  
    this.head = null;
26.  
    this.size = 0;
27.  
    }
28.  
     
29.  
    //获取链表元素的个数
30.  
    public int getSize(){
31.  
    return this.size;
32.  
    }
33.  
    //判断链表是否为空
34.  
    public boolean isEmpty(){
35.  
    return this.size == 0;
36.  
    }
37.  
    //链表头部添加元素
38.  
    public void addFirst(T t){
39.  
    Node node = new Node(t); //节点对象
40.  
    node.next = this.head;
41.  
    this.head = node;
42.  
    // this.head = new Node(e,head);等价上述代码
43.  
    this.size ;
44.  
    }
45.  
    //向链表尾部插入元素
46.  
    public void addLast(T t){
47.  
    this.add(t, this.size);
48.  
    }
49.  
    //向链表中间插入元素
50.  
    public void add(T t,int index){
51.  
    if (index <0 || index >size){
52.  
    throw new IllegalArgumentException("index is error");
53.  
    }
54.  
    if (index == 0){
55.  
    this.addFirst(t);
56.  
    return;
57.  
    }
58.  
    Node preNode = this.head;
59.  
    //找到要插入节点的前一个节点
60.  
    for(int i = 0; i < index-1; i ){
61.  
    preNode = preNode.next;
62.  
    }
63.  
    Node node = new Node(t);
64.  
    //要插入的节点的下一个节点指向preNode节点的下一个节点
65.  
    node.next = preNode.next;
66.  
    //preNode的下一个节点指向要插入节点node
67.  
    preNode.next = node;
68.  
    this.size ;
69.  
    }
70.  
    //删除链表元素
71.  
    public void remove(T t){
72.  
    if(head == null){
73.  
    System.out.println("无元素可删除");
74.  
    return;
75.  
    }
76.  
    //要删除的元素与头结点的元素相同
77.  
    while(head != null && head.t.equals(t)){
78.  
    head = head.next;
79.  
    this.size--;
80.  
    }
81.  
    /**
82.  
    * 上面已经对头节点判别是否要进行删除
83.  
    * 所以要对头结点的下一个结点进行判别
84.  
    */
85.  
    Node cur = this.head;
86.  
    while(cur != null && cur.next != null){
87.  
    if(cur.next.t.equals(t)){
88.  
    this.size--;
89.  
    cur.next = cur.next.next;
90.  
    }
91.  
    else cur = cur.next;
92.  
    }
93.  
     
94.  
    }
95.  
    //删除链表第一个元素
96.  
    public T removeFirst(){
97.  
    if(this.head == null){
98.  
    System.out.println("无元素可删除");
99.  
    return null;
100.  
     }
101.  
     Node delNode = this.head;
102.  
     this.head = this.head.next;
103.  
     delNode.next =null;
104.  
     this.size--;
105.  
     return delNode.t;
106.  
     }
107.  
     //删除链表的最后一个元素
108.  
     public T removeLast(){
109.  
     if(this.head == null){
110.  
     System.out.println("无元素可删除");
111.  
     return null;
112.  
     }
113.  
     //只有一个元素
114.  
     if(this.getSize() == 1){
115.  
     return this.removeFirst();
116.  
     }
117.  
     Node cur = this.head; //记录当前结点
118.  
     Node pre = this.head; //记录要删除结点的前一个结点
119.  
     while(cur.next != null){
120.  
     pre = cur;
121.  
     cur = cur.next;
122.  
     }
123.  
     pre.next = cur.next;
124.  
     this.size--;
125.  
     return cur.t;
126.  
     }
127.  
     //链表中是否包含某个元素
128.  
     public boolean contains(T t){
129.  
     Node cur = this.head;
130.  
     while(cur != null){
131.  
     if(cur.t.equals(t)){
132.  
     return true;
133.  
     }
134.  
     else cur = cur.next;
135.  
     }
136.  
     return false;
137.  
     }
138.  
     @Override
139.  
     public String toString() {
140.  
     StringBuffer sb = new StringBuffer();
141.  
     Node cur = this.head;
142.  
     while(cur != null){
143.  
     sb.append(cur.t "->");
144.  
     cur = cur.next;
145.  
     }
146.  
     sb.append("NULL");
147.  
     return sb.toString();
148.  
     }
149.  
      
150.  
     public static void main(String[] args) {
151.  
     Linked<Integer> linked = new Linked();
152.  
     for(int i = 0; i < 10; i ){
153.  
     linked.addFirst(i);
154.  
     System.out.println(linked);
155.  
     }
156.  
     linked.addLast(33);
157.  
     linked.addFirst(33);
158.  
     linked.add(33, 5);
159.  
     System.out.println(linked);
160.  
     linked.remove(33);
161.  
     System.out.println(linked);
162.  
     System.out.println("删除第一个元素：" linked.removeFirst());
163.  
     System.out.println(linked);
164.  
     System.out.println("删除最后一个元素：" linked.removeLast());
165.  
     System.out.println(linked);
166.  
     }
167.  
     }
168.  
      
169.  
      

双向链表

双向链表和单链表一样，也是由节点组成，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱。从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

双链表删除节点 删除"节点30"删除之前："节点20"的后继节点为"节点30"，"节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40"，"节点40" 的前继节点为"节点30"。删除之后："节点20"的后继节点为"节点40"，"节点40" 的前继节点为"节点20"。

 双链表添加节点 在"节点10"与"节点20"之间添加"节点15"添加之前："节点10"的后继节点为"节点20"，"节点20" 的前继节点为"节点10"。添加之后："节点10"的后继节点为"节点15"，"节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20"，"节点20" 的前继节点为"节点15"。

循环链表

循环列表是一个首尾相接的链表，将单链表最后一个指针域由NULL改为指向表头结点，称为循环单链表（单链式的循环链表）

每一个链表都包含多个节点，每个节点包含两部分，数据域（储存节点的数据信息）和引用域（储存下一个节点或者上一个节点的地址），节点的创建：

1.  
   1.创建一个节点类，节点类包含数据域和引用域。
2.  
   2.创建一个链表类，链表类包含三个属性：头结点、尾节点和大小，可添加、删除、插入等操作。
3.  
    
4.  
   private static class Node<E> {
5.  
   E item;
6.  
   Node<E> next;
7.  
   Node<E> prev;
8.  
    
9.  
   Node(Node<E> prev, E element, Node<E> next) {
10.  
    this.item = element;
11.  
    this.next = next;
12.  
    this.prev = prev;
13.  
    }
14.  
    }

队列

一种线性数据结构，先进先出，后进后出。队列的入口端叫做队尾，出口端叫做队头，入口端进行插入操作，出口端进行删除操作，插入一个队列元素称为入队，删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
效率上：入队O(1),出队O(1)
应用：消息队列、多线程等待队列等。例：

1.  
   1.电脑使用时可能会有这种经历，机器有时会处于疑似死机的状态，鼠标怎么点似乎都没用，
2.  
   双击任何快捷方式都不动弹。就当你失去耐心时，突然它像酒醒一样，把你刚才点击的所有操作全部按顺序执行一遍。
3.  
   这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。
4.  
   2.再比如打移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人
5.  
   员都占线的情况下，客户会被要求等待，直到有某个客户人员空下来，才能让最先等待的客户接通电话。
6.  
   这里也是将所有当前打客服电话的客户进行排队处理。操作系统和客服系统中，都是应用了一种数据结
7.  
   构来实现刚才提到的先进先出的排队功能，这就是队列。

       

顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，每次在队尾插入一个元素时，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。顺序队列中的溢出现象：

1.  
   （1）队头不动，出队列时队头后的所有元素向前移动
2.  
   缺陷：操作时如果出队列比较多，要搬移大量元素
3.  
   （2）队头移动，出队列时队头向后移动一个位置
4.  
   缺陷：如果还有新元素进行入队列容易造成假溢出（队列满时）

• 下溢：当队列为空时，做出队运算产生的溢出现象，是正常现象，常用作程序控制转移的条件。
• 真上溢：当队列满时，做进栈运算产生空间溢出的现象，是一种出错状态，应设法避免。顺序队列的最大存储空间已经存满二又要求进行入队列操作所引起的溢出
• 假上溢：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。

循环队列

使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件是front=（rear 1）%MaxSize。

1.  
   循环队列如何进行判空和满操作：
2.  
   1.少用一个存储单元
3.  
   2.设置一个标记flag；
4.  
   初始值 flag = 0；入队列：flag = 1； 出队列：flag = 0；
5.  
   队列为空时：（front == rear && flag == 0）
6.  
   队列为满时：（front == rear && flag == 1）

队列的数组实现

队列可以用数组Q[1…m]来存储，数组的上界m即是队列所容许的最大容量。在队列的运算中需设两个指针：head，队头指针，指向实际队头元素；tail，队尾指针，指向实际队尾元素的下一个位置。一般情况下，两个指针的初值设为0，这时队列为空，没有元素。数组定义Q[1…10]。Q(i) i=3,4,5,6,7,8。头指针head=2，尾指针tail=8。队列中拥有的元素个数为:L=tail-head。现要让排头的元素出队，则需将头指针加1。即head=head 1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail 1这时Q(9)入队。当队尾已经处理在最上面时，即tail=10，如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称为"假溢出"。克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为1。在结构上采用这种技巧来存储的队列称为循环队列。

1.  
   队列和栈一样只允许在断点处插入和删除元素。
2.  
   循环队的入队算法如下：
3.  
   1、tail=tail 1；
4.  
   2、若tail=n 1，则tail=1；
5.  
   3、若head=tail，即尾指针与头指针重合了，表示元素已装满队列，则作上溢出错处理；
6.  
   4、否则，Q(tail)=X，结束（X为新入出元素）。
7.  
   队列和栈一样，有着非常广泛的应用。
8.  
   注意：（1）有时候队列中还会设置表头结点，就是在队头的前面还有一个结点，这个结点的数据域为空，但是指针域指向队头元素。
9.  
   （2）另外，上面的计算还可以利用下面给出的公式cq.rear=(cq.front 1)/max;
10.  
    当有表头结点时，公式变为cq.rear=(cq.front 1)/（max 1）。

队列的链表实现

在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

1.  
   1）初始化队列：Init_Queue(q) ，初始条件：队q 不存在。操作结果：构造了一个空队；
2.  
   （2）入队操作： In_Queue(q,x),初始条件： 队q 存在。操作结果： 对已存在的队列q，插入一个元素x 到队尾，队发生变化；
3.  
   （3）出队操作： Out_Queue(q,x)，初始条件: 队q 存在且非空，操作结果： 删除队首元素，并返回其值，队发生变化；
4.  
   （4）读队头元素：Front_Queue(q,x)，初始条件: 队q 存在且非空，操作结果： 读队头元素，并返回其值，队不变；
5.  
   （5）判队空操作：Empty_Queue(q)，初始条件： 队q 存在，操作结果： 若q 为空队则返回为1，否则返回为0。

队列的创建

1.  
   //队列的创建1：
2.  
   Queue<Integer> queue = new LinkedList<>();//声明队列,先进先出原则
3.  
   queue.add(1);//添加数据
4.  
   queue.offer(9);//添加数据
5.  
   queue.add(3);
6.  
   queue.add(4);
7.  
   //add() offer()都是向队尾插入数据 区别是add()方法插入数据超出队列界限时候会抛出异常，而offer()方法是返回false
8.  
   queue.poll();//输出队列
9.  
   queue.peek();//输出队列但不删除
10.  
    queue.remove();//输出队列
11.  
    //在队列元素为空的情况下，remove() 方法会抛出NoSuchElementException异常，poll() 方法只会返回 null
12.  
    //队列的创建2：
13.  
    Queue<Integer> queSort = new PriorityQueue<>();//插入的数据会被排序
14.  
    queSort.add(2);
15.  
    queSort.add(16);
16.  
    queSort.add(9);
17.  
    queSort.add(1);

栈

[栈]栈是一种线性数据结构，后进先出，先进后出，最早进入的元素存放位置叫做栈底，最后进入的元素存放位置叫栈顶，栈底进，栈顶出。可以比喻成 栈是一个一端封闭一端开放的中空管子，队列是两端开放的中空管子。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。效率上：入栈O(1)，出栈O(1)，写入O(1)，读取O(1),扩容O(n)。

栈的原理

栈存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为出栈（POP）。栈也称为先进后出表。栈可以用来在函数调用的时候存储断点，做递归时要用到栈！在计算机系统中，栈则是一个动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：

1.  
   //栈的创建：
2.  
   Stack stack1 = new Stack();
3.  
   Stack<String> stackString = new Stack<>();
4.  
   stackString.add("c");
5.  
   stackString.pop();//输出元素，栈为空的时候会抛出异常
6.  
   stackString.add("a");//添加元素
7.  
   stackString.push("b");//添加元素
8.  
   //add是继承自Vector的方法，且返回值类型是boolean。
9.  
   //push是Stack自身的方法，返回值类型是参数类类型
10.  
     
11.  
    Map<String, String> map = new HashMap();//创建map,**********HashMap会根据Key值排序。
12.  
    map.put("b", "卫庄");
13.  
    map.put("a", "盖聂");
14.  
    for (Map.Entry<String, String> entry : map.entrySet()) {
15.  
    System.out.println(entry.getValue());
16.  
    System.out.println(entry.getKey());
17.  
    }

进栈

1.  
   进栈（PUSH）算法
2.  
    
3.  
   例如：有一个数列（23，45，3，7，3，945）
4.  
   我们先对其进行进栈操作，则进栈顺序为：23，45，3，7，3，945
5.  
   我们在对其进行出栈操作，则出栈顺序为：945，3，7，3，45，23
6.  
   算法思想：
7.  
   括号作用域检查的原则是，对表达式从左到右扫描。当遇到左括号时，左括号入栈；当遇到右括号时，首先将栈顶元素弹出栈，
8.  
   再比较弹出元素是否与右括号匹配，若匹配，则操作继续；否则，查出错误，并停止操作。当表达式全部扫描完毕，若栈为空，
9.  
   说明括号作用域嵌套正确，反之，说明表达式有错误。

出栈

1.  
   初始化
2.  
   void InitStack(SqStack *S){
3.  
   S->top = -1; //初始化栈顶指针
4.  
   }
5.  
   判栈空
6.  
   bool StackEmpty(SqStack S){
7.  
   if(S.top == -1){
8.  
   return true; //栈空
9.  
   }else{
10.  
    return false; //不空
11.  
    }
12.  
    }
13.  
     
14.  
    进栈操作push
15.  
    /*插入元素e为新的栈顶元素*/
16.  
    Status Push(SqStack *S, ElemType e){
17.  
    //满栈
18.  
    if(S->top == MAXSIZE-1){
19.  
    return ERROR;
20.  
    }
21.  
    S->top ; //栈顶指针增加一
22.  
    S->data[S->top] = e; //将新插入元素赋值给栈顶空间
23.  
    return OK;
24.  
    }
25.  
    出栈操作pop
26.  
    /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
27.  
    Status Pop(SqStack *S, ElemType *e){
28.  
    if(S->top == -1){
29.  
    return ERROR;
30.  
    }
31.  
    *e = S->data[S->top]; //将要删除的栈顶元素赋值给e
32.  
    S->top--; //栈顶指针减一
33.  
    return OK;
34.  
    }
35.  
    读取栈顶信息
36.  
    /*读栈顶元素*/
37.  
    Status GetTop(SqStack S, ElemType *e){
38.  
    if(S->top == -1){ //栈空
39.  
    return ERROR;
40.  
    }
41.  
    *e = S->data[S->top]; //记录栈顶元素
42.  
    return OK;
43.  
    }
44.  
     
45.  
     

哈希表

[哈希表]是一种数据结构，提供了键key和值value的映射关系。哈希表本质上是一个数组，不过数组是根据下标，像a[0]、a[1]、a[2]这样来访问，而哈希表的key一般是以字符串为主，通过哈希函数，可以把字符串类型或者其他类型的key，转化成数组的下标index。例如：

1.  
   给出一个长度为8的数组
2.  
   当key=0011011时，index=HashCode("0011011")%Array.length=7
3.  
   当key=this时, index=HashCode("this")%Array.length=6

哈希函数

散列表也叫哈希表，是一种通过键值对直接访问数据的结构。散列表的实现原理就是映射的原理，通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现O(1)的数据访问效率。在映射的过程中，事先设定的函数就是一个映射表，也可以称作散列函数或者哈希函数。散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数：

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。
• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
• 平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。 确定好散列函数之后，通过某个key值会得到一个唯一的value地址。但有时会出现一些特殊情况，通过不同的key值可能会访问到同一个地址，这个现象称之为冲突。

哈希冲突

哈希冲突不同的key通过哈希函数获取的下标有可能是相同的，例如0011011这个key对应的数组下标是2,0022011这个key对应的数组下标也是2，这种情况就是哈希冲突。
如何解决哈希冲突

• 开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，* 比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
• 再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
• 链地址法：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的。
• 公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。
  目前比较常用的冲突解决方法是链地址法，一般可以通过数组和链表的结合达到冲突数据缓存的目的。例如：HashMap，存储结构是数组 链表 红黑树(jdk1.8)。 

 

两个对象的 hashCode()相同，则 equals()也一定为true，对吗？

1.  
   不对，两个对象的hashCode值相同，内容不一定相同。
2.  
   String str1 = "通话";
3.  
   String str2 = "重地";
4.  
   System. out. println(String. format("str1：%d | str2：%d", str1. hashCode(),str2. hashCode()));
5.  
   System. out. println(str1. equals(str2));
6.  
   执行的结果：
7.  
   str1：1179395 | str2：1179395
8.  
   false
9.  
   '通话'和'重地'的哈希值相同，但是内容不同，在散列表中，hashCode()相等即两个键值对的哈希值相等，然而哈希值相等，并不一定能得出键值对相等。

数据结构操作演示地址：Data Structure Visualization

树

一种树状的数据结构，将有限个节点根据不同层次关系进行排列，从而形成数据与数据之间的父子关系。其表现形式像"倒挂的树"，将根朝上叶朝下。数据存储在节点中，每个节点有零个或者多个子节点。没有父节点的节点在最顶端，成为根节点；没有非根节点有且只有一个父节点；每个非根节点又可以分为多个不相交的子树。这意味着树是具备层次关系的，父子关系清晰，这也是树与图之间最主要的区别，树可看作是链表的高配版，树的实现就是对链表的指针域进行了扩充，增加了多个地址指向子结点。同时将“链表”竖起来，从而凸显了结点之间的层次关系，更便于分析和理解。树可以衍生出许多的结构，若将指针域设置为双指针，那么即可形成最常见的二叉树，即每个结点最多有两个子树的树结构。二叉树根据结点的排列和数量还可进一度划分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

无序树

树的任意节点的子节点没有顺序关系

有序树

非二叉树

每个节点有两个以上的分支。

二叉树(Binary Tree)

二叉树

每个节点最多只有两个分支，也可能只有1个，或者没有，通常称作左子树或者右子树。

1.  
   二叉树，是由很多个TreeNode构成的这种树形的数据结构
2.  
   class TreeNode {
3.  
   int value;
4.  
   TreeNode left;
5.  
   TreeNode right;
6.  
   }

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。完全二叉树对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。 如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树

完全二叉树

定义：除了最后一层，其他层都是满的，那么最后一层的节点要靠左排列且中间不允许有气泡。比如左边不是完全二叉树，右边的是

那么完全二叉树的最大的好处就是因为它排列紧密没有气泡，所以可以用数组来存储，这样就大大节省了内存空间

平衡二叉树 Balanced Binary Tree：定义：对于这棵树里的每个节点，它的左子树和右子树的高度差不大于 1。这里要注意，是对于每个节点，而不只是对于根结点。比如左边这棵树就不是平衡二叉树，右边的才是。

那么大名鼎鼎的 AVL-Tree 就是平衡二叉树，准确说是自平衡二叉查找树。那什么是二叉查找树呢？ 

完美二叉树

定义：所有层的所有节点都必须是满的。完美二叉树比完全二叉树的定义更加严格，包括最后一层，每一层的节点都要是满的，毕竟是追求完美的嘛。所以我们如果知道了层数，就知道了它有多少个节点，也就是一个等比数列求和。

对二叉查找树

最重要的性质就是：在做中序遍历时，这个序列是一个升序序列。当你在做二叉查找树的算法题没有思路时，可以想想这个性质，很多题目都会迎刃而解。

 

完满二叉树

定义：对于这棵树的每个节点而言，要么有 0 个孩子，要么有 2 个孩子

 

二叉查找树(Binary Search Tree)

也称为二叉搜索树、有序二叉树或者排序二叉树。

1.  
   1.若任意节点的左子树不为空，则左子树上所有节点的值都小于根节点。
2.  
   2.若任意节点的右子树不为空，则右子树上所有节点的值都大于等于根节点。
3.  
   3.任意节点的左右子树也分别为二叉查找树。
4.  
   二叉查找树有个非常严重的问题，如果数据的插入是从小到大插入{1，2，3，4，5}
5.  
   或者从大到小插入{5，4，3，2，1}会导致二叉查找树退化称单链表的形式。
6.  
   为了解决这个问题，平衡树。

平衡树

任意节点的子树的高度差都小于等于1。常见的符合平衡树的有AVL树(二叉平衡搜索树)、B树(多路平衡搜索树、2-3树、2-3-4树等)、红黑树等。

AVL树(由发明者Adelson-Velsky和Landis首字母缩写命名)

任意节点两个子树的高度差不超过1的平衡树。

红黑树

根节点是黑色，如果一个节点是红色，则它的子节点必须是黑色，红色节点不连续。

B 树

B树：指向下一节点的指针、每个节点的关键字以及关键字所代表的文件地址这三块一起构成了B树的一个节点，每一个节点都存储在一个磁盘块上。B树中子树的个数总比关键字个数多1个。关键字查询过程中，如果查询到的和关键字一致，则停止查询，直接取数据。

1.  
   1. 2-3树
2.  
   具有两个子节点和一个数据元素的节点称作2节点，具有三个子节点和两个数据元素的节点称作3节点，
3.  
   所以整棵树叫做2-3树
4.  
   2. 2-3-4树
5.  
   包含2个子节点和一个数据元素，包含3个子节点和一个数据元素，包含4个子节点和一个数据元素
6.  
   3.2-3-4-5-n的这一类的树统称为B树。

B 树

相对于B树，在内部节点中关键字的个数与其子树的个数相同，磁盘块上少了关键字代表的文件地址，所以在总数据量一定的情况下， 单个磁盘块可以容纳更多的关键字，更多的节点指针，减少了数据从磁盘块读入到内存的次数(I/O读写次数降低)，提高了磁盘IO性能。 表面上来看B 树会变胖，树的高度变低。对于数据查询操作，任何关键字的查找都会从根结点开始依次经过子节点最后到指定的叶子结点取到对应的数据。 所有关键字查询的路径长度相同，每一个数据的查询效率相当。如果查询过程中，查询到的和关键字一致，则继续下搜索，直到找到叶子节点上对应的数据位置。

B 树的优势

• 磁盘读写代价低 B 树的内部结点并没有指向关键字具体信息的指针。磁盘块所能容纳的关键字数量越多。一次性读入内存中的需要查找的关键字也就越多。 相对来说I/O读写次数也就降低了。

• 查询效率稳定 由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。 所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

• 更有利于对数据库的扫描 B树在提高了磁盘IO性能的同时并没有解决元素遍历效率低下的问题，而B 树只需要遍历叶子节点就可以解决对全部关键字信息的扫描， 所以对于数据库中频繁使用的range query，B 树有着更高的性能。

树的遍历

前序 pre order：根节点、左子树、右子树

中序 in order：左子树、跟节点、右子树 

后序 post order：左子树、右子树、根节点 

无论是哪种遍历顺序都是不变的，变的只是打印的顺序罢了。这三种遍历都是深度优先遍历 DFS，而层序遍历是广度优先遍历 BFS。DFS 和 BFS 都是图的基本遍历方式 

堆

堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子结点进行对应，因此堆总是一颗完全二叉树。对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n 1，2n 2，因此可以直接用数组来表示一个堆。不仅如此，堆还有一个性质：堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆常用来实现优先队列，在面试中经常考的问题都是与排序有关，比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值，因而可以在建堆以及重建堆的过程中，筛选出数据序列中的极值，从而达到排序或者挑选topK值的目的。

图

图的简介

图（Graph）结构是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行（自动机）等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。 相较于上文的几个数据结构可能接触的不多，图结构一般包括顶点和边，顶点通常用圆圈来表示，边就是这些圆圈之间的连线。边还可以根据顶点之间的关系设置不同的权重，默认权重相同皆为1。此外根据边的方向性，还可将图分为有向图和无向图。

邻接矩阵

目前常用的图存储方式为邻接矩阵，通过所有顶点的二维矩阵来存储两个顶点之间是否相连，或者存储两顶点间的边权重。

• 无向图的邻接矩阵是一个对称矩阵，是因为边不具有方向性，若能从此顶点能够到达彼顶点，那么彼顶点自然也能够达到此顶点。此外，由于顶点本身与本身相连没有意义，所以在邻接矩阵中对角线上皆为0。
• 有向图由于边具有方向性，因此彼此顶点之间并不能相互达到，所以其邻接矩阵的对称性不再。 用邻接矩阵可以直接从二维关系中获得任意两个顶点的关系，可直接判断是否相连。但是在对矩阵进行存储时，却需要完整的一个二维数组。若图中顶点数过多，会导致二维数组的大小剧增，从而占用大量的内存空间。 而根据实际情况可以分析得，图中的顶点并不是任意两个顶点间都会相连，不是都需要对其边上权重进行存储。那么存储的邻接矩阵实际上会存在大量的0。虽然可以通过稀疏表示等方式对稀疏性高的矩阵进行关键信息的存储，但是却增加了图存储的复杂性。 因此，为了解决上述问题，一种可以只存储相连顶点关系的邻接表应运而生。

邻接表

在邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。相较于无向图，有向图的情况更为复杂，因此这里采用有向图进行实例分析。 在邻接表中，每一个顶点都对应着一条链表，链表中存储的是顶点能够达到的相邻顶点。存储的顺序可以按照顶点的编号顺序进行。 通过邻接表可以获得从某个顶点出发能够到达的顶点，从而省去了对不相连顶点的存储空间。然而，这还不够。对于有向图而言，图中有效信息除了从顶点“指出去”的信息，还包括从别的顶点“指进来”的信息。这里的“指出去”和“指进来”可以用出度和入度来表示。入度：有向图的某个顶点作为终点的次数和。出度：有向图的某个顶点作为起点的次数和。 由此看出，在对有向图进行表示时，邻接表只能求出图的出度，而无法求出入度。这个问题很好解决，那就是增加一个表用来存储能够到达某个顶点的相邻顶点。这个表称作逆邻接表。

逆邻接表

逆邻接表与邻接表结构类似，只不过图的顶点链接着能够到达该顶点的相邻顶点。也就是说，邻接表时顺着图中的箭头寻找相邻顶点，而逆邻接表时逆着图中的箭头寻找相邻顶点。 邻接表和逆邻接表的共同使用下，就能够把一个完整的有向图结构进行表示。可以发现，邻接表和逆邻接表实际上有一部分数据时重合的，因此可以将两个表合二为一，从而得到了所谓的十字链表。

十字链表

十字链表似乎很简单，只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间，但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用，反而是进行了再次存储。十字链表优化后，可通过扩展的顶点结构和边结构来进行正逆邻接表的存储：（下面的弧头可看作是边的箭头那端，弧尾可看作是边的圆点那端）

1.  
   data：用于存储该顶点中的数据；
2.  
   firstin指针：用于连接以当前顶点为弧头的其他顶点构成的链表，即从别的顶点指进来的顶点；
3.  
   firstout指针：用于连接以当前顶点为弧尾的其他顶点构成的链表，即从该顶点指出去的顶点；
4.  
   边结构通过存储两个顶点来确定一条边，同时通过分别代表这两个顶点的指针来与相邻顶点进行链接：
5.  
   tailvex：用于存储作为弧尾的顶点的编号；
6.  
   headvex：用于存储作为弧头的顶点的编号；
7.  
   headlink 指针：用于链接下一个存储作为弧头的顶点的节点；
8.  
   taillink 指针：用于链接下一个存储作为弧尾的顶点的节点；

十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示，能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。具体的操作可能一时间不好弄懂，建议多研究一下，弄清指针指向的意义，明白正向和逆向邻接表的表示。

这篇好文章是转载于：学新通技术网