【栈】出栈顺序题目总结
【栈】
我们大家都不陌生的一个数据结构，先进后出。
关于栈，有很多的操作：
1.压栈，2.出栈，3.获取栈顶元素，4.判断栈是否为空，5.判断栈是否满
一、对于出栈的所有可能这个问题，大家首先想到的肯定就是递归。
本文也是采用该方法，实现出栈的所有可能的输出。
首先我们先看下代码：
package qyq.Algorithm.StackPop;import java.util.Stack;/** * 一个栈的输入序列，求出所有的出栈序列 * @author qi * @creation 2012-8-14 */public class StackPop {public static void orderStack(Stack<String> stack,String result,String input){@SuppressWarnings("unchecked")Stack<String> temp=(Stack<String>)stack.clone();String subStr=input.substring(0,1);input =input.substring(1);temp.push(subStr);if(input.length()==0){while(!temp.isEmpty()){result+=temp.pop();}System.err.println(result);}else {orderStack(temp, result, input);while(!temp.isEmpty()){result+=temp.pop();orderStack(temp, result, input);}}}public static void main(String args[]){String s="1234";Stack<String> stack =new Stack<String>();orderStack(stack, "", s);}}在这里我们使用了java的一个深拷贝，那就是clone（克隆）。在C++里面有深拷贝和浅拷贝，他们的区别：深拷贝,内容被拷贝了，而且地址也发生了变化，彼此之间不会相互影响。但是对于浅拷贝的话，主要是指向了同一块内存空间，如果一个内容发生改变，另外一个也会跟着改变！在java里面就是使用clone的方式来实现深拷贝！给定一个入栈的顺序，和一个出栈的顺序，判断该出栈顺序是否合法。
我们先来看代码：
package qyq.Algorithm.StackPop;import java.util.Stack;/** * 判断出栈的顺序是否合法 * @author qi * @creation 2012-8-14 */public class StackPopOrder {public static void main(String[] args) {String s="1234";String t="4312";boolean flag=popOrder(s, t);if(flag){System.err.println("yes");}else {System.err.println("no");}}public static boolean popOrder(String s,String t){Stack<Character> stack =new Stack<Character>();int lenS=s.length();int lenT=t.length();int i=0,j=0;while(i<lenS){if(s.charAt(i)==t.charAt(j)){i++;j++;}else if(!stack.isEmpty()&&t.charAt(j)==stack.peek()){j++;stack.pop();}else{stack.push(s.charAt(i));i++;}}while(j<lenT){char temp=t.charAt(j);char peek=stack.peek();if(temp==peek){j++;stack.pop();}else {break;}}if(stack.isEmpty()){return true;}return false;}}上面的两个while循环是关键点，分别处理不同的情况。大家思考下哈！嘿嘿