題目：輸入兩個整數(shù)序列钱雷，第一個序列表示棧的壓入順序抑堡，請判斷二個序列是否為該棧的彈出順序瀑构。假設(shè)壓入棧的所有數(shù)字均不相等普舆。
解法1：
代碼如下：
package demo;
import java.util.Stack;
public class Test22 {
/**
* @param push
* 入棧序列
* @param pop
* 出棧序列
* @return true：出棧序列是入棧序列的一個彈出順序
*/
public static boolean isPopOrder(int[] push, int[] pop) {
// 判斷出棧序列是不是入棧序列的一個彈出順序帐萎，默認(rèn)為false
boolean isPossible = false;
if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
// 輔助棧：存放入棧時的數(shù)據(jù)
Stack<Integer> stack = new Stack<>();
// 記錄下一個要處理的入棧元素的位置
int nextPush = 0;
// 記錄下一個要處理的出棧元素的位置
int nextPop = 0;
// 如果出棧元素沒有處理完撩独，就繼續(xù)進(jìn)行處理
while (nextPop < pop.length) {
// 如果棧為空敞曹，或者棧頂元素與當(dāng)前處理的出棧元素不相同，一直進(jìn)行操作
while (stack.isEmpty() || stack.peek() != pop[nextPop]) {
// 如果入棧元素已經(jīng)全部入棧了综膀，就退出內(nèi)層循環(huán)
if (nextPush >= push.length) {
break;
}
// 還有入棧元素可以入棧
stack.push(push[nextPush]);
nextPush++;
}
/*
* 此次有2種情況：
* 1.在棧頂上找到了一個與出棧元素相等的元素
* 2.在棧頂上沒有找到一個與出棧元素相等的元素澳迫，而且入棧元素已經(jīng)全部入棧了
*/
// 2.
if (stack.peek() != pop[nextPop]) {
break;
}
// 第1種情況，就將出棧的棧頂元素彈出
stack.pop();
// 指向下一個要處理的出棧元素的位置
nextPop++;
}
/*
* 此處有2種情況：
* 1. 外層while循環(huán)在第2種情況下退出剧劝，此時stack必不為空
* 2. 所有的出棧元素都被正確匹配橄登，此時stack為空
*/
if (stack.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 = { 3, 5, 4, 2, 1 };
int[] pop3 = { 4, 3, 5, 1, 2 };
int[] pop4 = { 3, 5, 4, 1, 2 };
System.out.println(isPopOrder(push, pop1));
System.out.println(isPopOrder(push, pop2));
System.out.println(isPopOrder(push, pop3));
System.out.println(isPopOrder(push, pop4));
int[] push5 = { 1 };
int[] pop5 = { 1 };
System.out.println(isPopOrder(push5, pop5));
System.out.println(isPopOrder(null, null));
}
}
運行結(jié)果
