【每天一个知识点】栈，堆，队列，链表，树和图的区别

先看图，所有的数据结构大概有这么多：

其实他们都是一种存储数据的方式而已，打个比方，你坐地铁1号线上班和2号线上班，都能上班只是路线不一样，他们都是存储数据的格式，每种数据结构有自己的特点，使用哪种数据格式需要根据具体的需求来选。

比如你现在需要有序的存储一组数据而且还要经常的查询数据，那么数组就是最合适的，他有角标可以很容易进行排序和查询！数组的读取和更改数据的效率是所有数据据结构中最高的。 但他的缺点是：不适合进行大量数据的存储， 因为数组在内存中很难找到连续且大的内存空间 。 并且数组的随机删除和插入的效率低，因为数组进行任意索引的删除和插入时，索引后面的元素都会发生集体左移或右移的行为（最大索引对应的元素除外）。 最后数组的空间大小固定没办法扩容，数组的空间是提前定义好的，如果想进行数组扩容的话，只能调用 System.arraycopy(); 向定义好的大数组进行拷贝，而解决这个问题的方法就是使用链表（链表可以随意扩容）。

数组的详细可以看这篇https://blog.csdn.net/ldxnb/article/details/123121849

上面提到，数组的长度在创建时就已经确定了，而解决这个方法最好的就是使用链表。如果你的数据长度无法确定，并且有序且经常增删数据，那么链表就是最合适的，他不像数组从创建时就已经确定了长度，因此便于管理长度或数量不确定的数据，链表另一个特点就是增删快查询慢，增删是因为只需要创建一个新节点把引用地址改变就可以。查询慢则是因为没办法通过索引直接查找，需要从头遍历，每一个节点的尾部会指向下一个节点地址。另外由于用了大量的指针域，占用的空间也变会变的特别大。

这里必须强调一下：很多人会以为数组链表堆栈队列树图这些是并列关系，其实不然。 数组和链表是并列关系，堆栈队列树图这些是并列关系。 堆栈队列树图是数据的概念，他们可以用数组和链表的形式去实现。 比如队列可以用数组去做，也可以用链表去做。所以大家要理解清楚这两块的区别。

那么我们先讲栈和队列。 栈和队列是最基本的两个ADT，简单但是重要。 最简单的理解方式就是： 栈：先进后出，后进先出。 队列：先进先出，后进后出。 在使用的场景最多的地方就是框架架构的底层和算法。 例如栈最典型的应用场景就是：“面包屑工程”，使用户在浏览页面时可以轻松的回溯到上一级或上一级页面，每打开一个页面就压入栈里，回退时只需把栈顶移除就可以了。 而队列则更不必说，先进入队列的任务先执行，就跟买票一样，第一个排队的就先买。

那么堆，树和图呢？ 堆其实就是一个完全二叉树，如图就是一个堆。 他的应用场景更多的是在算法上，能做到性能高效。 100亿个数中找出最大的前k个数（海量数据topk问题） 思路分析：乍一看，100亿个数，确实很大，一个数占四个字节，那么100亿个数就需要40G的存储空间，这对与普通电脑来说确实是不可能的。但是，这道题肯定不可能让我们创建一个具有100亿个数据的堆，这样不说存储空间不够大，时间复杂度也是很大的，正确·的做法是…

https://blog.csdn.net/zb1593496558/article/details/79371735?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-1.pc_relevant_default&utm_relevant_index=2

那么树便是各种形式的树了，这个点讲多了就会很复杂，要了解清楚需要另开一篇文章。

接下来就是图，树和堆的概念都很少用到了，更别说图了。

那么图其实就是“树是有向无环的特殊的图”，大概就是这两很像，但又有不一样的地方，具体也需要单独去了解，总的来说堆树图这三个其实我们实际的开发很少使用，了解一下即可，重点还是放在上面的几个基础的点。