面試題20：棧的壓入、彈出序列

思路：如果下一個彈出的數字剛好是棧頂數字，則直接彈出。若下一個彈出的數字不在棧頂，則把壓棧序列中還沒有入棧的數字壓入輔助棧，直到把下一個需要彈出的數字壓入棧頂為止。若所有的數字都壓入棧了仍沒有找到下一個彈出的數字，則表明該序列不可能滴一個彈出序列。

代碼：

#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;

bool IsPopOrder(int *pPush, int *pPop, int nLength)
{
   if (pPush == NULL || pPop == NULL || nLength <= 0)
   {
       return false;
   }

   stack<int> s;
   s.push(pPush[0]);
   int nPop_index = 0;
   int nPush_index = 1;
   while (nPop_index < nLength)
   {
	   while (s.top() != pPop[nPop_index] && nPush_index < nLength)
	   {
		   s.push(pPush[nPush_index]);
		   nPush_index++;
	   }

	   if (s.top() == pPop[nPop_index])
	   {
		   s.pop();
		   nPop_index++;
	   }
	   else
	   {
		   return false;
	   }	   
   }

   return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nPush[5] = {1,2,3,4,5};	
	int nPop1[5] = {4,5,3,2,1};
	int nPop2[5] = {4,3,5,1,2};
    int nPop3[5] = {5,4,3,2,1};
	int nPop4[5] = {4,5,2,3,1};
	cout << IsPopOrder(nPush, nPop1, 5) << endl;
	cout << IsPopOrder(nPush, nPop2, 5) << endl;
	cout << IsPopOrder(nPush, nPop3, 5) << endl;
	cout << IsPopOrder(nPush, nPop4, 5) << endl;
    system("pause");
	return 0;
}