数组
1、数组存储的数据在地址空间上是连续的。
2、方便数据的查找，查找数据的时间复杂度为O(1）。
链表
1、链表存储的数据在地址空间上可连续，可不连续。
2、链表中的每一个节点都包括数据和指向下一个地址的指针。
3、查找数据的时间复杂度为O(n)，方便数据的增删。
在链表中查找第 n 个数据以及查找指定的数据的时间复杂度是 O(N) ，但是插入和删除数据的时间复杂度是 O(1) ，因为只需要调整指针就可以。
栈
栈是一种先入后出的逻辑结构，每次加入新的元素和拿走元素都在顶部操作。
一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。
栈的基本操作：
进栈（压栈）：push
出栈：pop
取栈顶：gettop
队列
队列是一种先入先出的逻辑结构，对元素的操作分别在对头和队尾，元素的插入在队尾，元素的删除在队头。
对队列的三个操作时间复杂度都是常量O(1)。
进队：append
出队：popleft
图片.png
二叉树
图片.png
每个节点至多只有两个子树的结构，在父节点中有指向左右子树的指针
先序遍历：根–左–右
中序遍历：左–根–右
后序遍历：左–右–根
图片.png
查找二叉树：左子树的值小于根节点的值，右子树的值大于根节点的值，在插入数据时，从根节点开始往下比较，小于比较值则放在左边，大于比较值放在右边。插入一个值的时间复杂度是O(logn)
平衡二叉树：左右子树的高度差的绝对值不超过1
完全二叉树：如果一个二叉树除倒数第一层外都被填满，并且倒数第一层从左至右填充。
满二叉树： 如果一个二叉树的任意结点或者有0或者有2个孩子。
完美树：如果一个二叉树的所有层被填满。
图片.png
堆
- 堆通常是一个可以被看做一棵树的数组对象。
- 堆是指程序运行时申请的动态内存，而栈只是指一种使用堆的方法(即先进后出)。
- 堆是由操作系统管理的一片空间,事先是没有在进程空间里分配的(比如你在没有分配堆的时候就访问堆空间会报一个内存访问错误),一般是由程序动态的分配出来,一旦分配了以后,一般需要程序去释放自己的堆空间.
堆的定义：1.是一个完全二叉树；2.上层的节点键值大于下层节点键值（最小堆），或者相反（最大堆）。
基于数组实现的堆
某节点位于完全数的i层，那么其左子节点位于数组2i位置，右子节点位于2i+1位，数组第一个位置未使用。
图片.png
栈和堆
-
（1）与堆相比，栈不会导致内存碎片，分配效率高。
所以栈在程序中是应用最广泛的，就算是函数的调用也利用栈去完成，函数调用过程中的参数，返回地址， EBP和局部变量都采用栈的方式存放。如果少量数据需要频繁的操作，那么在程序中动态申请少量栈内存（例如使用alloca函数），会获得很好的性能提升。 -
（2）堆可以申请的内存大很多。
与堆相比，栈的使用不是那么灵活，如果分配大量的内存空间，推荐使用堆内存。 -
(3) 堆是可以动态地扩展和搜索的内存空间，不是连续的内存空间。
栈的地址是从大到小的连续内存空间 -
(4) 堆中存的是对象。栈中存的是基本数据类型和堆中对象的引用。
在执行函数时，函数内局部变量的存储单元都在栈上创建，全局变量存在于（静态区 ）中，动态申请数据( 存放由new创建的对象的存储空间)存在于（ 堆）中；
网友评论