棧的壓入、彈出序列

題目描述

輸入兩個(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就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）。

思路

1. 借用一個(gè)輔助的棧，將原數(shù)列依次壓入輔助棧，棧頂元素與所給的出棧隊(duì)列相比，如果相同則出棧；
2. 如果不同則繼續(xù)壓棧，知道原數(shù)列中所有的數(shù)字壓棧完畢；
3. 檢測(cè)輔助棧中是否為空， 若空，則該序列是壓棧序列對(duì)應(yīng)的一個(gè)彈出序列。否則，說(shuō)明序列不是該棧的彈出序列。

舉例
入棧：1，2，3，4，5
出棧：4，5，3，2，1
1） 1入輔助棧，此時(shí)1≠4；
2） 2入輔助棧，此時(shí)2≠4；
3） 3入輔助棧，此時(shí)3≠4；
4） 4入輔助棧，此時(shí)4＝4，輔助棧出棧，剩下 1，2，3；同時(shí)，彈出序列向后一位，為5；此時(shí)3≠5，繼續(xù)壓棧；
5） 5入輔助棧，此時(shí)5=5，輔助棧出棧，剩下1，2，3；同時(shí)，彈出序列向后一位，為3；
6） 此時(shí)3=3，輔助棧出棧，剩下1，2；同時(shí)彈出序列向后一位，為2；
7） 此時(shí)2=2，輔助棧出棧，剩下1；同時(shí)彈出序列向后一位，為1；
8） 此時(shí)1=1，輔助棧出棧，為空，所以該序列是壓棧序列對(duì)應(yīng)的一個(gè)彈出序列。

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

function IsPopOrder(pushV, popV)
{
    if(pushV.length === 0 || popV.length === 0){
        return;
    }
    var temp = [];
    var popIndex = 0;
    for(var i=0;i<pushV.length;i++){
        temp.unshift(pushV[i]);
        while(temp.length && temp[0] === popV[popIndex]){
            temp.shift();
            popIndex++;
        }
    }
    return (temp.length === 0);
}
module.exports = {
    IsPopOrder : IsPopOrder
};