<ul id="y6o0y"></ul>

【刷算法】棧的壓入、彈出序列

CarlBenjamin 發(fā)布于2019-08-22 18:17 / 1361人閱讀

摘要：題目描述輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。

題目描述

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

分析

其實(shí)該題就是考察一個進(jìn)棧序列能否和一個出棧序列對應(yīng)起來，但是棘手的地方在于：一個進(jìn)棧序列可能會有多個出棧的順序，所以還是得好好想一想。

可以從一個簡單的例子開始：

序列A：1,2,3

序列B：2,3,1

1先進(jìn)棧，B序列中未出棧的第一個數(shù)字是2，說明此時1不能再接著出棧；

2再進(jìn)棧，B序列中未出棧的第一個數(shù)字是2，說明第一個出棧的數(shù)字是2，那么2就此出棧；

此時棧頂元素為1，B序列中未出棧的第一個數(shù)字是1，說明1是自2出棧后的再一個出棧元素，那么1就此出棧，此時棧為空；

3繼續(xù)進(jìn)棧，此時B序列的中未出棧的第一個數(shù)字是3，說明3是再一個出棧元素，那么3就此出棧，此時棧為空，序列A也全都進(jìn)棧完畢了；

棧空了，序列A也進(jìn)棧完畢了，說明B就是A的彈出序列。

代碼實(shí)現(xiàn)

接著這個思路，可以試著寫代碼了

function IsPopOrder(pushV, popV)
{
    if(pushV.length === 0 || popV.length === 0 || pushV.length !== popV.length)
        return false;
    // 進(jìn)棧序列和出棧序列分別有一個指針，從頭開始
    var curPushIndex = 0, curPopIndex = 0;
    var stack = [];
    
    for(;curPushIndex < pushV.length;curPushIndex++) {
        
        stack.push(pushV[curPushIndex]);
        while(curPopIndex < popV.length && stack[stack.length-1] === popV[curPopIndex]){
        // 棧頂元素和當(dāng)前popIndex指向的數(shù)字一樣的話，stack彈出棧頂元素，且當(dāng)前popIndex指向pop序列的下一個數(shù)字
            stack.pop();
            curPopIndex++;
        }
    }
    // 棧中元素沒有全部彈出，說明兩個序列并不匹配，否則，就是匹配
    return stack.length === 0;
}