栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)


栈是先进后出的存储结构,一个元素在栈顶才能够弹出,题目中给定一个存入序列,求可能那些是弹出的序列,意思是按某个序列进行存入,中间由弹出套作。比如序列1,2,3,4,5,如果得到4,5,3,2,1的弹出序列。可以先压入1,2,3,4,此时4位于栈顶,可以弹出,然后压入5。此时5位于栈顶。弹出5.后面的3,2,1依次可以弹出,所以这个序列符合。但是4,3,5,1,2不行的原因是同样模拟后发现2在栈顶,1在2的下面,所以无法完成。综上所述可以构建一个辅助栈,就按照这个规则模拟,用一个索引i记录按给定顺序入栈的位置,用索引j记录弹出序列已经可以确认弹出元素的索引,只要弹出的序列不再栈顶就一直入栈,比如对于4,3,5,1,2来说将1,2,3,4压入辅助站,此时索引i等于3,然后循环弹出栈顶元素,同时j++。整个过程中可以发现,i的值和j的值只增加不减少,因为两个序列的长度一样。所以可以判断如果最后i的大小和j的大小相等并且i等于插入序列的大小(入栈序列已经完成)就由入栈序列可以得到出栈序列,如果i已经等于入栈序列长度,但是j没有。说明根据插入序列和栈的先入后出,只有位于栈顶元素才能弹出的特性,无法达到要求使得j的值增加,换句话说如果i的值增加到序列长度,说明已经入栈完毕了,剩余的操作只能按照入栈内当前已有的序列进行出栈,但是出栈的顺序却和期望输出不一致,类似于发证法一样同样说明不能由已知的入栈序列得到出栈序列。

function IsPopOrder($pushV, $popV)
{
    // write code here
    $temparray = array();
    $i = 0;
    $j = 0;
    while(1){
        while($popV[$j]!=end($temparray)&&$i<count($pushV)){
            $temparray[] = $pushV[$i++];
        }
        while($popV[$j]==end($temparray)&&$j<count($popV)){
            array_pop($temparray);
            $j++;
        }
        if($i==count($pushV)&&$j<count($pushV)){
            return false;
        }
        else if($i==count($pushV)&&$j==count($pushV)){
            return true;
        }
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容