栈相关的算法题

1.用递归逆序一个栈
一个栈进入顺序为1,2,3,4，则从栈顶往下看是4,3,2,1
希望从栈顶往下看也是1,2，3,4如何用递归实现。

参考大神的思路：
用两个递归函数
第一个函数返回栈底元素并移出
第二个递归函数逆序。

public static int getAndRemoveLastElement(Stack<Integer> stack) {
	int result = stack.pop();
	if(stack.isEmpty()) {//栈空返回栈底元素
		return result;
	}else {
		int last = getAndRemoveLastElement(stack);//得到栈底元素
		stack.push(result);//将除了栈底元素以外的元素重新压入栈
		return last;//返回栈底元素
	}
}
	
public static void reverse(Stack<Integer> stack) {
	if(stack.isEmpty()) {//栈空的时候，返回
		return ;
	}
	int i = getAndRemoveLastElement(stack);//得到栈底元素
	reverse(stack);//递归从下往上得到栈中元素
	stack.push(i);//递归返回的时候，从栈底依次往上压入元素
}

2.利用栈实现另一个栈元素排序，只能用一个辅助栈，不能用别的数据结构，可以利用辅助边量。
例如：一个栈从栈顶到栈底为 2 3 6 5 1 4
最后要排序为：6 5 4 3 2 1

思路：用一个辅助栈，依次从原栈中取出一个元素，如果比辅助栈顶元素小，直接放。
如果比辅助栈顶元素大，则把辅助栈所有元素都放回原栈，再把原栈当前元素放入辅助栈。

public static void sortStack(Stack<Integer> stack){
	    Stack<Integer> help = new Stack<Integer>();
	    while(stack.isEmpty()) {
	    	int cur = stack.pop();
	    	while(!help.isEmpty()&&cur>help.peek()) {
	    		stack.push(help.pop());
	    		
	    	}
	    	help.push(cur);
	    }

        while(!help.isEmpty()) {
        	stack.push(help.pop());
        }
	}

3.汉诺塔问题
添加一个限制条件：不能直接从最左侧到最右侧
非递归用栈实现
思路：1.小压大原则
2.相邻不可逆原则
解释如下：
L->M M->L 与M->R R->M为相邻逆过程，重复没有意义，不会得到最小步数。

public class Main {
    
      public static void main(String[] args) {
           hanoiProblem(3,"左","中","右");
      }
      public enum Action{
    	 No,LToM,MToL,MToR,RToM 
      }
      public static int hanoiProblem(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+=fStackToStack(record,Action.MToL,Action.LToM,ls,ms,left,mid);
    		  step+=fStackToStack(record,Action.LToM,Action.MToL,ms,ls,mid,left);
    		  step+=fStackToStack(record,Action.RToM,Action.MToR,ms,rs,mid,right);
    		  step+=fStackToStack(record,Action.MToR,Action.RToM,rs,ms,right,mid);
    	  }
    	  return step;
      }
      public static int fStackToStack(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("Mode"+tStack.peek()+"from"+from+"to"+to);
    		  record[0] = nowAct;
    		  return 1;
    	  }
    	  return 0;
      }
}

运行结果：

Move1from左to中
Move1from中to右
Move2from左to中
Move1from右to中
Move1from中to左
Move2from中to右
Move1from左to中
Move1from中to右
Move3from左to中
Move1from右to中
Move1from中to左
Move2from右to中
Move1from左to中
Move1from中to右
Move2from中to左
Move1from右to中
Move1from中to左
Move3from中to右
Move1from左to中
Move1from中to右
Move2from左to中
Move1from右to中
Move1from中to左
Move2from中to右
Move1from左to中
Move1from中to右