【剑指offer 面试题22】栈的压入、弹出序列

思路：

　　不停地压栈，直到栈头元素与弹出序列的首元素相等则出栈，同时弹出序列后移；若不相等则一直保持压栈，直到压入所有元素后弹出序列仍不为空，则说明无法匹配。

C++:

 #include <iostream>

 #include <vector>

 #include <stack>

 using namespace std;

 bool IsPreOrder(vector<int>& pushVec, vector<int>& popVec)

 {

     if(pushVec.size() !=  && popVec.size() != )

     {

         vector<int>::iterator itPush = pushVec.begin();

         vector<int>::iterator itPop = popVec.begin();

         stack<int> _stack;

         while(itPop != popVec.end())

         {

             while(_stack.empty() || _stack.top() != *itPop)

             {

                 if(itPush == pushVec.end())

                     break;

                 cout<<"push: "<<*itPush<<endl;

                 _stack.push(*itPush);

                 itPush++;

             }

             if(_stack.top() != *itPop)

                 break;

             cout<<"pop: "<<_stack.top()<<endl;

             _stack.pop();

             itPop++;

         }

         if(_stack.empty() && itPop == popVec.end())

             return true;

     }

     return false;

 }

 int main()

 {

     int apush[] = {,,,,};

     int apop1[] = {,,,,};

     int apop2[] = {,,,,};

     vector<int> vpush(apush, apush + );

     vector<int> vpop1(apop1, apop1 + );

     vector<int> vpop2(apop2, apop2 + );

     cout<<"push: 1 2 3 4 5 pop: 4 5 3 2 1"<<endl;

     cout<<"res = "<<IsPreOrder(vpush, vpop1)<<endl<<endl;

     cout<<"push: 1 2 3 4 5 pop: 4 3 5 1 2"<<endl;

     cout<<"res = "<<IsPreOrder(vpush, vpop2)<<endl;

 }

测试结果：

push: 1 2 3 4 5 pop: 4 5 3 2 1
push: 1
push: 2
push: 3
push: 4
pop: 4
push: 5
pop: 5
pop: 3
pop: 2
pop: 1
res = 1

push: 1 2 3 4 5 pop: 4 3 5 1 2
push: 1
push: 2
push: 3
push: 4
pop: 4
pop: 3
push: 5
pop: 5
res = 0