TypeScript棧的壓入與彈出序列校驗(yà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-test.ts
以上就是TypeScript棧的壓入與彈出序列校驗(yàn)的詳細(xì)內(nèi)容,更多關(guān)于TypeScript 棧序列校驗(yàn)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
- TypeScript之調(diào)用棧的實(shí)現(xiàn)
- 前端算法之TypeScript包含min函數(shù)的棧實(shí)例詳解
- TypeScript數(shù)組實(shí)現(xiàn)棧與對(duì)象實(shí)現(xiàn)棧的區(qū)別詳解
- Typescript是必須要學(xué)習(xí)嗎?如何學(xué)習(xí)TS全棧開(kāi)發(fā)
- 數(shù)據(jù)結(jié)構(gòu)TypeScript之棧和隊(duì)列詳解
- TypeScript數(shù)據(jù)結(jié)構(gòu)棧結(jié)構(gòu)Stack教程示例
- Typescript實(shí)現(xiàn)棧的方法示例
相關(guān)文章
微信小程序 循環(huán)及嵌套循環(huán)的使用總結(jié)
這篇文章主要介紹了微信小程序 循環(huán)及嵌套循環(huán)的使用總結(jié)的相關(guān)資料,希望通過(guò)本文能幫助到大家,需要的朋友可以參考下2017-09-09codemirror6實(shí)現(xiàn)在線代碼編輯器使用詳解
這篇文章主要為大家介紹了codemirror6實(shí)現(xiàn)在線代碼編輯器使用詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-01-01微信小程序中input標(biāo)簽詳解及簡(jiǎn)單實(shí)例
這篇文章主要介紹了微信小程序中input標(biāo)簽詳解及簡(jiǎn)單實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-05-05javascript數(shù)據(jù)類(lèi)型之原始類(lèi)型詳解
這篇文章主要為大家介紹了javascript數(shù)據(jù)類(lèi)型之原始類(lèi)型詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-06-06前端面試必會(huì)網(wǎng)絡(luò)跨域問(wèn)題解決方法
這篇文章主要為大家介紹了前端面試必會(huì)的網(wǎng)絡(luò)跨域問(wèn)題解決方法講解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-07-07微信小程序 (一)新建項(xiàng)目hello WeApp 詳細(xì)介紹
這篇文章主要介紹了微信小程序 (一)hello WeApp 詳細(xì)介紹的相關(guān)資料,需要的朋友可以參考下2016-09-09微信小程序 wx.request方法的異步封裝實(shí)例詳解
這篇文章主要介紹了微信小程序 wx.request方法的異步封裝實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-05-05