PHP implements stack push and pop sequences

This article mainly introduces the push and pop-up sequence of the PHP implementation stack. It has a certain reference value. Now I share it with you. Friends in need can refer to it

Title description

Input two integer sequences. The first sequence represents the push sequence of the stack. Please determine whether the second sequence is the pop sequence of the stack. Assume that all numbers pushed onto the stack are not equal. For example, the sequence 1, 2, 3, 4, 5 is the push sequence of a certain stack, and the sequence 4, 5, 3, 2, 1 is the pop sequence corresponding to the push sequence. sequence, but 4, 3, 5, 1, 2 cannot be the pop-up sequence of the push sequence. (Note: The lengths of these two sequences are equal)
Time limit: 1 second Space limit: 32768K

• Solution ideas

• Pass in the push sequence and pop sequence. We use a stack as an auxiliary stack. The push sequence is pushed into the auxiliary stack during traversal. If the auxiliary stack is not empty during traversal, and the top element of the stack If it is equal to the current popped element, the auxiliary stack element will be popped. If the auxiliary stack is empty after the traversal, it means that the second sequence is the pop-up sequence of the stack

• The code is as follows

<?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]));

• Example explanation
  

• The push sequence is 1, 2, 3, 4, 5 Pop from the stack The sequence is 4, 5, 3, 2, 1

• for the first time traversal, obviously 1 is not equal to 4 Continue traversing, traverse 4 times to the auxiliary stack station. When the stack elements are 1, 2, 3, 4 and the top element of the stack is 4

• Pop the top element of the auxiliary stack and change the element to be popped into 5

• At this time, the element in the auxiliary stack is 1 , 2, 3 The top element of the stack is 3. Obviously 3 is not equal to the element to be popped 5. We continue to traverse 5 Push into the auxiliary stack

• At this time, the element to be popped out of the stack is 5, which is the same as the top element of the stack, so we pop the top element of the stack to be popped out of the stack The element becomes 3

• before continuing. The top element of the stack is now 3 which is the same as the element to be popped. Pop the top element of the stack

• At this time, the top element of the stack becomes 2, and the element to be popped becomes 2, and the top element of the stack continues to be popped

• At this time, the top element of the stack becomes 1, the element to be popped becomes 1, and the top element of the stack is popped

• Because the auxiliary stack is empty at this time, jump out of while

• Because all the elements pushed into the stack at this time have entered the auxiliary stack and jumped out for

• auxiliary stack Finally it is empty and the program ends

Related recommendations:

ThinkPHP implements the attachment upload function

The above is the detailed content of PHP implements stack push and pop sequences. For more information, please follow other related articles on the PHP Chinese website!