前言

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

思路分析

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

彈出序列滿足條件

如下圖所示，它的壓入過(guò)程為：

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

此時(shí)，棧頂元素與彈出序列的第1個(gè)元素相等，將棧頂元素出棧。

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

此時(shí)，棧頂元素與彈出序列的第2個(gè)元素相等，將棧頂元素出棧。

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

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

取出彈出序列的第4個(gè)元素；

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

取出彈出序列的第5個(gè)元素；

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

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

彈出序列不滿足條件；

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

實(shí)現(xiàn)代碼

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

export function StackPushAndPopSequence(
  pushSequence: Array<number>,
  popupSequence: Array<number>
): boolean {
  if (pushSequence.length === 0 || popupSequence.length === 0) return false;
  // 下一個(gè)入棧、出棧索引
  let nextPushIndex = 0;
  let nextPopIndex = 0;
  // 輔助棧
  const stackData = new Stack();
  // 下一個(gè)彈出序列存在則執(zhí)行進(jìn)一步的判斷
  while (nextPopIndex < popupSequence.length) {
    // 下一個(gè)彈出序列的元素與棧頂元素不等則入棧
    while (
      nextPushIndex < pushSequence.length &&
      popupSequence[nextPopIndex] !== stackData.peek()
    ) {
      stackData.push(pushSequence[nextPushIndex]);
      nextPushIndex++;
    }

    // 棧頂元素與下一個(gè)彈出序列元素相等則出棧
    if (stackData.peek() === popupSequence[nextPopIndex]) {
      stackData.pop();
      nextPopIndex++;
    } else {
      // 元素不等則終止循環(huán)，此時(shí)壓入序列已經(jīng)全部壓入輔助棧，該序列不可能是一個(gè)彈出序列
      break;
    }
    // 輔助棧清空，則代表彈出序列是正確的
    if (stackData.isEmpty()) {
      return true;
    }
  }
  return false;
}

最后，我們將開頭列舉的例子來(lái)驗(yàn)證下上述代碼是否正確執(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);

示例代碼

本文所用代碼完整版請(qǐng)移步：

• StackPushAndPopSequence.ts
• stackPushAndPopSequence-test.ts