数据结构二：两个栈描述队列 跳台阶

//用两个栈实现队列 //用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

//思路 // 进栈： // 直接进stack1 // 出栈： // 若stack2不为空，则出栈。 //
否则，当stack1不为空时，将stack1中的元素依次出栈并压人stack2中。最后，弹出stack2的栈顶元素。

package nowcoder.offer.cn;

import java.util.Stack;

/**
 * @author xumaosheng
 * @date 2019/9/9 19:25
 */
public class _05TwoStacksRealizeQueues {
	public static void main(String[] args) {
		Solution solution = new _05TwoStacksRealizeQueues().new Solution();
		solution.push(1);
		solution.push(2);
		solution.push(3);
		solution.push(4);
		solution.push(5);
		solution.push(6);
		while (!solution.stack2.empty() || !solution.stack1.empty()) {
			System.out.println(solution.pop());
		}
	}

	public class Solution {
		Stack<Integer> stack1 = new Stack<Integer>();
		Stack<Integer> stack2 = new Stack<Integer>();

		public void push(int node) {
			stack1.push(node);
		}

		public int pop() {
			if (!stack2.empty()) {
				return stack2.pop();
			} else {
				while (!stack1.empty()) {
					stack2.push(stack1.pop());
				}
				return stack2.pop();
			}
		}
	}
}

//跳台阶 //一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

//思路 // 暴力枚举（自顶向下递归）： // 若台阶数小于等于0，返回0； // 若台阶数为1，返回1；(1) //
若台阶数为2，返回2；(1,1),(2) // 否则，返回F(n-1)+F(n-2);（因为下一步只能是跳1级或者跳2级） //
// 备忘录算法（自顶向下递归）： // 上面的方法包含大量重复计算，这里利用Map来记录计算过的结果，以减少计算次数。 // //
迭代法(自底向上迭代，也许也算动态规划吧): // 拿两个变量记录前两个结果和一个临时变量保存当前计算结果（也可不用改临时变量）

package nowcoder.offer.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author xumaosheng
 * @date 2019/9/9 19:36
 */
public class _08JumpSteps {
	public static void main(String[] args) {
		Solution1 solution1 = new _08JumpSteps().new Solution1();
		int step = solution1.JumpFloor(5);
		System.out.println(step);

	}

	public class Solution1 {
		public int JumpFloor(int target) {
			if (target <= 0) {
				return 0;
			} else if (target == 1 || target == 2) {
				return target;
			} else {
				return JumpFloor(target - 1) + JumpFloor(target - 2);
			}
		}
	}

	public class Solution2 {
		public int JumpFloor(int target) {
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			return JumpFloor(target, map);
		}

		public int JumpFloor(int n, Map<Integer, Integer> map) {
			if (n <= 0) {
				return 0;
			} else if (n <= 2) {
				return n;
			}
			if (map.containsKey(n)) {
				return map.get(n);
			} else {
				int value = JumpFloor(n - 1, map) + JumpFloor(n - 2, map);
				map.put(n, value);
				return value;
			}
		}
	}

	public class Solution3 {
		public int JumpFloor(int target) {
			if (target <= 0) {
				return 0;
			} else if (target == 1 || target == 2) {
				return target;
			}
			int temp = 0, pre = 1, last = 2;
			for (int i = 3; i <= target; i++) {
				temp = pre + last;
				pre = last;
				last = temp;
			}
			return last;
		}
	}
}