栈与递归
2018-12-03 本文已影响0人
仲达_dc6c
概念:
限定只能在表尾部插入和删除的线性表，允许插入和删除的一端称作栈顶top，另一端称作栈底bottom，没有元素的栈，是空栈。也是先进后出的线性表。
实现方式：
顺序实现，通过数组来实现。
java 中JDK有一个Stack.java 就是栈，继承了Vector，Vector继承了List，看来Stack也是一个链表，只不过控制了插入和删除只能在一端而已。
java中Vector和ArrayList的区别：
Vector是JDK1.0就有的，增加了很多多线程的控制，是线程安全的，在JDK1.0版本考虑的非常全面，但是在实际的应用中发现其实并不用考虑线程安全的事情，所以在JDK2.0之后就将Vector改成了ArrayList，去掉了线程安全控制，就是去掉了Synchronize关键字，性能比Vector要好。
链表实现:
通过单链表实现即可，控制push和pop都是通过head节点来做。
逆波兰表达式：
1.a>>1
2.a/2
上面的两个表达式中语句1的执行效率高，为什么?
语句1只需要1条指令。
语句2需要至少六条指令：
1）将中缀表达书转化成后缀表达式，需要至少5条指令。
a打印，/入栈,2打印，/打印，再计算a/2.
递归：
函数自己调用自己的编程技巧。
作为一种常用的编程算法，直接或者间接调用自己。
一般来说，递归具有边界条件，前进段和返回段。不满足边界条件，递归前进，满足边界条件，递归返回。
调用自己一次的情况：
常见例子，计算非负数n的阶层。调用自己前是正循环，调用自己后是反循环(调用自己后的代码是压栈处理的）
调用自己两次的情况：
