剑指Offer - PHP栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
分析
- 借用一个辅助的栈，遍历压栈序列。
- 辅助栈先放入压栈序列的第一个，在判断是否和出栈序列的第一个值相等。
- 如果相等，则辅助栈弹出，然后压栈序列向后移动一位。然后继续比较辅助栈栈顶是否和出栈序列当前元素相等。
- 如果不相等，在继续将压栈序列压入辅助栈。
- 最后判断辅助栈是否为空，即全部弹出。是的话，说明出栈序列是弹出序列。
代码
<?php
namespace app\index\controller;
class Test
{
public function test()
{
$pushArr = [1, 2, 3, 4, 5]; // 入栈序列
$popArr = [4, 5, 3, 2, 1]; // 出栈序列
$length = count($pushArr); // 入栈的长度
$j = 0; // 出栈序列的下标
$stack = new \SplStack(); // 辅助栈
// 循环入栈序列
for ($i = 0; $i < $length; $i++) {
$stack->push($pushArr[$i]); // 先根据入栈序列压入辅助栈
// 出栈序列长度等于入栈序列长度 && 辅助栈栈顶等于出栈序列当前元素
while ($j < $length && $stack->top() == $popArr[$j]) {
$stack->pop(); // 弹出辅助栈栈顶
$j++; // 出栈序列指向下一个
}
}
// 如果辅助栈清空，说明 popArr 是弹出序列
if ($stack->isEmpty()) echo true;
echo false;
}
}笔记
SplStack 类：通过使用一个双向链表来提供栈的主要功能。
关于 LearnKu
粤公网安备 44030502004330号