前言：数据结构学习第二波笔记来袭！
数组
数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为O(n)。插入删除时间复杂度是O(n)、查询时间复杂度是O(1)
链表
三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。
链表组成：结点、后继指针
单链表：插入删除时间复杂度是O(1)、查询时间复杂度是O(n)。第一个结点叫作头结点，把最后一个结点叫作尾结点。头结点用来记录链表的基地址，可以根据它遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
循环链表：一种特殊的单链表。循环链表的尾结点指针是指向链表的头结点。
双向链表：它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。Java中的LinkedHashMap的实现原理，就用到了双向链表这种数据结构。
双向循环链表：循环链表和双向链表的组合体。
链表应用：可用于实现LRU缓存淘汰算法
写出正确的链表代码的技巧
理解指针或引用的含义；
警惕指针丢失和内存泄漏；
利用哨兵简化实现难度；
解说：表示一个空链表方法：head=null 表示链表中没有结点了。head 表示头结点指针，指向链表中的第一个结点。引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。
重点留意边界条件处理；
画图辅助思考
5 个常见的链表操作：单链表反转、链表中环的检测、两个有序的链表合并、删除链表倒数第n个结点、求链表的中间结点
栈
栈概念：后进者先出，先进者后出，这就是典型的“栈”结构。
栈实现：栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。需要一个栈顶指针。
栈的时间复杂度和空间复杂度均为O（1）
支持动态扩容的顺序栈
栈在函数调用中的应用：操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
栈在表达式求值中的应用
栈在括号匹配中的应用：我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。
栈可实现浏览器的前进和后退功能
队列
队列概念：先进者先出，这就是典型的“队列”。
队列操作：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
队列实现：用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
基于数组的队列实现方法：队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。
带来的问题：随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。解决办法是只需要在入队时，再集中触发一次数据的搬移操作。
基于链表的队列实现方法：同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。
循环队列：避免了数据搬移，但一定确定好队空和队满的判定条件。
阻塞队列：就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
并发队列：最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
递归
递归满足的三个条件：
一个问题的解可以分解为几个子问题的解；这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样；存在递归终止条件。
递归代码实现总结：写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
递归代码注意事项：
递归代码要警惕堆栈溢出；递归代码要警惕重复计算
将递归代码改写为非递归代码：可以尝试改为这种迭代循环的非递归写法
递归可以解决“最终推荐人”类似的问题
若有收获，就点个赞吧
0 人点赞
