学习算法第二天：栈队列和并查集、哈希表
栈和队列
•定义：存放数据的线性表
•操作：入栈/队列、出栈/队列、判断满/空
•空间复杂度：O(n)
•单次操作时间复杂度：O(1)
•区别 先进后出（FILO, First In Last Out） 先进先出（FIFO, First In First Out）
栈和队列的实现方式：数组和链表皆可（线性表）
•指针（辅助变量）栈顶/底指针 队头/尾指针
•关键：出入元素的同时移动指针
三、栈的应用
括号匹配：
•括号、引号等符号是成对出现的，必须相互匹配
•设计一个算法，自动检测输入的字符串中的括号是否匹配
•比如：{}[([][])] 匹配 [(])不匹配 (()]不匹配
从左向右扫描字符串
当前是[，期待一个]
当前是(，和刚才的[不匹配，说明相匹配的符号还在右边，继续扫描
当前是[，和刚才的(不匹配，说明相匹配的符号还在右边，继续扫描
当前是]，和刚才的[正好一对，可以从字符串中“删去”不考虑了
当前是[，目前最近的一个是(，不匹配，继续扫描
当前是]，和刚才的[正好一对，可以从字符串中“删去”不考虑了
当前是)，目前最近的一个是(，正好一对，可以从字符串中“删去”不考虑了
当前是]，目前最近的一个是[，正好一对，可以从字符串中“删去”不考虑了，此时左右的括号都匹配成功
总结：从上述过程看，由于括号很多，并不知道最后的括号是什么，所以采用流处理方式，先进来的括号反而是最后删除的，所以是先进后出，所以要用栈实现，如下：
依次类推，直至栈为空；
应用2：四则运算，加减乘除等,平常四则运算如：4*(5-2)+8属于中缀表达式 需要解析为后缀表达式：452-*8+；其中需要两个栈：数字栈和运算符栈。中缀表达式“9+（3-1）*3+10/2”转化为后缀表达式为“9 3 1- 3 * + 10 2 / +”.
1,数字直接入栈
2，如果是（因为还没匹配到括号所以直接入栈
3，如果是符合就和栈顶元素比，如果小于等于符合栈栈顶元素，则符号栈顶元素出栈压入数字栈，直到符合栈顶元素<当前符合优先级为止。
4，如果是)则直接出栈，直至出栈元素为匹配的括号为止。
人工栈模拟系统栈
因为系统栈可能内存溢出。递归隐式的栈调用，无出栈入栈操作，转为显示的栈调用。
1，递归是两步，一是调用跳转，二是返回back，需要明确
2，空间提前开辟，一个是当前值一个是返回值
如下求n！弄清楚边界条件，跳转做什么，返回做什么就好。
里层if语句：当n<=1时，返回值是1，开始往回返回。
外层if语句：往回走发生的事情是，f(n-1)算完了，所以是出栈*f(n-1)；
继续往里走的事情是n进栈，然后跳转n-1；
结论：附加了进栈和出栈操作；以及是跳转还是返回的判断；外加栈为空的循环。
递归很多，全排列，求组合，并把排列和组合结果输出，8皇后，汉诺塔