栈

后进先出者，先进后出者，就是栈，操作受限的线性表结构 当某种数据只涉及一段插入和删除的时候，并且满足先进后出，后进先出的特性，我们就应该使用栈。

链式栈

用链表实现的栈

顺序栈

用数组实现的栈

栈在函数中的调用关系

函数调用栈 操作系统给每个线程分配一块内存空间，这个内存空间被组织成栈结构，用来存储函数调用的临时变量，每调用一个函数，都会讲临时变量坐位栈帧入栈，等函数执行完成，返回后，将这个函数对应的临时变量出栈

栈在表达式求值中的应用

编译器通过两个栈实现表达式求值的过程 保存操作数的栈 保存运算符的栈 从左至右开始遍历表达式，当表达式是数字的时候，放入操作数的栈中，当表达式是运算符的时候，就与运算符栈顶的做比较。 如果比栈顶的运算符优先级高，就将当前运算符压入栈， 如果比栈顶运算符元素优先级低或者相同，就从操作数栈中取两个元素，从运算符栈中取出运算符，然后进行运算，把结果入操作数栈中， 继续比较

队列

先进者先出，这就是队列,操作受限的线性表结构 支持的操作：

• 入队 enqueue() 放一个数据到队列尾部
• 出队 dequeue() 从队列头部取一个数据

用数组实现的是顺序队列，用链表实现的是链式队列 需要两个指针，一个指针指向队列头，一个指向队列尾部，

顺序队列

数组删除操作 有界队列，对相应时间敏感的系统来说，就相对更加合理，但是设置一个合理的队列大小，也是非常有讲究的，队列太大，导致等待请求过多，队列太小，导致无法充分利用系统资源，发挥最大性能。

链式队列

需要两个指针，头指针 head ,和尾指针tail head 指向链表的第一个节点，尾指针指向链表的最后一个节点 可以实现一个支持无线排队的误解队列，但是可能因为导致过多的请求等待，导致处理请求的时间过长，

循环队列

也是需要两个指针，头指针 head ,和尾指针tail 关键一点： 确定队列为空和队列已满的情况 队列为空 还是 head==tail 队列已满 （tail+1）%n==head 会浪费一个存储空间 应用场景 高性能的队列 Disruptr , Linux 环形缓存，

阻塞队列

队列基础上添加了阻塞条件，简单来说就是 如果队列为 null 的时候，取数据会被阻塞，直到有数据才会返回， 如果队列已满，再往队列里面添加数据，也会被阻塞，直到有空间才会添加进去。 这就是生产者消费者模型。

并发队列

线程安全的队列， 简单的实现就是在 enqueue() 和 dequeue() 上添加锁 但是锁粒度太大，并发度较低，同一个时刻只允许一个存或者取操作。 基于数组的队列可以通过 CAS 原子操作。实现非常高效的并发队列。 java concurrent 并发包 利用的是 ArrayBlockQueue 来实现公平锁

总结

适用于任何资源有限资源池中。 用于排队请求，比如数据库连接池， 实际上，大部分资源有限的场景， 当没有空闲资源的时候， 基本上都可以通过队列这种数据结构来实现排队请求。

递归

一种应用非常广泛的算法（或者编程技巧） DFS 深度优先搜索，前中后序二叉树算法， 去的过程叫”递”，回来的过程叫”归” 基本上，所有的递归的问题都可以用递推公式来表示。

需要满足的三个条件

• 一个问题可以分解几个子问题的解
• 这个问题分解后的子问题，除了数据规模不同，求解思路完全一样
• 存在递归终止条件

如何编写递归

关键： 写出递归公式，找到终止条件。 写递归代码，关键就是找打把大问题化解为小问题的的规律，并且基于此写出递推公式，然后在推敲出终止条件，最后将递推公式和终止条件翻译成代码

理解递归，只需要考虑问题和子问题之间的 关系即可，不需要层层考虑就行。屏蔽掉递归细节就可以了。

递归警惕堆

• 栈溢出的问题。
• 重复计算 可以通过一个数据结构，例如 hash 表保存已经计算过的数据，当递归到f(k)的时候，先查询是否已经计算过了，如果已经计算过了，就直接从散列表中取值，否则计算结果，然后再保存到散列表中。

  递归的利弊

• 利 表达能力强，写起来简单，
• 弊 空间复杂度高，有堆栈溢出的风险，存在重复计算，过多函数调用会耗时的问题。

思考题

如果 A 的推荐人是 B ， B 的推荐人是 C ， C 的推荐人是 A ，如何检测这种死循环存在的