判斷棧的出棧順序是否正確

一 問題描述：

     兩個數組pPush和pPop分別存儲了壓棧序列和出棧序列，如何判斷出棧序列是否正確，假設元素不重覆。

     需要實現的函數：

  bool isStackOutRight(int *stackIn,int *stackOut,int length)

二 舉例：

    pPush中序列為：[5   9   1   8    13     4   2    7]

    給出一個出棧序列pPop：[8   4    13   1   7   2  9   5]，這個出棧序列是正確的。

    給出另一個出棧序列pPop:[8   4    13   1   5   4   2     7    9]，這個出棧序列就是錯誤的，因為8第一個出棧，說明棧中已經壓入過5  9  1三個元素，它們還存在棧中

    它們的出棧順序必須滿足 1  9  5 這個順序（可以不連續，但是1在9前，9在5前），但是出棧隊列中給出的順序是1   5   9，所以是錯誤的。

三  演算法思路：

     需要用到一個輔助棧stackData來存儲壓入棧而尚未出棧的元素

     現在舉錯誤的出棧順序為例：pPop：[8   4    13   1   5   4   2     7    9]

     1  對出棧序列進行遍歷，第1個元素是8，說明前面已經存過5  9  1，將它存入輔助棧中

          在壓入輔助棧的操作中，我們需要遍歷壓棧序列pPush：[5   9   1   8    13     4   2    7]

          （1）   [5   9   1   8    13     4   2    7]   index指向首元素5，不等於元素8 ，將5壓入輔助棧

        （2）   [5   9   1   8    13     4   2    7]   index指向元素9不等於元素8 ，將9壓入輔助棧

          （3）   [5   9   1   8    13     4   2    7]   index指向元素1不等於元素8 ，將1壓入輔助棧

          （4）   [5   9   1   8    13     4   2    7]   index指向元素8等於元素8 ，相等時不壓入，因為還要彈出

          （5）   [5   9   1   8    13     4   2    7]   index指向下一個元素，以便下次壓入操作

           壓棧結束後

           stackData：  1  9  5】        （“】”形象的表示棧開口方向向左，1是棧頂元素）  

           可以看出，壓入輔助棧的關鍵是壓棧序列中的元素是否等於目前的遍歷元素（8），不等於壓入，等於就不再壓入 

     2  遍歷第2個元素是4，它不等於stackData中的top元素1，說明它可能（也可能存在於輔助棧）是新壓入的元素，那麼容易知道4之前的元素13已經被壓入棧中，所以將13壓入輔助棧

          stackData：   13  1  9  5】 

           index指向下一個元素2

             [5   9   1   8    13     4   2    7]

     3  遍歷第3個元素是13，它等於是stackData中的top元素13，說明沒有新壓入元素，只是彈出元素，所以輔助棧需要彈出top元素13

          stackData：  1  9  5】     

    4  遍歷第4個元素是1，它等於現在stackData中的top元素1，說明沒有新壓入元素，只是彈出元素，所以輔助棧需要彈出top元素1

         stackData：    9  5】     

   5  遍歷第5個元素是5，它不等於現在stackData中的top元素9，說明它可能是新壓入的元素，也可能是輔助棧中的元素

          情況1：如果是新壓入的元素，那麼出棧順序到現在為止還是正確的

           情況2：如果是輔助棧中的元素（已經知道不是首元素），就可以知道出棧序列是錯誤的，因為如果是輔助棧中的元素，出棧順序必須和輔助棧一致，也就是必須是先9後5

           問題的關鍵是怎麼判斷這種情況是情況1還是情況2

         可以這樣做，將這種情況看做是情況1，那麼需要繼續向輔助棧中壓入元素，但是會發現將壓棧序列中全部元素都壓入輔助棧後依然找不到一個元素等於當前遍歷元素5   

           在第2步後，index已經指向了2

         （1）   [5   9   1   8    13     4   2   7]   index指向元素2不等於元素5 ，將2壓入輔助棧

          （2）   [5   9   1   8    13     4   2    7]   index指向元素7不等於元素5 ，將7壓入輔助棧

           現在index已經指向了最後一個元素，但是沒有找到等於5的元素，那麼可以斷言，5其實是在輔助棧中的，這種情況屬於情況2，因此出棧序列是不正確的

四   偽代碼

     int index = 0

       for 遍歷出棧序列           

             if  （輔助棧不空 && 輔助棧top元素等於pPop[i]）                  

                      輔助棧彈出top元素

             else    //輔助棧為空 或者 top元素不等於pPop[i]，要壓入元素了

                  while（pPush[index] 不等於 pPop[i]） //只壓入pPop[i]之前的元素，本身不壓入

                         輔助棧壓入pPush[index] 元素 

                         index++

                   if （index 等於 length）//說明沒有找到這個元素標記，pPop[i]一定在輔助棧中，出棧序列錯誤

                             return false

                   else

                             index++ //要指向下一個元素

       return  true  //for 迴圈能正常結束，出棧序列就一定是正確的

 五  代碼

       1   C++版本

 1 bool isStackOutRight(int *stackIn,int *stackOut,int length){    
 2       stack<int>  stackData;//輔助棧
 3       int index(0);        
 4          for (int i = 0;i<length;i++){//遍歷整個出棧序列
 5   
 6              if (!stackData.empty() && stackData.top() == stackOut[i]) //輔助棧不空，而且遍歷的元素是輔助棧的top元素，需要彈出操作             
 7                      stackData.pop();                                     
 8              else {  //輔助棧為空，或者不等於首元素，指向壓棧操作
 9                  while(index<length && stackIn[index] != stackOut[i])
10                     stackData.push(stackIn[index++]);
11                 if (index == length)//這裡是關鍵，說明在壓棧序列中從index開始往後遍歷，沒有找到該元素，該出棧序列不正確
12                     return false;
13                 else 
14                     index++;
15             }
16         }
17         return true;//整個for迴圈能正常結束（沒有遇到return false），說明出棧序列正確
18  }