JZ31 棧的壓入、彈出序列

描述

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有數字均不相同

方法1 輔助棧（推薦使用）

思路：

題目要我們判斷兩個序列是否符合入棧出棧的次序，我們就可以用一個棧來模擬。對於入棧序列，只要棧為空，序列肯定要依次入棧。那什麼時候出來呢？自然是遇到一個元素等於當前的出棧序列的元素，那我們就放棄入棧，讓它先出來。
//入棧：棧為空或者棧頂不等於出棧數組
while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
    q.push(pushA[j]);
    j++;
}

如果能按照這個次序將兩個序列都訪問完，那說明是可以匹配入棧出棧次序的。

具體做法：

step 1：準備一個輔助棧，兩個下標分別訪問兩個序列。
step 2：輔助棧為空或者棧頂不等於出棧數組當前元素，就持續將入棧數組加入棧中。
step 3：棧頂等於出棧數組當前元素就出棧。
step 4：當入棧數組訪問完，出棧數組無法依次彈出，就是不匹配的，否則兩個序列都訪問完就是匹配的。

代碼

public boolean IsPopOrder(int[] pushA, int[] popA) {
      Stack<Integer> q = new Stack<>();
      int n = pushA.length;
      //記錄進棧位置
      int j = 0;

      for (int i = 0; i < n; i++) {
          while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
              q.push(pushA[j]);
              j++;
          }

          if (q.peek() == popA[i]) q.pop();
          else return false;
      }
      return true;
  }

方法2 原地棧（擴展思路）

思路：

方法一我們使用了一個輔助棧來模擬，但是數組本來就很類似棧啊，用下標表示棧頂。在方法一種push數組前半部分入棧了，就沒用了，這部分空間我們就可以用來當成棧。原理還是同方法一一樣，只是這時我們遍歷push數組的時候，用下標n表示棧空間，n的位置就是棧頂元素。

具體做法：
step 1：用下標n表示棧空間，用j表示出棧序列的下標。
step 2：遍歷每一個待入棧的元素，加入棧頂，即push數組中n的位置，同時增加棧空間的大小，即n的大小。
step 3：當棧不為空即棧頂n大於等於0，且棧頂等於當前出棧序列，就出棧，同時縮小棧的空間，即減小n。
step 4：最後若是棧空間大小n為0，代表全部出棧完成，否則不匹配。

代碼

package mid.JZ31棧的壓入彈出序列;

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        //初始化棧
        int n = 0;
        //出棧元素位置
        int j = 0;

        for (int i = 0; i < popA.length; i++) {
            //當前push元素入棧
            pushA[n] = pushA[i];
            //出棧
            while (n >= 0 && pushA[n] == popA[j]){
                n--;
                j++;
            }
            n++;
        }
        return n == 0;
    }
    /*public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> q = new Stack<>();
        int n = pushA.length;
        //記錄進棧位置
        int j = 0;

        for (int i = 0; i < n; i++) {
            while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
                q.push(pushA[j]);
                j++;
            }

            if (q.peek() == popA[i]) q.pop();
            else return false;
        }
        return true;
    }*/
}