題目31：棧的壓入、彈出序列
輸入兩個(gè)整數(shù)序列沾谓，第一個(gè)序列表示棧的壓入順序委造，請(qǐng)判斷二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等均驶。
舉例說(shuō)明
序列1,2,3,4,5是某棧的壓入順序昏兆，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列妇穴。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）
思路
解決這個(gè)問(wèn)題很直觀的想法就是建立一個(gè)輔助棧爬虱，把輸入的第一個(gè)序列中的數(shù)字依次壓入該輔助棧，并按照第二個(gè)序列的順序依次從該棧中彈出數(shù)字腾它。
判斷一個(gè)序列是不是棧的彈出序列的規(guī)律：
- 壓棧序列：
int[] push - 彈出序列：
int[] pop - 輔助棧：
Stack<Integer> help = new Stack<>(); - 判斷彈出元素是不是棧頂元素
help.peek() != pop[nextPop]
- 如果Stack下一個(gè)彈出的數(shù)字剛好是棧頂數(shù)字跑筝，那么直接彈出
- 如果Stack下一個(gè)彈出的數(shù)字不在棧頂，把push[]中還沒(méi)有入棧的數(shù)字壓入help瞒滴，直到把下一個(gè)需要彈出的數(shù)字壓入棧頂為止
- 如果所有的數(shù)字都?jí)喝霔Ａ?strong>仍然沒(méi)有找到下一個(gè)彈出的數(shù)字曲梗，那么該序列不可能是一個(gè)彈出序列
代碼實(shí)現(xiàn)
public class _31 {
public static boolean isPopOrder(int[] push, int[] pop) {
boolean isPossible = false;
// a. 都不為空 b. 都有數(shù)據(jù)，且數(shù)據(jù)個(gè)數(shù)都相等
if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
Stack<Integer> help = new Stack<>();// 用于存放入棧時(shí)的數(shù)據(jù)
int nextPush = 0;
int nextPop = 0;
while (nextPop < pop.length) { // 如果pop[] 沒(méi)有處理完就繼續(xù)進(jìn)行處理
// a. 棧為空 b. 棧頂?shù)脑嘏c當(dāng)前處理的出棧元素不相同
while (help.isEmpty() || help.peek() != pop[nextPop]) {
if (nextPush >= push.length) {//若入棧的元素已經(jīng)全部入棧了
break;//就退出內(nèi)層循環(huán)
}
//說(shuō)明沒(méi)被break。nextPush < push.length,還有push[] 可以入棧
help.push(push[nextPush]);// 將push[]元素 入 help棧
nextPush++;// 指向下一個(gè)要處理的入棧元素的位置
}
// 執(zhí)行到此處有兩種情況：
// 第一種：在棧頂上找到了一個(gè)與入棧元素相等的元素
// 第二種：在棧頂上沒(méi)有找到一個(gè)與入棧元素相等的元素虏两，但輸入棧的元素已經(jīng)全部入棧了
// 對(duì)于第二種情況就說(shuō)彈出棧的順序是不符合要求的愧旦，退出外層循環(huán)
if (help.peek() != pop[nextPop]) {
break;
}
help.pop();// 對(duì)應(yīng)到第一種情況：需要要棧的棧頂元素彈出
nextPop++;// 指向pop[]下一個(gè)要處理的出棧元素的位置
}
// 執(zhí)行到此處有兩種情況
// 第一種：外層while循環(huán)被break
// 第二種：所有的出棧元素都被正確匹配
// 對(duì)于出現(xiàn)的第一種情況其stack.isEmpty()必不為空，原因?yàn)榉治鋈缦拢? // 所有的入棧元素一定會(huì)入棧碘举，但是只有匹配的情況下才會(huì)出棧，
// 匹配的次數(shù)最多與入棧元素個(gè)數(shù)元素相同（兩個(gè)數(shù)組的長(zhǎng)度相等）搁廓，如果有不匹配的元素引颈，
// 必然會(huì)使出棧的次數(shù)比入棧的次數(shù)少，這樣棧中至少會(huì)有一個(gè)元素
// 對(duì)于第二種情況其stack.isEmpty()一定為空
// 所以書(shū)本上的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
