PHP는 스택 푸시 및 팝 시퀀스를 구현합니다.-PHP 튜토리얼-php.cn

PHP는 스택 푸시 및 팝 시퀀스를 구현합니다.

不言

풀어 주다： 2023-03-25 15:06:02

원래의

1471명이 탐색했습니다.

이 글은 주로 PHP 구현 스택의 푸시 및 팝업 시퀀스를 소개합니다. 이제 모든 사람과 공유합니다. 도움이 필요한 친구들은 이를 참조할 수 있습니다.

문제 설명

두 개의 정수 시퀀스를 입력하세요. 각 시퀀스는 스택의 푸시 시퀀스를 나타냅니다. 두 번째 시퀀스가 스택의 팝 시퀀스인지 확인하세요. 스택에 푸시된 모든 숫자가 동일하지 않다고 가정합니다. 예를 들어 1, 2, 3, 4, 5 시퀀스는 특정 스택의 푸시 시퀀스이고, 4, 5, 3, 2, 1 시퀀스는 다음과 같습니다. 스택에 해당하는 푸시 시퀀스입니다. 팝 시퀀스이지만 4, 3, 5, 1, 2는 푸시 시퀀스의 팝 시퀀스가 될 수 없습니다. (참고: 이 두 시퀀스의 길이는 동일합니다.)
시간 제한: 1초 공간 제한: 32768K1，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]));

로그인 후 복사