面試題22：棧的壓入、彈出序列
題目：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1、2、3、4、5 是某棧的壓棧序列，序列4、5、3、2、1 是該壓棧序列對應(yīng)的一個彈出序列，但 4、3、5、1、2 就不可能是該壓棧序列的彈出序列。

壓棧序列為1、2、3、4、5，彈出序列4、5、3、2、1對應(yīng)的壓棧和彈出過程

一個壓入順序為1、2、3、4、5的棧沒有一個彈出序列為4、3、5、1、2

規(guī)律:
如果下一個彈出的數(shù)字剛好是棧頂數(shù)字，那么直接彈出。如果下一個彈出的數(shù)字不在棧頂，我們把壓棧序列中還沒有入棧的數(shù)字壓入輔助棧，直到把下一個需要彈出的數(shù)字壓入棧頂為止。如果所有的數(shù)字都壓入棧了仍然沒有找到下一個彈出的數(shù)字，那么該序列不可能是一個彈出序列。

代碼如下:

#include <iostream> #include <stack> using namespace std;bool IsPopOrder(const int *pPush, const int *pPop, int nLength) {bool bPossible = false;if (pPush != nullptr && pPop != nullptr && nLength > 0){const int *pNextPush = pPush;const int *pNextPop = pPop;stack<int>stackDate;while (pNextPop - pPop < nLength){while (stackDate.empty() || stackDate.top() != *pNextPop){if (pNextPush - pPush == nLength) break;stackDate.push(*pNextPush);pNextPush++;}if (stackDate.top() != *pNextPop) break;stackDate.pop();pNextPop++;}if (stackDate.empty() && pNextPop - pPop == nLength) bPossible = true;}return bPossible; }

測試用例：
● 功能測試（輸入的兩個數(shù)組含有多個數(shù)字或者只有 1 個數(shù)字，第二個數(shù)組是或者不是第一個數(shù)組表示的壓入序列對應(yīng)的棧的彈出序列）。
● 特殊輸入測試（輸入兩個NULL指針）。
本題考點(diǎn)：
● 考查分析復(fù)雜問題的能力。剛聽到這個面試題的時候，很多人可能都沒有思路。這個時候，可以通過舉一兩個例子，一步步分析壓棧、彈出的過程，從中找出規(guī)律。
● 考查應(yīng)聘者對棧的理解。

總結(jié)

以上是生活随笔為你收集整理的[剑指offer]面试题22：栈的压入、弹出序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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