欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

TypeScript棧的壓入與彈出序列校驗(yàn)

 更新時(shí)間:2022年09月15日 10:53:42   作者:神奇的程序員  
這篇文章主要為大家介紹了TypeScript棧的壓入與彈出序列校驗(yàn)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

前言

有兩個(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è)已取索引,在壓入序列中從已取索引位置開(kāi)始尋找與之相等的元素,將它之前的數(shù)字和其本身依次入棧,每取1個(gè)元素就將索引自增1次

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

取出彈出序列的第2個(gè)元素,在壓入序列中從已取索引位置開(kāi)始尋找與之相等的元素,將它之前的數(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;
}

最后,我們將開(kāi)頭列舉的例子來(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);

示例代碼

StackPushAndPopSequence.ts

stackPushAndPopSequence-test.ts

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

相關(guān)文章

最新評(píng)論