1、数组
数组：是指相同元素按照一定顺序排列的集合
优点：
1、构建一个数组很简单
2、能够在O(1)的时间内根据数组的小标查询某个元素
缺点：
1、构建时必须分配一段连续的时间
2、查询某个元素是否存在时需要遍历整个数组，需要花费O(n)的时间内
3、删除或者添加某个元素时，同样需要耗费O(n)的时间
2.链表
链表的出现在某种程度上是为了避免数组的一大缺陷，即分配数组的时候需要开辟一段连续的内存空间，但鱼和熊掌不可兼得，链表也牺牲了数组的一些优点，链表不能通过下标进行快速查询。所以在考虑是否需要运用链表的时候，务必搞懂所用算法是否需要经常进行查询和遍历。
优点：
1、链表能灵活地分配内存空间
2、能在O(1)时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在O(1)时间内删除或者添加该元素 。
缺点：
1、查询第k个元素需要O(k)时间
很显然，如果要解决的问题里面需要很多快速的查询，链表可能并不适合。一般而言，如果数据的元素个数不确定，而且需要经常进行数据的添加和删除，那么链表会比较合适，而如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合。
栈
1.栈的特点
栈的特点就是后进先出（LIFO），对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以查看栈顶部的数据，只能够向栈的顶部压⼊入数据，也只能从栈的顶部弹出数据。
因此，可以利用一个单链表来实现栈的数据结构，而且，因为只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在O(1)的时间内完成。虽然可以用一个数组外加一个指针也能实现相似的效果，但是，一旦数组的长度发生了改变，哪怕只是在最后添加一个新的元素，时间复杂度不再是O(1)，而且，空间复杂度也得不到优化。
2.什么时候需要用到栈呢？
围绕栈的算法面试题很多，基本的核心思想就是：当解决某个问题的时候，只关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。
例如，给出了一串由左括号和右括号组成的字符串，需要判断这些括号的组成是否合法。方法就是可以利用一个栈，不断地往里压左括号，一旦遇上了一个右括号，就把栈顶的左括号弹出来，表示这是一个合法的组合，以此类推，直到最后判断栈里还有没有左括号剩余。
队列
队列的最大特点是先进先出，就好像按顺序排队一样。
对于队列的数据来说，只允许在队尾查看和添加数据，在队头查看和删除数据
2.如何实现一个队列
可以借助双链表实现队列，双链表的头指针允许在队头查看和删除数据，而双链表的尾指针允许在队尾查看和添加数据。
当需要按照一定的顺序来处理数据，而要处理的数据量在不断地变化的时候，就需要使用队列。
在算法面试题当中，广度优先搜索（Breadth-First Search）是运用队列最多的地方。
双端队列
双端队列和普通队列最大的不同在于，它允许在队列的头尾两端都能在O(1)的时间内进行数据的查看，添加和删除
与队列相似，可以利用一个双链表来实现双端队列
双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。
树
树的结构十分直观，而树的很多概念定义都有一个相同的特点：递归，也就是说，一棵树要满足某种性质，往往要求每个节点都必须满足。例如，在定义一棵二叉搜索树时，每个节点也都必须是一棵二叉搜索树。
网友评论