第一章 栈和队列

设计一个有getMin功能的栈
基本思路是用两个栈，同步地压入内容，但是getMin栈中需要判断是压入为当前最小，根据是否重复压入，可以确定出栈时是否需要重复判断。（空间与时间的矛盾关系）
两个栈组成的队列
栈为先进后出，队列为先进先出。需要用两个栈倒一下就可成为队列。但是需要满足两个条件：（1）如果stackpush要往stackpop中压入数据，必须一次性将stackpush中的全部数据压入；（2）如果stackpop不为空，stackpush不能向stackpop中压入数据。
**如何仅用递归函数和栈操作逆序一个栈
直接上代码：

Public static int getAndRemoveLastElemant(Stack<Integer> stack){
    int result = stack.pop();
    if(stack.isEmpty()){
        return result;
    }else{
        int last = getAndRemoveLastElement(stack);
        stack.push(result);
        return last;
    }
}

猫狗队列
用count作为时间戳，没压入队列，就在实例中的时间戳增加。
用一个栈实现另一个栈的排序
通过一个新的栈和新的变量实现对已有栈的排序。有顺序直接压入，要插入则将新栈元素弹至已有栈，至有序后重新压入。
用栈来求解Hanoi问题
题目变形为————移动只在相邻塔间发生，用栈模拟Hanoi的递归过程。
现在我们把左、中、右三个地点抽象成栈，依次记为LS、MS和 RS。最初所有入到另一个上。那么如上4个动作就可以看作是:
某一个栈（from）把栈顶元素弹出,然后压栈里（to)，作为这一个栈（to）的栈顶。
例如，如果是7层搭，在最初时所有的搭都在LS上，LS从栈顶到栈底就依次是1～7，如果现在发生了“左”到“中”的动作，这个动作对应的操作是LS栈将栈顶元素1弹出，然后1压入到 MS栈中,成为MS 的栈顶。其他操作同理。一个动作能发生的先决条件是不违反小压大的原则。栈的栈顶。
from栈弹出的元素num加果相压入到to栈中，那么num 的值必须小于当前to
还有一个原则不是很明显，但也是非常重要的，叫相邻不可逆原则，解释如下:
1．我们把4个动作依次定义为:L->M、M->L、M->R 和R->M。
2．很明显，L->M和M->过程互为逆过程，M->R和R->M互为逆过程。
3．在修改后的汉诺塔游戏中，如果想走出最少步数，那么任何两个相邻的动作
都不是互为逆过程的。举个例子:如果上一步的动作是L->M，那么这一步绝不可能是M->L，直观地解释为:你在上一步把一个栈顶数从“左”移动到“中”,这一步为什么又要移回去呢?
这必然不是取得最小步数的走法。同理，M->R动作和R->M动作也不可能相邻发生。有了小压大和相邻不可逆原则后，可以推导出两个十分有用的结论——非递归的方法核心结论:
1．游戏的第一个动作一定是L->M，这是显而易见的。
2．在走出最少步数过程中的任何时刻，4个动作中只有一个动作不违反小压大和相邻不可逆原则，另外三个动作一定都会违反。