这篇文章主要介绍了关于 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
辅助栈最终为空,程序结束
相关推荐:
以上是 php实现栈的压入以及弹出序列的详细内容。更多信息请关注PHP中文网其他相关文章!