棧的壓入、彈出序列，彈出序列

棧的壓入、彈出序列，彈出序列

題目:判斷一數字序列是否為這些數字入棧的一種出棧方式（前提：棧中的數字不重復）

思路1:如果下一個彈出的數字剛好是棧頂數字，那麼直接彈出。如果下一個彈出的數字不在棧頂，我們把壓棧序列還沒有入棧的數字壓入輔助棧，知道把下一個要彈出的數字壓入棧頂為止。如果所有的數字都壓入了仍然沒有找到下一個彈出的數字，那麼該序列不可能是一個彈出序列。

思路2：開辟一個輔助棧，模擬入棧出戰過程(假設pa為入棧序列，pb為出戰序列),pA中的元素依次壓入輔助棧,新壓入的元素與彈出序列的棧底相同，輔助棧彈出，同時pB向上移動,不相同了pB中的元素繼續入輔助棧。

 1 #include "stdafx.h"
 2 #include <stack>
 3 
 4 //方法1 
 5 bool IsPopOrder(const int* pPush, const int* pPop, int nLength)
 6 {
 7     bool bPossible = false;
 8     
 9     if(pPush != NULL && pPop != NULL && nLength > 0)
10     {
11         const int* pNextPush = pPush;
12         const int* pNextPop = pPop;
13         
14         std::stack<int> stackData;
15         
16         while(pNextPop - pPop < nLength)
17         {
18             // 當輔助棧的棧頂元素不是要彈出的元素
19             // 先壓入一些數字入棧
20             while(stackData.empty() || stackData.top() != *pNextPop)
21             {
22                 // 如果所有數字都壓入輔助棧了，退出循環
23                 if(pNextPush - pPush == nLength)
24                     break;
25                 
26                 stackData.push(*pNextPush);
27                 
28                 pNextPush ++;
29             }
30             
31             if(stackData.top() != *pNextPop)
32                 break;
33         
34             stackData.pop();
35             pNextPop ++;
36         }
37         
38         if(stackData.empty() && pNextPop - pPop == nLength)
39             bPossible = true;
40     }
41     
42     return bPossible;
43     
44 }
45 
46 //方法2 
47 bool IsPopOrder1(const int* pPush, const int* pPop, int lengthA, int lengthB)
48 {
49     if( lengthA != lengthB || lengthA == 0)
50         return false;
51     bool flag = false;
52 
53     int pA =0;
54     int pB =0;
55     int *newpPush = new int[lengthA];
56     int top = -1;
57     for(pA = 0 ; pA < lengthA; ++pA)
58     {
59         ++top;
60         newpPush[top] = pPush[pA];
61         while(newpPush[top] == pPop[pB])
62         {
63             --top;
64             ++pB;
65         }
66     }
67     if(top == -1)
68         flag = true;
69     delete []newpPush;
70     return flag;
71 }
72 
73 int main()
74 {
75     const int nLength = 5 ;
76     int push[nLength] = {1,2,3,4,5};
77     int pop[nLength] = {4, 5, 3, 2, 1};
78     
79     bool  flag1 = IsPopOrder(push, pop, nLength);
80     printf("Solution 1 is %d\n", flag1 );
81     
82     bool  flag2 = IsPopOrder1(push, pop, nLength, nLength);
83     printf("Solution 2 is %d", flag2 );
84     return 0;
85 }