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

이 글은 주로 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]));

---

• 实例解说
  

• 进栈序列为 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

  ---
문제 해결 아이디어
푸시 시퀀스와 팝 시퀀스를 전달합니다. 푸시 시퀀스를 탐색하기 위해 스택을 보조 스택으로 사용합니다. 순회 중에 보조 스택이 비어 있지 않고 스택의 최상위 요소가 현재 팝된 요소와 같으면 보조 스택 요소가 팝됩니다. 순회 후 보조 스택이 비어 있으면 두 번째 시퀀스가 ​​스택의 팝업 시퀀스라는 의미
• 코드는 다음과 같습니다

rrreee

---

예시 설명


스태킹 순서는 1, 2, 3, 4, 5 팝 시퀀스는 4, 5, 3, 2, 1
🎜🎜첫 번째 순회는 분명히 1이 아닙니다. 4와 같음 계속해서 탐색하고, 스택의 요소는 1, 2, 3, 4입니다. 4, 🎜🎜🎜🎜 보조 스택 넣기 스택의 최상위 요소가 팝되며, 팝되는 요소는 5🎜🎜🎜🎜가 됩니다. 보조 스택의 요소는 1, 2, 3이고 스택의 최상위 요소는 3입니다. 분명히 3은(는) 스택 5에서 팝될 요소가 있으면 계속 순회하여 5를 보조 스택으로 푸시합니다🎜 🎜🎜🎜이 순간 팝될 요소는 5는 스택의 최상위 요소와 동일하므로 스택의 최상위 요소를 팝하고 팝할 요소는 3🎜🎜🎜🎜가 됩니다. 계속 , 스택의 최상위 요소는 이제 3이며 이는 팝될 요소와 동일합니다. 🎜🎜🎜🎜이때, 의 최상위 요소가 팝됩니다. 스택은 2가 되어 팝됩니다. 스택 요소는 2가 되며, 이때 스택의 최상위 요소가 계속해서 팝됩니다. 스택은 1이 되고, 팝될 요소는 1가 되므로 스택의 최상위 요소를 팝합니다 🎜🎜🎜🎜 이때 보조 스택은 비어 있으므로 점프 out of while🎜🎜🎜🎜 왜냐하면 이때 스택에 푸시된 모든 요소가 🎜🎜🎜🎜에 대한 보조 스택에서 튀어나오기 때문입니다. 보조 스택은 마침내 비워지고 프로그램이 종료됩니다🎜 🎜🎜🎜관련 권장 사항: 🎜🎜🎜 ThinkPHP는 첨부 파일 업로드 기능을 구현합니다🎜🎜🎜

위 내용은 PHP는 스택 푸시 및 팝 시퀀스를 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!