《劍指offer》面試題22：

題目：輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出序列。假設(shè)壓入棧的所有數(shù)字均不相同。

????????? 例如序列1、2、3、4、5是某棧的入棧序列，序列4、5、3、2、1是該壓棧序列所對(duì)應(yīng)的一個(gè)彈出序列，但是4、3、5、1、2就不可能是該壓棧序列的彈出序列。

分析：

???????? 直觀想法是使用輔助棧，把輸入的第一個(gè)序列數(shù)字依次壓入輔助棧，并按照第二個(gè)序列的順序依次從棧中彈出數(shù)字。

???????? 舉具體數(shù)字進(jìn)行分析，得出判斷一個(gè)序列是否是棧的彈出序列的規(guī)律：

??????????如果序列的下一個(gè)數(shù)字正好是棧頂?shù)臄?shù)字，那么直接彈出；如果下一個(gè)數(shù)字不在棧頂，則把壓棧序列中還沒(méi)有入棧的數(shù)字壓入輔助棧，直到找到需要彈出的數(shù)字壓入棧頂為止。如果所有的數(shù)字都?jí)喝霔Ａ巳匀粵](méi)有找到下一個(gè)彈出的數(shù)字，那么該序列不可能是一個(gè)彈出序列。

???????? 當(dāng)看到此題的時(shí)候，我想到一個(gè)方法，此種想法是錯(cuò)誤的：如果彈出序列中有兩個(gè)連續(xù)數(shù)字和壓棧時(shí)相同，而最長(zhǎng)的相同序列不位于壓棧的尾部，我來(lái)斷定不可能是該壓棧序列的彈出序列。因?yàn)槿绻麖棾鲂蛄兄袃蓚€(gè)連續(xù)數(shù)和壓入順序相同，那么只能是壓入第一個(gè)彈出再壓入第二個(gè)彈出此種方式，但是忽略了可以第一個(gè)第二個(gè)壓入彈出繼續(xù)后面壓完再?gòu)棾觥＿@種方式是錯(cuò)誤的。

代碼：

(1) 下面這個(gè)代碼自己寫(xiě)的（測(cè)試通過(guò)），當(dāng)檢測(cè)到第二個(gè)序列中的數(shù)字時(shí)，并沒(méi)有壓入輔助棧，而是忽略，再檢查下一個(gè)數(shù)字。這樣省去了入棧出棧的代價(jià)。

bool IsPopOrder2(const int* pPush, const int* pPop, int nLength) {if( pPush == NULL || pPop == NULL || nLength <= 0 )return false;stack<int> tempStack;int pushIndex = 0;for( int i=0; i<nLength; ++i ){//輔助棧為空，或者棧頂元素和彈出數(shù)字不相同if( tempStack.empty() || tempStack.top()!=pPop[i] ){for( ; pushIndex<nLength; ++pushIndex ){//彈出數(shù)字前的序列都入棧if( pPush[pushIndex] != pPop[i] ){tempStack.push( pPush[pushIndex] );}else //檢測(cè)到彈出數(shù)字時(shí)，下次檢測(cè)下一位{++ pushIndex;break;}}//當(dāng)索引到達(dá)壓棧序列末端，且最后一位沒(méi)有檢測(cè)到時(shí)，肯定不是此棧的出棧序列if( pushIndex == nLength && pPush[nLength-1]!= pPop[i]){return false;}}else //棧頂元素和彈出數(shù)字相同{tempStack.pop();}}return true; }

(2)附上《劍指offer》中的代碼，按照以上的分析寫(xiě)的，這樣增加了數(shù)據(jù)入棧出棧，但是每個(gè)元素都是從輔助棧彈出的，具有統(tǒng)一性。

bool IsPopOrder(const int* pPush, const int* pPop, int nLength) {bool bPossible = false;if(pPush != NULL && pPop != NULL && nLength > 0){const int* pNextPush = pPush;const int* pNextPop = pPop;std::stack<int> stackData;while(pNextPop - pPop < nLength){// 當(dāng)輔助棧的棧頂元素不是要彈出的元素// 先壓入一些數(shù)字入棧while(stackData.empty() || stackData.top() != *pNextPop){// 如果所有數(shù)字都?jí)喝胼o助棧了，退出循環(huán)if(pNextPush - pPush == nLength)break;stackData.push(*pNextPush);pNextPush ++;}if(stackData.top() != *pNextPop)break;stackData.pop();pNextPop ++;}if(stackData.empty() && pNextPop - pPop == nLength)bPossible = true;}return bPossible; }

總結(jié)

以上是生活随笔為你收集整理的面试题整理6 栈的压入、弹出序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。