題目31：棧的壓入、彈出序列
輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。
舉例說明
序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）
思路
解決這個問題很直觀的想法就是建立一個輔助棧，把輸入的第一個序列中的數字依次壓入該輔助棧，并按照第二個序列的順序依次從該棧中彈出數字。
判斷一個序列是不是棧的彈出序列的規(guī)律：
- 壓棧序列：
int[] push - 彈出序列：
int[] pop - 輔助棧：
Stack<Integer> help = new Stack<>(); - 判斷彈出元素是不是棧頂元素
help.peek() != pop[nextPop]
- 如果Stack下一個彈出的數字剛好是棧頂數字，那么直接彈出
- 如果Stack下一個彈出的數字不在棧頂，把push[]中還沒有入棧的數字壓入help，直到把下一個需要彈出的數字壓入棧頂為止
- 如果所有的數字都壓入棧了仍然沒有找到下一個彈出的數字，那么該序列不可能是一個彈出序列
代碼實現
public class _31 {
public static boolean isPopOrder(int[] push, int[] pop) {
boolean isPossible = false;
// a. 都不為空 b. 都有數據，且數據個數都相等
if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
Stack<Integer> help = new Stack<>();// 用于存放入棧時的數據
int nextPush = 0;
int nextPop = 0;
while (nextPop < pop.length) { // 如果pop[] 沒有處理完就繼續(xù)進行處理
// a. 棧為空 b. 棧頂的元素與當前處理的出棧元素不相同
while (help.isEmpty() || help.peek() != pop[nextPop]) {
if (nextPush >= push.length) {//若入棧的元素已經全部入棧了
break;//就退出內層循環(huán)
}
//說明沒被break。nextPush < push.length,還有push[] 可以入棧
help.push(push[nextPush]);// 將push[]元素 入 help棧
nextPush++;// 指向下一個要處理的入棧元素的位置
}
// 執(zhí)行到此處有兩種情況：
// 第一種：在棧頂上找到了一個與入棧元素相等的元素
// 第二種：在棧頂上沒有找到一個與入棧元素相等的元素，但輸入棧的元素已經全部入棧了
// 對于第二種情況就說彈出棧的順序是不符合要求的，退出外層循環(huán)
if (help.peek() != pop[nextPop]) {
break;
}
help.pop();// 對應到第一種情況：需要要棧的棧頂元素彈出
nextPop++;// 指向pop[]下一個要處理的出棧元素的位置
}
// 執(zhí)行到此處有兩種情況
// 第一種：外層while循環(huán)被break
// 第二種：所有的出棧元素都被正確匹配
// 對于出現的第一種情況其stack.isEmpty()必不為空，原因為分析如下：
// 所有的入棧元素一定會入棧，但是只有匹配的情況下才會出棧，
// 匹配的次數最多與入棧元素個數元素相同（兩個數組的長度相等），如果有不匹配的元素，
// 必然會使出棧的次數比入棧的次數少，這樣棧中至少會有一個元素
// 對于第二種情況其stack.isEmpty()一定為空
// 所以書本上的nextPop == pop.length（pNextPop-pPop==nLength）是多余的
if (help.isEmpty()) {
isPossible = true;
}
}
return isPossible;
}
public static void main(String[] args) {
int[] push = { 1, 2, 3, 4, 5 };
int[] pop1 = { 4, 5, 3, 2, 1 };
int[] pop2 = { 4, 3, 5, 1, 2 };
System.out.println(isPopOrder(push, pop1));// true
System.out.println(isPopOrder(push, pop2));// false
}
}
輸出：
true
false
