Sword finger offer 30 contains the stack of Min function

Still stack , Because I did it first 09, So when looking at this question , Priority has been given to the use of dual stacks , Similarly, the first stack is the data stack , The second stack is the auxiliary stack （ Smallest stack ）

The comment of this question is in the solution , Animation given by the boss 、 Vernacular inscriptions are more popular 、 detailed , Here I write it simply , If you can understand

First Understand data stack and auxiliary stack （ Smallest stack ） The role of , seeing the name of a thing one thinks of its function , Data stack means that all elements are pushed into the data stack , The minimum stack is the minimum value of the element in the data stack after each input element in the data stack , As shown in the figure

When the initial , Push elements into the data stack 2

After pressing , Because there is only one element in the data stack 2 , Then the smallest element in the smallest stack is 2

Push in an element again 3 , At this time, there is 2、3 Two elements

At this time, the minimum stack is the minimum value of the element in the data stack , At this time, there is only 2、3 Two elements , The minimum value is 2, Then continue to push elements into the minimum stack 2

If you continue to push elements into the data stack 1 , So at this time The data stack element is ：2、3、1

Then the minimum value of the three elements in the data stack becomes 1, So the data pushed into the minimum stack is 1

Through such steps, we can find , The top element of the smallest stack is always the smallest element in the data stack  

So we can judge , To write push Methods

and pop Double stack elements pop

top Then the top element of the data stack is returned

min According to the red summary above , Is returned The top element of the smallest stack

Write the code according to the idea

class MinStack {

    Stack<Integer> data_stack;
    Stack<Integer> min_stack;

    /** initialize your data structure here. */
    public MinStack() {
        data_stack = new Stack<>();
        min_stack = new Stack<>();
    }
    
    public void push(int x) {
        if(min_stack.isEmpty()){ // The minimum stack is empty , It indicates that the data stack is also empty , Then press the element into the minimum stack 
            min_stack.push(x);
        }else{ // Minimum stack is not empty , Note that the data stack is not empty , And the smallest stack top element is the smallest element of the data stack , Then judge and compare 
            if(min_stack.peek() > x){ // The top element of the smallest stack  > x , explain  x  smaller , It should be pushed into the minimum stack 
                min_stack.push(x);
            }else{
                // The top element of the smallest stack  < x , explain  x  Bigger , Then the smallest stack is pressed into the smallest element recorded last 
                min_stack.push(min_stack.peek());
            } 
        }
        data_stack.push(x);  
    }
    
    public void pop() {
        data_stack.pop();
        min_stack.pop();
    }
    
    public int top() {
        return data_stack.peek();
    }
    
    public int min() {
        return min_stack.peek();
    }
}

There needs to be a difference pop() and peek()

pop() Is the element that returns to the top of the stack , And delete it in the process .

peek() Is to return the element at the top of the stack , But don't delete it from the stack .

isEmpty() Is to judge whether it is empty , If the stack is empty , Then return to true, If the stack contains elements , Then return to false