One 、 What is stack?

Stack ： A special linear table , It only allows the insertion and deletion of elements at the fixed end . The end at which data is inserted and deleted is called the top of the stack , The other end is called the bottom of the stack .

characteristic ： Last in, first out

Two 、Java Virtual machine stack

（1） Stack frame ： The memory for which the function is called is called stack frame .

3、 ... and 、Java Basic use of stack in basic library

public static void main(String[] args) {
    
        Stack<Integer> stack= new Stack<Integer>();
        // Push 
        stack.push(3);// At the bottom of the stack 
        stack.push(4);
        stack.push(5);
        stack.push(7);// To the top of the stack 
        // Out of the stack ： Pop up top element 
        System.out.println(stack.pop());//7
        // Play it again , At this point, the top element of the stack is 5 了 , as follows .
        System.out.println(stack.pop());
        // Get the top element of the stack without deleting , At this time, the top element of the stack is 4 了 
        System.out.println(stack.peek());
        // Determine whether the stack top element is empty 
        System.out.println(stack.empty());
        Stack<Integer> stack1=new Stack<>();
        System.out.println(stack1.empty());
        // Get the position of the element in the stack , The top of the stack is 1 Number , here stack There is 3,4 Two elements , therefore 4 The location of the element is 1 Number 
        System.out.println(stack.search(4));
        // Use the method of the parent class ,stack Inherited from Vector
        System.out.println(stack.isEmpty());
    }

Four 、 Infix expression 、 Postfix expression 、 Conversion of prefix expression .

（1）、 Suffix expression evaluation ：

Evaluate the inverse Polish expression ：

Stack<Integer> stack=new Stack<>();
    public int evalRPN(String[] tokens) {
    
        for(int i=0;i<tokens.length;i++){
    
        String val=tokens[i];
        if(isOperation(val)==false){
    
            stack.push(Integer.parseInt(val)）// adopt Integer Turn your method into numbers ;
        }else {
    
            int num2=stack.pop();
            int num1=stack.pop();
            switch(val){
    
                 case "+":
                        stack.push(num1+ num2);
                        break;
                 case "-":
                        stack.push(num1- num2);
                        break;
                 case "*":
                        stack.push(num1 * num2);
                        break;
                  case "/":
                     stack.push(num1/ num2);  
                   break;
                default:
            }
        }
    }
    return stack.pop();
    }
    private boolean isOperation(String x){
    
        if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
    
        return true;
    }
    return false;
    }

5、 ... and 、 Realize a stack with a sequence table

// Use the sequence table to realize a stack 
class MyStack{
    

    private int[] array=new int[5];// Suppose this is a storage 5 A stack of elements .
    private int size=0;
    public void push(int value){
    
        this.array[size]=value;
        size++;
    }
    public int pop(){
    
        int ret=this.array[size-1];
        size--;
        return ret;
    }
    public int peek(){
    
        int ret=this.array[size-1];
        return ret;
    }
    public boolean isEmpty(){
    
        if (size==0){
    
            return true;
        }
        return false;
    }
    public int getSize(){
    
        return size;
    }

}
public class Demo3 {
    
    public static void main(String[] args) {
    
        MyStack myStack=new MyStack();
        // Push 
        myStack.push(5);
        myStack.push(6);
        myStack.push(8);
        myStack.push(3);
        myStack.push(2);
        // Calculate the length of the stack at this time 
        System.out.println(myStack.getSize());
        // Pop up top element 2
        System.out.println(myStack.pop());
        // Pop up top element 3
        System.out.println(myStack.pop());
        // Pop up top element 8, But don't delete 
        System.out.println(myStack.peek());
        // Judge whether the stack is empty 
        System.out.println(myStack.isEmpty());
        // Create a new stack , Don't put elements 
        MyStack myStack1=new MyStack();
        System.out.println(myStack1.isEmpty());
    }
}

6、 ... and 、 Bracket matching problem

public class Demo4 {
    
    public static void main(String[] args) {
    
        Scanner scanner=new Scanner(System.in);
        String str=scanner.nextLine();
        System.out.println(isValid(str));
    }
    public static boolean isValid(String s) {
    
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
    
            char ch=s.charAt(i);
            if(ch=='('||ch=='['||ch=='{'){
    
                stack.push(ch);
            }else{
    
                if(stack.empty()){
    
                    return false;
                }
                char top=stack.peek();
                if(top=='('&&ch==')'||top=='{'&&ch=='}'||top=='['&&ch==']'){
    
                    stack.pop();
                }else{
    
                    return false;
                }

            }
        }
        if(!stack.empty()){
    
            return false;
        }
        return true;
    }
}

7、 ... and 、 Determine whether an array is the correct stack order .

public class Demo5 {
    
    public static void main(String[] args) {
    
        int[] A={
    1,2,3,4,5};
        int[] B={
    4,5,3,2,1};
        System.out.println(IsPopOrder(A, B));
    }
    public static boolean IsPopOrder(int [] pushA,int [] popA) {
    
        Stack <Integer> stack=new Stack<>();
        int j=0;
        for(int i=0;i<pushA.length;i++){
    
            stack.push(pushA[i]);
            while(j<popA.length&&!stack.empty()&&stack.peek()==popA[j]){
    
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

8、 ... and 、 Design a stack to get the smallest element in the stack

class MinStack {
    
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
    
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    
    public void push(int val) {
    
        stack.push(val);
        if(!minStack.empty()){
    
            int top=minStack.peek();
            if(val<=top){
    
                minStack.push(val);
            }
        }else{
    
            minStack.push(val);
        }
    }
    
    public void pop() {
    
        int popVal=stack.pop();
        if(!minStack.empty()){
    
            int top=minStack.peek();
            if(top==popVal){
    
                minStack.pop();
            }
        }
    }
    
    public int top() {
    
        return stack.peek();
    }
    
    public int getMin() {
    
        return minStack.peek();
    }
}