棧的壓入、彈出序列 -電腦資料

    題目描述

    輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序，

棧的壓入、彈出序列

。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

    解法：

    模擬棧的操作

    創(chuàng)建一個(gè)stack變量，表示入棧；

    如果stack為空，或者stack.top()==popV[i],stack.pop

    否則，stack.push(pushv【inpos])

   

bool IsPopOrder(vector<int> pushV, vector<int> popV) {    int size1 = pushV.size();    int size2 = popV.size();    if (size1 != size2||size1==0)        return false;    stack<int> st;    int inpos = 0;    for (int i = 0; i<size2;){        if (!st.empty() && st.top() == popV[i]){            st.pop();            i++;        }        else{            if (inpos < size1)                st.push(pushV[inpos++]);            else                return false;        }    }    return inpos == size1&&st.empty();}