首页  >  文章  >  后端开发  >  php实现栈的压入以及弹出序列

php实现栈的压入以及弹出序列

不言
不言原创
2018-05-08 09:25:071445浏览

这篇文章主要介绍了关于 php实现栈的压入以及弹出序列,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下

题目描述

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


  • 解题思路

    • 传入入栈序列,和出栈序列,我们使用一个栈作为辅助栈,遍历将入栈序列压入辅助栈,如果遍历时辅助栈不为空,且栈顶元素等于当前出栈元素 ,则弹出辅助栈元素。遍历结束后如果辅助栈为空则说明第二个序列是该栈的弹出顺序

  • 代码如下

<?php

function isPopOrder($pushValue, $popValue){    
$stack = new SplStack;    
$count = count($pushValue);

    for ($i = 0, $j = 0; $i < $count; $i++) {        
    $stack->push($pushValue[$i]);

        while (!$stack->isEmpty() && $stack->top() == $popValue[$j] && $j < $count) {            
        $stack->pop();            
        $j++;
        }
    }
    return $stack->isEmpty();
}

var_dump(isPopOrder([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]));

  • 实例解说

    • 进栈序列为 1,2,3,4,5 出栈序列为  4,5,3,2,1

    • 第一次遍历,明显 1 不等于 4 继续遍历,遍历 4 次到辅助栈站的栈内元素为1,2,3,4   栈顶元素为4

    • 把辅助栈栈顶元素弹出,将待出栈元素变为5

    • 这时辅助栈的栈内元素为1,2,3 栈顶元素为3,很明显3不等于待出栈元素5 ,我们继续遍历把 5 压入辅助栈

    • 正好这时待出栈元素为5 与栈顶元素相同,于是我们弹出栈顶元素,待出栈元素变为3

    • 再继续,栈顶元素此时为3 与待出栈元素相同,弹出栈顶元素

    • 此时栈顶元素变为2,待出栈元素变为2,继续弹出栈顶元素

    • 此时栈顶元素变为1,待出栈元素变为1 ,弹出栈顶元素

    • 由于辅助栈此时为空 跳出while

    • 由于此时入栈元素以全部进入辅助栈 跳出 for

    • 辅助栈最终为空,程序结束

    相关推荐:

    ThinkPHP实现附件上传功能

以上是 php实现栈的压入以及弹出序列的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn