一、什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

特点：后进先出

二、Java虚拟机栈

（1）栈帧：调用函数是为其开辟的内存叫栈帧。

三、Java基本库中栈的基本使用

public static void main(String[] args) {
    
        Stack<Integer> stack= new Stack<Integer>();
        //入栈
        stack.push(3);//栈底
        stack.push(4);
        stack.push(5);
        stack.push(7);//栈顶
        //出栈：弹出栈顶元素
        System.out.println(stack.pop());//7
        //再弹一次，此时栈顶元素为5了，如下。
        System.out.println(stack.pop());
        //获取栈顶元素但不删除,这时的栈顶元素以及是4了
        System.out.println(stack.peek());
        //判断栈顶元素是否为空
        System.out.println(stack.empty());
        Stack<Integer> stack1=new Stack<>();
        System.out.println(stack1.empty());
        //获取栈中的元素的位置，栈顶为1号，此时stack中有3,4两个元素，所以4元素的位置为1号
        System.out.println(stack.search(4));
        //使用父类的方法，stack继承自Vector
        System.out.println(stack.isEmpty());
    }

四、中缀表达式、后缀表达式、前缀表达式的转化。

（1）、后缀表达式求值：

逆波兰表达式求值：

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)）//通过Integer的方法转成数字;
        }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;
    }

五、用顺序表实现一个栈

//利用顺序表实现一个栈
class MyStack{
    

    private int[] array=new int[5];//假设这是存放5个元素的栈。
    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();
        //入栈
        myStack.push(5);
        myStack.push(6);
        myStack.push(8);
        myStack.push(3);
        myStack.push(2);
        //计算此时栈的长度
        System.out.println(myStack.getSize());
        //弹出栈顶元素2
        System.out.println(myStack.pop());
        //弹出栈顶元素3
        System.out.println(myStack.pop());
        //弹出栈顶元素8，但不删除
        System.out.println(myStack.peek());
        //判断栈是否为空
        System.out.println(myStack.isEmpty());
        //新创一个栈，不放元素
        MyStack myStack1=new MyStack();
        System.out.println(myStack1.isEmpty());
    }
}

六、括号匹配问题

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;
    }
}

七、判断某个数组是否是正确的出栈顺序。

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();
    }
}

八、设计一个获取栈中最小元素的栈

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();
    }
}