題目：輸入兩個整數序列。其中一個序列表示棧的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;
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;
}
}
運行結果：
輸出序列是否為合法的pop序列：false
