求高手指教
栈的push、pop序列。具体描述，输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
代码如何实现？
------解决方案--------------------------------------------------------
入栈：1 2 3 4 5
可能出栈：
5 4 3 2 1
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
3 5 4 2 1
3 4 5 2 1
3 4 2 5 1
3 4 2 1 5
3 2 5 4 1
3 2 4 5 1
3 2 4 1 5
3 2 1 5 4
3 2 1 4 5
2 5 4 3 1
2 4 5 3 1
2 4 3 5 1
2 4 3 1 5
2 3 5 4 1
2 3 4 5 1
2 3 4 1 5
2 3 1 5 4
2 3 1 4 5
2 1 5 4 3
2 1 4 5 3
2 1 4 3 5
2 1 3 5 4
2 1 3 4 5
1 5 4 3 2
1 4 5 3 2
1 4 3 5 2
1 4 3 2 5
1 3 5 4 2
1 3 4 5 2
1 3 4 2 5
1 3 2 5 4
1 3 2 4 5
1 2 5 4 3
1 2 4 5 3
1 2 4 3 5
1 2 3 5 4
1 2 3 4 5
附相关算法:
- Java code
import java.util.LinkedList;import java.util.Stack;public class TestIO { /** * 穷举每一种可能的出栈序列 * @param inQueue * @param stack * @param outQueue */ public static void getStackSequence(LinkedList<String> inQueue,Stack<String> stack,LinkedList<String> outQueue){ if(inQueue.isEmpty()&&stack.isEmpty()){ //输出可能的出栈序列 while(!outQueue.isEmpty()){ System.out.print(outQueue.poll()+" "); } System.out.println(); }else if(!inQueue.isEmpty()&&!stack.isEmpty()){ //保存现场 LinkedList<String> tempInQueue=new LinkedList<String>(inQueue); LinkedList<String> tempOutQueue=new LinkedList<String>(outQueue); Stack<String> tempStack=new Stack<String>(); for(int i=0;i<stack.size();i++) tempStack.push(stack.get(i)); //队首元素入栈 stack.push(inQueue.poll()); getStackSequence(inQueue, stack, outQueue); //还原现场 inQueue=tempInQueue; outQueue=tempOutQueue; stack=tempStack; //栈顶元素出栈 outQueue.offer(stack.pop()); getStackSequence(inQueue, stack, outQueue); }else if(!inQueue.isEmpty()&&stack.isEmpty()){ //队首元素入栈 stack.push(inQueue.poll()); getStackSequence(inQueue, stack, outQueue); }else if(inQueue.isEmpty()&&!stack.isEmpty()){ //栈顶元素出栈 outQueue.offer(stack.pop()); getStackSequence(inQueue, stack, outQueue); }else{ } } /** * 封装输出，获得内部算法所需要的接口 * @param in * @param out */ private static void init(String[] in){ Stack<String> stack=new Stack<String>(); LinkedList<String> outQueue=new LinkedList<String>(); LinkedList<String> inQueue=new LinkedList<String>(); for(int i=0;i<in.length;i++) inQueue.add(in[i]); getStackSequence(inQueue, stack, outQueue); } public static void main(String[] args){ String[] in={"1","2","3","4","5"}; //入栈顺序 init(in); }}