棧的壓入與彈出序列校驗
前言
有兩個整數序列，第一個序列表示棧的壓入順序，判斷第二個序列是否為該棧的彈出順序。假設壓入棧的數字均不相等。例如，序列[1, 2, 3, 4, 5]是某棧的壓棧序列，序列[4, 5, 3, 2, 1]是該棧序列對應的一個彈出序列，但[4, 3, 5, 1, 2]就不可能是該壓棧序列的彈出序列。
思路分析
仔細分析題目后，我們很直觀的想法就是構造一個輔助棧，把壓入序列中的數字依次壓入該輔助棧。按照彈出序列的順序依次從該棧中彈出數字，如果輔助棧被清空則代表此序列是它的一個彈出序列，否則就不可能是一個彈出序列。
彈出序列滿足條件
如下圖所示，它的壓入過程為：
取出彈出序列的第1個元素，維護一個已取索引，在壓入序列中從已取索引位置開始尋找與之相等的元素，將它之前的數字和其本身依次入棧，每取1個元素就將索引自增1次。
此時，棧頂元素與彈出序列的第1個元素相等，將棧頂元素出棧。
取出彈出序列的第2個元素，在壓入序列中從已取索引位置開始尋找與之相等的元素，將它之前的數字和其本身依次入棧。
此時，棧頂元素與彈出序列的第2個元素相等，將棧頂元素出棧。
取出彈出序列的第3個元素，此時，壓入序列的元素已經被取完。我們繼續判斷 輔助棧中的元素是否與彈出序列的元素相等。
棧頂元素為3，要彈出的元素也是3，二者相等，棧頂元素出棧；
取出彈出序列的第4個元素；
棧頂元素為2，要彈出的元素也是2，二者相等，棧頂元素出棧；
取出彈出序列的第5個元素；
棧頂元素為1，要彈出的元素也是1，二者相等，棧頂元素出棧；
彈出序列已取完，輔助棧已清空。 該彈出序列屬于壓入序列的一個彈出順序；
彈出序列不滿足條件；
接下來，我們來分析下它不是壓入序列的彈出順序的情況，它的壓入過程與滿足條件時一樣，唯獨不同的是，彈出序列的第3個元素從輔助棧出棧后，壓入序列已經被取完。此時，彈出序列的第4個元素是1，輔助棧的棧頂元素是2，二者不等，那么該序列肯定不是壓入序列的彈出順序。
實現代碼
經過上面的分析，我們已經知道了如何解決這個問題。思路已明確，接下來，我們就可以愉快的進入編碼環節了。
export function StackPushAndPopSequence(
pushSequence: Array<number>,
popupSequence: Array<number>
): boolean {
if (pushSequence.length === 0 || popupSequence.length === 0) return false;
// 下一個入棧、出棧索引
let nextPushIndex = 0;
let nextPopIndex = 0;
// 輔助棧
const stackData = new Stack();
// 下一個彈出序列存在則執行進一步的判斷
while (nextPopIndex < popupSequence.length) {
// 下一個彈出序列的元素與棧頂元素不等則入棧
while (
nextPushIndex < pushSequence.length &&
popupSequence[nextPopIndex] !== stackData.peek()
) {
stackData.push(pushSequence[nextPushIndex]);
nextPushIndex++;
}
// 棧頂元素與下一個彈出序列元素相等則出棧
if (stackData.peek() === popupSequence[nextPopIndex]) {
stackData.pop();
nextPopIndex++;
} else {
// 元素不等則終止循環，此時壓入序列已經全部壓入輔助棧，該序列不可能是一個彈出序列
break;
}
// 輔助棧清空，則代表彈出序列是正確的
if (stackData.isEmpty()) {
return true;
}
}
return false;
}
最后，我們將開頭列舉的例子來驗證下上述代碼是否正確執行，如下所示：
const pushSuite = [1, 2, 3, 4, 5];
const popSuite1 = [4, 5, 3, 2, 1];
const popSuite2 = [4, 3, 5, 1, 2];
const result1 = StackPushAndPopSequence(pushSuite, popSuite1);
const result2 = StackPushAndPopSequence(pushSuite, popSuite2);
console.log(result1, result2);
示例代碼
本文所用代碼完整版請移步：
- StackPushAndPopSequence.ts
- stackPushAndPopSequence-test.ts
