读书笔记之《程序员代码面试指南(栈和队列)》 有getMin功能的栈 由两个栈组成的队列 用栈解决汉诺塔问题

第一章、栈和队列

使用两个栈,一个用来保存当前栈中的元素,记为stackData,一个用来保存每一步的最小值,即为stackMin.

public class MyStack {
    public static void main (String [] args){
        int [] Arr = {1,2,3};
        push(Arr[0]);
        push(Arr[1]);
        System.out.println(pop()+"  " + getMin());
    }
    private static Stack<Integer > stackData=new Stack<Integer>();
    private static Stack <Integer> stackMin =new Stack<Integer>();

    public static void push(int newNum){
        stackData.push(newNum);
        if(stackMin.isEmpty()){
            stackMin.push(newNum);
        }else if(newNum<stackMin.peek()){
            stackMin.push(newNum);
        }
    }

    public static int  pop(){
        if(stackData.peek()==stackMin.peek()){
            stackMin.pop();
        }
        return stackData.pop();
    }

    public static int getMin(){
        if(stackMin.isEmpty()){
            throw new RuntimeException("you stack is empty.");
        }
        return stackMin.peek();
    }
}

由两个栈组成的队列

  • 一个栈stackPush专门用来存数据
  • 一个栈stackPop专门用来取数据
  • 每次取数据前stackPop必须清空
  • 每次stackPush压入数据到stackPop中时,必须一次性全部压入
public class MyStack {
    private static Stack<Integer > stackPush =new Stack<Integer>();
    private static Stack <Integer> stackPop  =new Stack<Integer>();

    public static void  add(int pushInt){
        stackPush.push(pushInt);
    }

    public static int poll(){
        if(stackPush.isEmpty()&&stackPop.isEmpty()){
            throw new RuntimeException("Queue is Empty !");
        }else if(stackPop.isEmpty()){
            while (!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.pop();
    }

    public static int peek(){
        if(stackPush.isEmpty()&&stackPop.isEmpty()){
            throw new RuntimeException("Queue is Empty !");
        }else if(stackPop.isEmpty()){
            while (!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.peek();
    }
}

用栈解决汉诺塔问题

修改后的汉诺塔问题不能从左直接到右,也不能从右直接到左,必须通过中间;

左、中、右三个地点依次记为LS,LM,RS;

则仅有四个动作:LS-->LM 、LM-->LS 、LM-->RS 、RS-->LM

动作:某一个栈(from)把栈顶元素弹出 ,然后压入到另一个栈里(to),作为这一个栈(to)的栈顶。

两个原则:

  • 一个动作能发生的先决条件是不违反小压大的原则。
  • 还一个是相邻不可逆原则。

意思是,L->M ,那么M->L,就重复了,如果要最小步法完成,必须不走重复步。

核心

  • 游戏的第一个动作一定是L->M
  • 在走出任何最小步数过程中,四个动作,只有一个动作不违反原则,其余三个一定会违反。
public class MyStack {
    public enum Action {
        No , LToM , MToL , MToR , RToM
    }

    public static  int hannoProblem(int num , String left , String mid ,String right){
        Stack<Integer > ls =new Stack<Integer>();
        Stack <Integer> ms  =new Stack<Integer>();
        Stack <Integer> rs  =new Stack<Integer>();
        ls.push(Integer.MAX_VALUE);
        ms.push(Integer.MAX_VALUE);
        rs.push(Integer.MAX_VALUE);
        for( int i=num ;i>0;i--){
            ls.push(i);
        }
        Action [] record = {Action.No};
        int step = 0;
        while (rs.size()!=num+1){
            step+= fStackTotStack(record,Action.MToL,Action.LToM,ls,ms , left , mid);
            step+= fStackTotStack(record,Action.LToM,Action.MToL,ms,ls , mid , left);
            step+= fStackTotStack(record,Action.RToM,Action.MToR,ms,rs  , mid , right);
            step+= fStackTotStack(record,Action.MToR,Action.RToM,rs,ms , right, mid);
        }
        return step;
    }

    public static int fStackTotStack(Action [] record , Action preNoAct ,
                                     Action nowAct , Stack<Integer> fStack , Stack<Integer> tStack,
                                     String from , String to){
        if(record[0] != preNoAct && fStack.peek()<tStack.peek()){
            tStack.push(fStack.pop());
            System.out.println("Move"+"  "+tStack.peek()+"  "+"from" +"  "+ from +"  "+ "to" +"  "+ to);
            record[0]=nowAct;
            return 1;
        }
        return 0;
    }
  
    public static void main (String [] args){
        int num=2;
        String left="left";
        String mid ="mid";
        String right= "right";
        System.out.println(hannoProblem(num,left,mid,right));
    }
}


读书笔记之《程序员代码面试指南(栈和队列)》
有getMin功能的栈
由两个栈组成的队列
用栈解决汉诺塔问题