preface

Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

Their thinking

  • The idea here is to think about the simulation stack
  • Let’s first define an array to simulate the stack
  • Pushed from the first element of the pushed array, if the element is in the first element of the popped array, we push the pushed element out of the stack, and then continue to determine whether the top element is the same as the element pointed to by the popped array pointer, and if so, we push the pushed element out.
  • If the number of elements in the simulated stack is zero, then it is the push and eject sequence of the stack, and vice versa.

The problem solving code

var validateStackSequences = function (pushed, popped) {

    // Stack stack stack stack stack stack stack stack stack
    const stack = [];
    // Define a pointer to the popped element
    let pointer = 0;

    for (let i = 0; i < pushed.length; i++) {
        stack.push(pushed[i]);
        if (popped[pointer] === pushed[i]) {
            stack.pop();
            pointer++;
        }
        if (pointer === popped.length) break;
        while (stack[stack.length-1] === popped[pointer]) {
            stack.pop();
            pointer++;
            if (pointer === popped.length) return true; }}while(stack.length ! = =0) {
        if(stack[stack.length - 1] === popped[pointer]) {
            stack.pop();
            pointer++;
        } else {
            return false; }}return true;
};
Copy the code

conclusion

  • This is a stack type problem.
  • The core idea is to think of the pressing and popping of the simulation stack and compare the elements pointed to by the pointer of popped. Finally, it can judge whether the stack is empty or not to judge whether it belongs to the pressing and popping of the stack.