数组（Array）

数组（Array）由相同类型的元素（Element）组成，并且使用一块连续的内存来存储。可以直接用索引（index）计算出该元素对应的存储地址
特点是：提供了随机访问 并且容量有限

1
2
3
4
假设数组长度为n
访问：O（1） 访问特定位置的元素
插入：O（n） 最坏的情况，插入在数组首位，需要移动整个数组元素
删除：O（n） 最坏的情况，删数组开头元素，需将后面的元素整个前移

链表（LinkedList）

虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据
链表的删除和插入操作的复杂度为O（1），因为只需要知道目标元素的上一个元素位置即可，但是在查找的时候复杂度为O（n）

使用链表结构可以克服数组需要预知大小的缺点。链表可以充分利用计算机内存空间，进行灵活内存管理。但是链表不是节省空间，相对于数组会占用更多空间，
因为每个节点还要存储指向其他节点的指针。除此以外，链表不具有数组随机读取的优点

链表分类

  1. 单链表
  2. 双向链表
  3. 循环链表
  4. 双向循环链表
    1
    2
    3
    假如列表中有n个元素
    访问：O（n）     访问特定位置的元素
    插入删除：O（1） 需知道插入元素的位置

单链表

只有一个方向，节点只有一个后继指针next指向后面的一个节点。因此这种链表在物理内存上是不连续的。
我们习惯把第一个节点叫头节点，通过头节点我们可以遍历整个链表。头节点不保存任何值，尾节点指向null。

循环链表

是一种特殊的单链表，与单链表不同的地方在于尾节点是指向头节点

双向链表

包含两个指针，一个（prev）指向前一个节点，一个(next)指向后一个节点

双向循环链表

尾节点的next指向头节点，头节点的prev指向尾节点，构成一个环。

数组和链表的应用场景和区别

  • 数组支持随机访问，链表不支持
  • 数组使用连续内存空间对CPU的缓存机制友好，链表则相反
  • 数组的大小固定，链表支持动态扩容（数组如果声明过小，需要另外申请一块更大的内存空间存放，然后将原数组拷贝进去，这个操作比较耗时）
  • 如果需要存储的数据元素个数确定，并且不需要经常添加和删除，就使用数组
  • 如果需要存储的数据元素个数不确定，并且需要经常添加和删除，就使用链表

栈（Stack）

只允许在有序的线性数据集合的一端进行加入数据和取出数据，即在栈顶（top）中进行数据push或pop。按照后进先出（LIFO，last in first out）的方式运作。
栈常用一维数组或者链表来实现，用数组实现的叫顺序栈；用链表实现的叫链式栈

1
2
3
假设栈中有n个元素
访问：O（n）     最坏的情况访问元素在栈底（bottom）
插入删除：O（1） 顶端插入和删除元素

栈的应用场景

当我们需要处理的数据只涉及在一端插入和删除数据，并且满足 后进先出 的特征时，使用栈数据结构。

栈实现游览器的前进后退

使用两个栈stack1、stack2实现这个功能：按顺序查看了1 2 3 4这四个页面，依次将四个页面入栈。
当想回看2页面时，先将4,3取出放入stack2。这时情况为stack1：1 2；stack2：4 3。
前进看3页面时，将stack2中的3取出放入stack1.这时情况为stack1：1 2 3；stack2：4。

栈实现检查符号是否成对出现

给定一个只包含{ } [ ] ( )的字符串，判断是否有效
有效需要满足：比如 “()”、”()[]{}”、”{[]}” 都是有效字符串，而 “(]” 、”([)]” 则不是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean isValid(String str){
    Map<Character,Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');
    Stack stack = new Stack();
    for(int i=0; i<str.length(); i++>){
        char s = str.charAt(i);
        if(map.containsKey(s)){
            char c = stack.isEmpty() ? '@' : stack.pop();
            if(c != map.get(s)){
                return false;
            }
        }else{
            stack.push(s);
        }
        return stack.isEmpty();
    }
}

栈实现字符串反转

将每个字符入栈再取出即反转

栈实现维护函数的调用顺序

写了多个函数嵌套的代码，最后一个被调用的函数必须最先执行。fun(fun1(fun2()))。fun2最先执行，符合后进先出特征

栈的实现

栈既可以通过数组实现，也可以通过链表实现。 不管是基于数组还是链表，入栈、出栈的时间复杂度都为O（1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//使用数组实现栈
public class MyStack<E> {

    private int count;
    private int capacity;
    private E[] storage;
    private static final int FACTOR = 2;

    public MyStack(){
        this.count = 0;
        this.capacity = 8;
        this.storage = (E[]) new Object[8];
    }

    public MyStack(int capacity){
        this.count = 0;
        this.capacity = capacity;
        this.storage = (E[]) new Object[capacity];
    }

    private void push(E e){
        if(count == capacity){
            capacity = capacity * FACTOR;
            storage = Arrays.copyOf(storage, capacity);
        }
        storage[count++] = e;
    }

    /**
     * 返回栈顶元素不出栈
     * @return
     */
    private E peek(){
        return storage[count - 1];
    }

    /**
     * 返回栈顶元素并出栈
     * @return
     */
    private E pop(){
        return storage[--count];
    }

    private boolean isEmpty(){
        return size() == 0;
    }

    private int size(){
        return count;
    }

    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>(1);
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        myStack.push(6);
        myStack.push(7);
        myStack.push(8);
        System.out.println(myStack.peek());//8
        System.out.println(myStack.size());//8
        for (int i = 0; i < 8; i++) {
            System.out.println(myStack.pop());
        }
    }
}

队列（Queue）

队列是先进先出（FIFO，First In First Out）的线性表。用数组实现的叫顺序队列；用链表实现的叫链式队列。队列的操作方式和堆栈类似，唯一的区别在于队列只在后端插入。
队列只允许在末端（rear）进行插入操作，也就是入队（enqueue），在前端（front）进行删除操作也就是出队（dequeue）

1
2
3
假设队列有n个元素
访问：O（n）    
插入删除：O（1） 后端插入，前端删除

单队列

常见的队列，每次添加元素时都是添加到队尾，单队列又分为顺序队列（数组实现）和链式队列（链表实现）
顺序队列存在 假溢出 的问题，也是明明有位置却不能添加的情况

假如一个顺序队列中，将前两个元素1、2出队，并入队7、8。当进行入队、出队操作时，front和rear都会持续往后移动，当rear移动到最后位置时，就无法再往队列中添加数据，
即使数组中还有空间，这种现象就是“假溢出”。

循环队列

循环队列可以解决顺序队列的假溢出和越界问题。形成头尾相接的循环

常见场景

  • 阻塞队列：当队列为空时，出队操作阻塞；当队列满的时候，入队操作阻塞。相当于在队列基础上多了阻塞操作。生产者-消费者模型
  • 线程池请求队列：线程池满的时候将放入请求队列中，当有空闲线程时，会循环反复从队列中获取任务执行。队列分为无界队列(基于链表)和有界队列(基于数组)。
    • 无界队列：可以一直入队，除非资源耗尽，比如FixedThreadPool使用无界队列LinkedBlockingQueue
    • 有界队列：当队列满的时候，会拒绝抛出java.util.concurrent.RejectedExecutionException异常
  • 消息队列
  • 播放列表

堆

堆是一种树结构，堆中每个节点都大于等于（或小于等于）子树所有节点的值。或者说：任意节点的值都（大于等于）/（小于等于）所有子节点的值。

二叉堆是一个数组，他可以被看成一个近似的完全二叉树

堆的分类-区别与节点排序方式

  • 最大堆：堆中的每一个节点的值都大于等于所有子节点的值
  • 最小堆：堆中的每一个节点的值都小于等于所有子节点的值

堆的用途

当我们只关系所有数据中的最大值或者最小值，存在多次获取最大值或者最小值、多次插入和删除时，可以使用堆
使用有序数组也可以实现，但是初始化一个有效数组的时间复杂度是O(nlog(n))、查找最大值或最小值的时间复杂度都是O(1)，但是插入和删除是O(n)
相对于有序数组，堆的主要优势在于更新数据的效率高，堆的初始化复杂度O(nlog(n)) 。取出最大值或最小值为O(1)，插入删除为O(log(n))

堆的插入

  • 最大堆插入：先将插入的元素放到最后面；从底向上，如果父节点比该元素小，则与父节点交换，直到无法交换
  • 最小堆插入：先将插入的元素放到最后面；从底向上，如果父节点比该元素大，则与父节点交换，直到无法交换
    根据堆的性质，最大堆的堆顶元素是所有元素中最大的；最小堆的堆顶元素是所有元素中最小的。
    当我们需要多次查找最大元素或最小元素时，利用堆来实现

堆的删除

删除堆顶元素之后，为了保持堆的性质，需要对堆进行调整，这个过程称之为堆化。堆化的方式有两种：

  • 一种是自底向上堆化，元素从最底部向上移动：会出现气泡
  • 一种是自顶向下堆化，元素由最顶部向下移动：

堆的操作总结

  • 插入元素：先将元素放到数组的末端，再自底向上堆化，把末端元素上浮
  • 删除堆顶元素：将末尾元素放置堆顶，再自顶向下堆化，把堆顶元素下沉。也可以自底向上堆化，但是会产生气泡，浪费空间

堆的排序

堆的排序分为两个步骤：

  1. 第一步是建堆，将一个无序数组建立成一个堆
  2. 第二步是排序，将堆顶的元素取出，然后对剩下的元素进行堆化，反复迭代，直到所有元素被取出为止

建堆

建堆的过程就是一个对所有非叶子节点进行自顶向下堆化的过程
首先要了解哪些是非叶子节点：最后一个节点的父节点及它之前的节点都是非叶子节点。也就是说，如果节点数为N。那么我们需要对N/2 到 1的节点进行堆化

排序

由于堆顶元素是最大元素，所以我们重复取出堆顶元素，将这个最大的堆顶元素放到数组末尾，并对剩下的元素进行堆化即可。

问题点
1.取出的元素存在哪里，新建一个数组还是？
2.删除堆顶元素后，堆化是自底向上，还是自顶向下
执行自顶向下堆化，这个堆化一开始要将末尾的元素移至堆顶，由于堆中元素已经减少，这个位置不会再被使用，所以我们可以将取出的元素放在末尾。

–

原文地址

–