Press in and pop-up sequence of "Niuke | daily question" stack

Author's brief introduction ： One likes to write , Sophomore rookie of planning major

Personal home page ：starry Lu Li

First date ：2022 year 7 month 14 Thursday, Sunday

Last article ：『 Cattle guest | A daily topic 』 Template stack

Subscription column ：『 Collection of Niuke brush questions 』

Daily recommendation ： Basic algorithm is a very important part in both graduate interview and job interview , Here we recommend an algorithm interview artifact ： Cattle from - Interview artifact ; Algorithm problems can only be kept thinking and feeling by brushing more and more frequently , Let's move quickly （ reminder ： The common interview question bank is also very nice Oh ）

If the article helps you, remember to praise + Collect and support

1. A daily topic

2. Method 1 ： Auxiliary stack

2.1 Thought analysis

The topic requires us to judge whether the two sequences conform to the order of entering and leaving the stack , We can Simulate with a stack . For the stack sequence , As long as the stack is empty , The sequence must be stacked in turn . When will you come out ？ Naturally Encountered an element equal to the current stack sequence , Then we'll give up entering the stack , Let it come out first .

 // Push ： The stack is empty or the top element of the stack is not equal to the out of stack array ( Note that the array is also controlled to be out of bounds j<n)
while(j<n&&(stack.isEmpty()||stack.peek()!=popA[i])){
    
    stack.push(pushA[j++]);
}

2.2 specific working means

• step 1： Prepare one Auxiliary stack , Two subscripts access two sequences respectively .
• step 2： The auxiliary stack is empty or the top of the stack is not equal to the current element of the out of stack array , Continue to add the stack array to the stack .
• step 3： The top of the stack is equal to the current element of the stack array Out of the stack .
• step 4： When the stack array is accessed , The out of stack array cannot be ejected in turn , It just doesn't match , Otherwise, the two sequences will match after they are accessed .

2.3 Code solution

import java.util.*;
import java.util.ArrayList;

public class Solution {
    
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    
        // Number of elements 
        int n=pushA.length;
        // Auxiliary stack 
        Stack<Integer>stack=new Stack<Integer>();
        // Traverse the subscript of the stack 
        int j=0;
        // Traverse the stack array ,i Subscript the stack array 
        for(int i=0;i<n;++i){
    
            // Push ： The stack is empty or the top element of the stack is not equal to the out of stack array ( Note that the array is also controlled to be out of bounds j<n)
            while(j<n&&(stack.isEmpty()||stack.peek()!=popA[i])){
    
                stack.push(pushA[j++]);
            }
            // The element at the top of the stack is equal to the element in the stack array 
            if(stack.peek()==popA[i]){
    
                stack.pop();
            }else{
    // Otherwise, it is a mismatched sequence 
                return false;
            }
        }
        return true;
    }
}

3. Method 2 ： In situ stack

3.1 Thought analysis

In method 1, we use an auxiliary stack to simulate , however Arrays are very similar to stacks ah , Use subscripts to indicate the top of the stack . In method 1 push The first half of the array is stacked , It's useless. , This part of the space can be used as a stack . The principle is the same as the method , Just then we traverse push When you have an array , Use subscript n Represents stack space ,n The position of the stack is the top element .

3.2 specific working means

• step 1： use Subscript i Represents stack space , use j Indicates the subscript of the stack sequence .
• step 2： Traverse every element to be put on the stack , Join the top of the stack , namely push Array i The location of , At the same time, increase the size of stack space , namely i Size .
• step 3： When If the stack is not empty, it means the top of the stack i Greater than or equal to 0, And the top of the stack is equal to the current stack sequence , Out of the stack , At the same time, reduce the space of the stack , That is to reduce i.
• step 4： Finally, if Stack space size i by 0, On behalf of all stack completion , Otherwise it doesn't match .

3.3 Code solution

import java.util.*;
import java.util.ArrayList;

public class Solution {
    
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    
        // The size of stack space 
        int i=0;
        // Out of stack sequence subscript 
        int j=0;
        // Traversing stack array 
        for(int a:pushA){
    
            // Add elements to the top of the stack 
            pushA[i]=a;
            // When the stack is not empty and the top element of the stack is equal to the out of stack array element 
            while(i>=0&&pushA[i]==popA[j]){
    
                j++;
                // Element out of stack , Reduce stack space 
                i--;
            }
            // Prepare for the next element stack 
            i++;
        }
        // The size of stack space is 0 Explain that all elements are out of the stack 
        return i==0;
    }
}

Daily recommendation ： Basic algorithm is a very important part in both graduate interview and job interview , Here we recommend an algorithm interview artifact ： Cattle from - Interview artifact ; Algorithm problems can only be kept thinking and feeling by brushing more and more frequently , Let's move quickly （ reminder ： The common interview question bank is also very nice Oh ）