NO IMAGE

題目:輸入兩個整數數列,第一個序列表示棧的壓入順序,請判斷第二個序列是否是該棧的其中一個彈出順序。假設壓入棧的所有數字均不相等。例如,序列{1,2,3,4,5}是某棧的壓棧序列,序列{4,5,3,2,1}是該壓棧序列對應的一個彈出序列,但是{4,3,5,1,2}就不可能是該壓棧序列對應的一個彈出序列。

思路

解決這個問題很直觀的想法就是建立一個輔助棧,把輸入的第一個序列中的數字依次壓入輔助棧,並按著第二個序列的順序依次從該棧中彈出數字。

以彈出{序列4,5,3,2,1}為例分析壓入棧和彈出的過程。第一個希望被彈出的數字是4.,因此4需要先壓入輔助棧,壓入棧的順序由壓棧序確定,也就是把4壓入棧之前,數字1,2,3都需要壓入棧,此時棧中包含數字4.分別是1,2,3,4.其中4位於棧頂,把4彈出棧後,剩下的 數字3位於棧頂,接下來希望被彈出的5,由於它不是棧頂元素,因此我們接著在第一個序列中把4以後的數字壓入輔助棧,直到壓入數字5,這個時候5位於棧頂,就可以被彈出來了。接下來希望被彈出的是3,2,1.由於每次操作前他們都位於棧頂,因此直接彈出即可。

接下來再分析彈出序列{4,3,5,1,2}。第一個希望被彈出的是4和前面的情況一樣。把4彈出之後,3位於棧頂,可以直接彈出,接下來希望被彈出的是5,由於它不是棧頂元素,因此我們接著在第一個序列中把4以後的數字壓入輔助棧,直到壓入數字5,這個時候5位於棧頂,就可以被彈出來了。此時棧中有兩個數字1 ,2,其中2位於棧頂,由於接下來希望被彈出的 數字是1,我們需要從壓棧序列中尚未壓棧的數字中去搜素這個數字。但是此時所有壓棧序列中的數字都已經壓棧了,所以該彈出序列不是{1,2,3,4,5}對應的彈出序列。

總結
綜上所訴,我們可以找到一個判斷一個序列是不是棧的彈出序列的規律:如果下一個彈出數字剛好是棧頂數字,那麼直接彈出,如果不是,則把尚未壓棧的數字壓入輔助棧,直到把下一個彈出的數字壓入棧頂為止,如果所有數字都壓入後仍然沒有找到下一個彈出數字,那麼該序列不可能是一個彈出序列。

形成了思路之後,下面附上程式碼~

bool IsPopOrder(const int* pPush, const int* pPop, int nLength) 
{
bool bOrderFlag = false;
if (NULL != pPush && NULL != pPop && nLength > 0) {
const int* pNextPush = pPush;
const int* pNextPop = pPop;
std::stack<int> pStack;
while (pNextPop - pPop < nLength) {//直到彈出序列為空
while (pStack.empty() || pStack.top() != *pNextPush) {//直到壓入棧的數字等於需要彈出的數字
if (pNextPush - pPush == nLength) {//全部壓棧
break;
}
pStack.push(*pNextPush);
pNextPush  ;
}
if (pStack.top() != *pNextPush) {// 匹配失敗
break;
}
pStack.pop();
pNextPop  ;
}
if (pStack.empty() && pNextPop - pPop == nLength) {//全部匹配成功
bOrderFlag = true;
} 
}
return bOrderFlag;
}

以上,歡迎留言交流~