栈的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序列。
分析：这到题除了考查对栈这一基本数据结构的理解，还能考查我们的分析能力。
这道题的一个很直观的想法就是建立一个辅助栈，每次push的时候就把一个整数push进入这个辅助栈，同样需要pop的时候就把该栈的栈顶整数pop出来。
我们以前面的序列4、5、3、2、1为例。第一个希望被pop出来的数字是4，因此4需要先push到栈里面。由于push的顺序已经由push序列确定了，也就是在把4 push进栈之前，数字1，2，3都需要push到栈里面。此时栈里的包含4个数字，分别是1，2，3，4，其中4位于栈顶。把4 pop出栈后，剩下三个数字1，2，3。接下来希望被pop的是5，由于仍然不是栈顶数字，我们接着在push序列中4以后的数字中寻找。找到数字5后再一次push进栈，这个时候5就是位于栈顶，可以被pop出来。接下来希望被pop的三个数字是3，2，1。每次操作前都位于栈顶，直接pop即可。
再来看序列4、3、5、1、2。pop数字4的情况和前面一样。把4 pop出来之后，3位于栈顶，直接pop。接下来希望pop的数字是5，由于5不是栈顶数字，我们到push序列中没有被push进栈的数字中去搜索该数字，幸运的时候能够找到5，于是把5 push进入栈。此时pop 5之后，栈内包含两个数字1、2，其中2位于栈顶。这个时候希望pop的数字是1，由于不是栈顶数字，我们需要到push序列中还没有被push进栈的数字中去搜索该数字。但此时push序列中所有数字都已被push进入栈，因此该序列不可能是一个pop序列。
也就是说，如果我们希望pop的数字正好是栈顶数字，直接pop出栈即可；如果希望pop的数字目前不在栈顶，我们就到push序列中还没有被push到栈里的数字中去搜索这个数字，并把在它之前的所有数字都push进栈。如果所有的数字都被push进栈仍然没有找到这个数字，表明该序列不可能是一个pop序列。
java代码如下
[java]
import java.util.LinkedList;
public class Test_24 {
public static void main(String[] args) {
String push="12345";
String pop="43512";
System.out.print("输出序列是否为合法的pop序列："+IsPossiblePopOrder(push,pop));
}
public static boolean IsPossiblePopOrder(String push,String pop){
if(push.length()!=pop.length()){
System.out.println("输入输出序列长度不一样！");
return false;
}
int length = push.length();
boolean isPossible = false;
//list模拟辅助栈
LinkedList<Character> list = new LinkedList<Character>();
int pushindex = 0;
int popindex = 0;
if(push!=null&&pop!=null&&length>0){
//检查pop序列中每一个字符
while(popindex<length){
//当栈顶字符和pop中要访问的字符不一样时候，将push中未入栈的字符入栈
while(list.size()==0 || list.getLast()!= pop.charAt(popindex)){
if(pushindex>=length)break;
list.add(push.charAt(pushindex));
pushindex++;
}
//入栈完毕后，如果栈顶元素和pop中要访问的字符仍然不一样，则此pop序列不是合法的pop序列
if(list.getLast()!=pop.charAt(popindex)){
break;
}
//检查pop序列中的下一个字符
list.pollLast();
popindex++;
}
//如果pop序列中所有的字符都被检查过，则该序列是合法的
if(list.size()==0&&popindex==length){
isPossible = true;
}
}
return isPossible;
}
}
import java.util.LinkedList;
public class Test_24 {
public static void main(String[] args) {
String push="12345";
String pop="43512";
System.out.print("输出序列是否为合法的pop序列："+IsPossiblePopOrder(push,pop));
}
public static boolean IsPossiblePopOrder(String push,String pop){
if(push.length()!=pop.length()){
System.out.println("输入输出序列长度不一样！");
return false;
}
int length = push.length();
boolean isPossible = false;
//list模拟辅助栈
LinkedList<Character> list = new LinkedList<Character>();
int pushindex = 0;
int popindex = 0;
if(push!=null&&pop!=null&&length>0){
//检查pop序列中每一个字符
while(popindex<length){
//当栈顶字符和pop中要访问的字符不一样时候，将push中未入栈的字符入栈
while(list.size()==0 || list.getLast()!= pop.charAt(popindex)){
if(pushindex>=length)break;
&
补充：软件开发 , C++ ,
