前言

有兩個整數(shù)序列，第一個序列表示棧的壓入順序，判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的數(shù)字均不相等。例如，序列[1, 2, 3, 4, 5]是某棧的壓棧序列，序列[4, 5, 3, 2, 1]是該棧序列對應(yīng)的一個彈出序列，但[4, 3, 5, 1, 2]就不可能是該壓棧序列的彈出序列。

思路分析

仔細(xì)分析題目后，我們很直觀的想法就是構(gòu)造一個輔助棧，把壓入序列中的數(shù)字依次壓入該輔助棧。按照彈出序列的順序依次從該棧中彈出數(shù)字，如果輔助棧被清空則代表此序列是它的一個彈出序列，否則就不可能是一個彈出序列。

彈出序列滿足條件

如下圖所示，它的壓入過程為：

取出彈出序列的第1個元素，維護一個已取索引，在壓入序列中從已取索引位置開始尋找與之相等的元素，將它之前的數(shù)字和其本身依次入棧，每取1個元素就將索引自增1次

• 此時，棧頂元素與彈出序列的第1個元素相等，將棧頂元素出棧。

取出彈出序列的第2個元素，在壓入序列中從已取索引位置開始尋找與之相等的元素，將它之前的數(shù)字和其本身依次入棧。

• 此時，棧頂元素與彈出序列的第2個元素相等，將棧頂元素出棧。

取出彈出序列的第3個元素，此時，壓入序列的元素已經(jīng)被取完。我們繼續(xù)判斷 輔助棧中的元素是否與彈出序列的元素相等。

• 棧頂元素為3，要彈出的元素也是3，二者相等，棧頂元素出棧

取出彈出序列的第4個元素

• 棧頂元素為2，要彈出的元素也是2，二者相等，棧頂元素出棧

取出彈出序列的第5個元素

• 棧頂元素為1，要彈出的元素也是1，二者相等，棧頂元素出棧

彈出序列已取完，輔助棧已清空。 該彈出序列屬于壓入序列的一個彈出順序

彈出序列不滿足條件

接下來，我們來分析下它不是壓入序列的彈出順序的情況，它的壓入過程與滿足條件時一樣，唯獨不同的是，彈出序列的第3個元素從輔助棧出棧后，壓入序列已經(jīng)被取完。此時，彈出序列的第4個元素是1，輔助棧的棧頂元素是2，二者不等，那么該序列肯定不是壓入序列的彈出順序。

實現(xiàn)代碼

經(jīng)過上面的分析，我們已經(jīng)知道了如何解決這個問題。思路已明確，接下來，我們就可以愉快的進入編碼環(huán)節(jié)了??

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();
  // 下一個彈出序列存在則執(zhí)行進一步的判斷
  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 {
      // 元素不等則終止循環(huán)，此時壓入序列已經(jīng)全部壓入輔助棧，該序列不可能是一個彈出序列
      break;
    }
    // 輔助棧清空，則代表彈出序列是正確的
    if (stackData.isEmpty()) {
      return true;
    }
  }
  return false;
}

最后，我們將開頭列舉的例子來驗證下上述代碼是否正確執(zhí)行，如下所示：

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

以上就是TypeScript棧的壓入與彈出序列校驗的詳細(xì)內(nèi)容，更多關(guān)于TypeScript 棧序列校驗的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論