本文共 1991 字，大约阅读时间需要 6 分钟。
只允许在一端操作，且满足先进后出，后进先出的特性，底层可以使用数组，或者链表实现；
计算空间复杂度，是指除了原本的数据存储空间外，算法运行需要的额外存储空间；
数组实现的固定大小栈 入栈和出栈的时间复杂度都是 O(1)，空间复杂度也是 O(1) 数组实现的变长大小的栈 入栈的平均时间复杂度也是 O(1)
只允许一端插入，另一端取出，有先进先出特性的数据结构，底层用数组实现，称为顺序队列，用链表实现，称为链式队列；
使用数组实现队列时，因为双端操作，所以会有数据搬移，可以通过构造循环队列，来提高效率；
数组实现队列，入队在数组尾部，出队操作，在数组头部 循环队列，
阻塞队列，就是入队和出队操作，在队列满和队列空时会阻塞
并发队列，即多线程操作无安全问题，实现并发安全，不一定使用锁，可以通过 CAS等，实现无锁并发队列；
// 表达式求值 编译器通过两个栈来实现，一个保存操作数的栈，另一个保存运算符的栈 从左向右遍历表达式，遇到数字，压入操作数栈 遇到运算符，先与运算符栈的栈顶元素比较，如果比栈顶运算符的优先级高，压入栈 如果比栈顶运算符的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，进行计算，把计算的 结果压入操作数栈； 继续遍历比较...
分为前进栈和后退栈，如果顺序查看了a,b,c页面，就依次放入后退栈中，这样就可以通过后退栈，依次退回到 b，a 页面 并且，每次后退，后退栈弹出出栈元素后，需要将其压入前进栈中，如，从 c 页面退回 a 页面，那么前进栈，就会压入 c b, 这样通过前进，就可以查看 b c 页面
如果，每次出队操作，都搬移数据，太耗时，可以在入队操作，当没有新空间时，才尝试搬移数据 通过 head tail 指针指向队列头部，和尾部 入队操作，data[tail] = value; tail ++; 当tail = data.length 时，搬移数据，如果 head == 0,无法入队 出队操作：return data[head]; head --
相比于之前的队列，入队当 tail = data.length 需要搬移数据，改为 tail = data.length 时，直接 tail 从0计数 为此队列满的条件是 head 和 tail 只相差1，(tail +1) % data.length == head
通过一个成员变量，记录队列尾节点，避免每次删除，都需要遍历到尾节点
递归是一种应用非常广泛的算法；
满足的三个条件的问题，往往可以通过递归解决，重点是找到递推公式，和终止条件；
1. 一个问题，可以分解为几个子问题 2. 问题和子问题间，除了数据规模不同，求解思路完全一样 3. 存在递归终止条件
递推公式：f(n)=f(n-1)+1 终止条件：f(1)=1 编码：int f(int n) { if (n == 1) return 1; return f(n-1) + 1; } 1. 问题，可以分解为 走一阶台阶，后走六阶台阶的走法 + 走二阶台阶，后走五阶台阶的走法 2. 递推公式：f(n) = f(n-1) + f(n-2); 3. 终止条件： f(2) = 2, f(1) = 1
栈溢出：可以通过限制递归的深度，避免无限递归，和超出内存空间的递归 重复计算：可以通过散列表缓存计算过的递归值； // 台阶问题，缓存计算递归值 public int f(int n) { if (n == 1) return 1; if (n == 2) return 2; // hasSolvedList可以理解成一个Map，key是n，value是f(n) if (hasSolvedList.containsKey(n)) { return hasSolvedList.get(n); } int ret = f(n-1) + f(n-2); hasSolvedList.put(n, ret); return ret; } 转载地址：http://hsfin.baihongyu.com/