面試題之判斷棧的入棧和出棧序列的合法性

完整題目是這樣的：給我們兩個序列，第一個序列表示棧的壓入順序，然後讓判斷第二個序列是不是是否是該棧的彈出序列。現設第一個序列為[1,2,3,4,5],第二個序列為[3,2,5,4,1],可以看出這個出棧順序是合法的，那麼我們怎麼通過程序來驗證呢？

既然是判斷棧的出棧順序，那麼我們肯定得有一個輔助棧，來幫助我們做這樣的題。我們把第一個序列中的數字一次壓入棧中，壓入的過程中按照第二個序列的順序依次從棧中彈出數字。

我采用的是用vector來存放兩個序列，判斷當棧為空或者棧頂元素和V2[i]不相等，就繼續壓棧。第一次1壓入棧，一直滿足上面說的壓棧條件，所以壓入了1,2,3，此時棧頂的3和V2第一個元素相等，則進行出棧操作，i++即下次比較V2的下一個元素。

這個循環的操作，重要的是判斷結束的條件。

下面是代碼：

 1 #include<stack>
 2 bool CheckOutStackOrder(const vector<int>& v1, const vector<int>& v2)
 3 {
 4     if (v1.size() != v2.size() )
 5         return false;
 6     stack<int> s;
 7     size_t idex1 = 0, idex2 = 0;
 8     while (idex2 < v2.size())
 9     {
10         while (s.empty() || s.top()!=v2[idex2])
11         {
12             if (idex1 < v1.size())
13             {
14                 s.push(v1[idex1++]);
15             }
16             else
17                 return false;
18         }
19         idex2++;
20         s.pop();
21     }
22     return true;
23 }
24 void funtest()
25 {
26     vector<int> v1;
27     vector<int> v2;
28     v1.push_back(1);
29     v1.push_back(2);
30     v1.push_back(3);
31     v1.push_back(4);
32     v1.push_back(5);
33 
34     v2.push_back(3);
35     v2.push_back(2);
36     v2.push_back(5);
37     v2.push_back(4);
38     v2.push_back(1);
39     bool a = CheckOutStackOrder(v1, v2);
40 }