題干
輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序跋理，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序择克。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列「1前普，2肚邢，3，4拭卿，5」是某棧的壓棧序列骡湖，序列「4，5峻厚，3响蕴，2，1」是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列惠桃，但「4浦夷，3获枝，5伊约，1议薪，2」就不可能是該壓棧序列的彈出序列陵叽。
解題思路
如果下一個(gè)彈出的數(shù)字剛好是棧頂數(shù)字，那么直接彈出肥缔，如果下一個(gè)彈出的數(shù)字不在棧頂莲兢，則把壓棧序列中還沒有入棧的數(shù)字壓入輔助棧，直到把下一個(gè)需要彈出的數(shù)字壓入棧頂為止续膳；如果所有數(shù)字都?jí)喝霔：笕匀粵]有找到下一個(gè)彈出的數(shù)字改艇，那么該序列不可能是一個(gè)彈出序列。
代碼實(shí)現(xiàn)
<?php
function isPopOrder($in, $out)
{
if (empty($in) || empty($out) || count($in) != count($out)) {
return false;
}
$arr = [];
$inIdx = 0;
$outIdx = 0;
$inCount = count($in);
$outCount = count($out);
while ($outIdx < $outCount) {
while (empty($arr) || $arr[0] != $out[$outIdx]) {
if ($inIdx == $inCount) {
break;
}
array_unshift($arr, $in[$inIdx]);
$inIdx++;
}
if ($arr[0] != $out[$outIdx]) {
break;
}
array_shift($arr);
$outIdx++;
}
if (empty($arr) && $outIdx == $outCount) {
return true;
}
return false;
}
var_dump(isPopOrder([1,2,3,4,5], [5,4,3,2,1]));
var_dump(isPopOrder([1,2,3,4,5], [4,5,3,2,1]));
var_dump(isPopOrder([1,2,3,4,5], [5,4,3,1,2]));
