学校里我们可能都学过数据结构，面试上数据结构和算法已然是必修课了，看了极客的数据结构，当然要比《算法导论》简单易懂。画个笔记，把数据结构和算法基础知识提炼总结一下。有个概念的认识多是有益的。也推荐大家去学习阅读下极客的数据结构与算法的文稿。

数据结构概念

数据结构就是指一组数据的存储结构。它是组织数据的一种方式。

常见的数据结构

• 数组 (Array)
• 链表 (Linked List)
• 栈 (Stack)
• 队列 (Queue)
• 跳表 (Skip list)
• 散列表 (Hash)
• 树 (Tree)
• 堆 (Heap)
• 图 (Graph)

数组 (Array)

数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，查询效率高，但插入、删除操作也因此变得比较低效。

数组的增删改查类似于现实生活中的插队，一列排好的队伍，突然有一个人进来势必会影响之后的人的队。

//数据机构-最基础
 int[] a={2,0,2,1};

链表 (Linked List)

链表并不需要一块连续的内存空间，它通过 “指针” 将一组零散的内存块串联起来使用。

和数组相比，链表更适合插入、删除操作频繁的场景。

//链表结构
public class LinkNode{
    //数据
    int data;
    //下一个节点
    LinkNode next;
    //上一个节点
    LinkNode before;
    public LinkNode(){
    }
    public LinkNode(int data){
        this.data=data;
    }
}

栈 (Stack)

后进者先出，先进者后出，这就是典型的 “栈” 结构。栈是一种 “操作受限” 的线性表，只允许在一端插入和删除数据。


从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选 “栈” 这种数据结构。

用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

//基于数组的顺序栈结构
public class ArrayStack {
    private String[] items;  // 数组
    private int count;       // 栈中元素个数
    private int n;           //栈的大小

    // 初始化数组，申请一个大小为n的数组空间
    public ArrayStack(int n) {
        this.items = new String[n];
        this.n = n;
        this.count = 0;
    }
}    

队列 (Queue)

先进者先出，这就是典型的 “队列”。队列跟栈一样，也是一种操作受限的线性表数据结构。

使用广泛：循环队列、阻塞队列、并发队列、Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁。
用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

 //基于数组的顺序队列结构
public class ArrayQueue {
    // 数组：items，数组大小：n
    private String[] items;
    private int n = 0;
    // head表示队头下标，tail表示队尾下标
    private int head = 0;
    private int tail = 0;

    // 申请一个大小为capacity的数组
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }
}

跳表 (Skip list)

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低。

链表加多级索引的结构，就是跳表。跳表可以减少查询次数的，提高查询效率。

建立跳表数据结构后，查找某个结点，先通过遍历索引层一级级缩小目标访问，再对原始链表进行遍历，遍历的节点减少了，效率自然提升了。

结构定义与链表结构一致。
因为跳表本就是从链表中抽取出来的节点数据组成了索引链表。

下次再总结散列表 (Hash)、树 (Tree)、堆 (Heap)、
图 (Graph) 的基础知识

扫一扫，关注我