一、題目鏈接

棧的壓入、彈出序列

二、題目

三、算法原理：用一個棧模擬入棧出棧的過程

• 思路：用一個棧模擬入棧出棧的過程，模擬出與第二個序列一樣的序列就合法，模擬不出與第二個序列一樣的序列就不合法。

給出兩個下標pushi、popi分別指向入棧序列和出棧序列。（index：下標）

步驟：

1. pushi指向的數據入棧，入棧后pushi++
2. "持續比較"棧頂數據和popi指向的數據（因為有剛入棧的數據就出棧的可能，沒有確定的出棧順序，所以就要持續比較）。若相等，"持續"出數據，出一個數據popi就++；若不相等或者棧為空，執行步驟1。

• 匹配案例演示，示例1：

• 不匹配案例演示，示例2：

循環結束條件是兩個下標都越界嗎？popi在合法的序列下是一定能走到最后的，但是popi在非法的序列下一定到不了最后，所以popi是否能走到最后面是不確定的。但是pushi一定能走到最后面，即循環結束條件。

如何判斷入棧序列和出棧序列是否匹配？棧為空或者popi走到尾，兩個條件選一個即可，因為兩個條件會同時存在：棧為空，所有的數據都入棧了，棧為空一定是因為與出棧序列匹配，所有數據都出棧了，popi也走到了最后；popi走到尾，表示此時棧中數據都出棧了，棧一定為空。

"內存超限或者超時"的問題有兩種可能性：代碼有問題、死循環。入棧后要pushi++。

四、編寫代碼

在調用top前先判空，順序不能顛倒，棧為空時直接取top元素會崩潰：

class Solution {
public:/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布爾型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// 用一個棧模擬入棧出棧的過程stack<int> st;// 持續比較棧頂元素和popi指向的元素：若相等，持續出棧，popi++;若不相等或棧為空，執行步驟1size_t pushi = 0, popi = 0;while (pushi < pushV.size()){st.push(pushV[pushi++]);while (!st.empty() && st.top() == popV[popi]) st.pop(), popi++;}return st.empty();}
};