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

这篇文章主要介绍了关于 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中文网其他相关文章！