数据结构：栈

栈：

栈的定义：

一种特殊的线性表，其只允许从其中一端进行删除和插入数据的操作，进行数据插入和删除的操作的一端叫做栈顶，另一端称为栈底，栈中的元素都遵循先出后进的原则

压栈：数据的插入操作叫做进栈/压栈/入栈，插入的数据在栈底。

出栈：数据的删除操作叫做出栈，出栈的数据在栈顶。

 栈的使用：

栈的模拟实现： 

知道了栈的功能后，我们模拟实现这些功能：

public class Mystack {
    int[] elem;//顶一个数组
    int usesize;//用来求栈内的有效元素的长度
    public Mystack(){//构造方法
        elem=new int[10];
    }
    private boolean isFull(){
        return elem.length==usesize;
    }
    public int push(int data){//入栈的方法
        if(isFull()){
           elem= Arrays.copyOf(elem,2*elem.length);
        }else{
            elem[usesize++]=data;
        }
        return data;
    }
    public int pop(){//出栈的方法
        if(Empty()){
            throw new EmptyException("栈内元素为空");//抛一个异常
        }
        int tem=elem[usesize-1];
        usesize--;
        return tem;
    }
    public int peek(){//获得栈顶的方法
        if(Empty()){
            throw new EmptyException("栈内元素为空");//抛一个异常
        }
        return elem[usesize-1];
    }
    public int size(){//求栈内有效元素的个数
        return usesize;
    }
    public boolean Empty(){//判断栈内是否为空
        return usesize==0;
    }
}

栈的应用场景：

问题1：括号匹配：

20. 有效的括号 - 力扣（LeetCode）

要求：

 这个题，我们用栈来解决：

public boolean isValid(String s) {
        Stack<Character> stack=new Stack<Character>();
       
        for(int i=0;i<s.length();i++){//遍历字符串
             char ch=s.charAt(i);//拿到每单个括号
            if(ch=='(' || ch=='[' || ch=='{'){//判断是不是左括号
                stack.push(ch);
            }else{//不是左括号的情况
                if(stack.isEmpty()){//栈为空，但字符串没有遍历完
                    return false;
                }
                if(ch==')'&&stack.peek()=='('||ch==']'&&stack.peek()=='['||ch=='}'&&stack.peek()=='{'){//判断左右括号是否匹配
                   stack.pop();
                }else{//括号不匹配
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){//字符串遍历完了，但是栈中还有括号
                return false;
            }
           return true;
    }

 问题2：逆波兰表达式求值：

150. 逆波兰表达式求值 - 力扣（LeetCode）

 public int evalRPN(String[] tokens) {
      Stack<Integer> stack=new Stack<Integer>();
            for(String st : tokens){//开始遍历字符串
                if(!isoperter(st)){//如果不为运算符
                    int x=Integer.parseInt(st);
                    stack.push(x);
                }else{//遍历到数字字符时
                    int x1=stack.pop();
                    int x2=stack.pop();
                    switch(st){
                        case "+":stack.push(x2+x1);
                        break;
                        case "-":stack.push(x2-x1);
                        break;
                        case "*":stack.push(x2*x1);
                        break;
                        case "/":stack.push(x2/x1);
                        break;
                    }
                }
            }
            return stack.peek();//最后运算结果
        }

        private boolean isoperter(String ch){//判断字符是否是运算字符
            if(ch.equals("+")||ch.equals("-")||ch.equals("*")||ch.equals("/")){
                return true;
            }
            return false;    
        }

问题3：栈的压入，弹出序列：

 public boolean IsPopOrder (int[] pushV, int[] popV) {
     Stack<Integer> stack=new Stack<Integer>();
     int j=0;
     for(int i=0;i<pushV.length;i++){//遍历popV
        stack.push(pushV[i]);//压栈
        while(!stack.isEmpty()&&j<popV.length&&stack.peek()==popV[j]){//判断栈顶元素和popV[j]是否相同
            stack.pop();
            j++;
        }
     }
     return stack.isEmpty();  //栈是否为空，作为返回结果
    }

 问题4：最小栈

155. 最小栈 - 力扣（LeetCode）

class MinStack {
Stack<Integer> stack;
Stack<Integer> minstack;
    public MinStack() {
        stack=new Stack<>();
        minstack =new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minstack.isEmpty()){
            minstack.push(val);
        }else{
            if(val<=minstack.peek()){
            minstack.push(val);
        }
        }
        
    }
    
    public void pop() {
        if(stack.isEmpty()){
            return ;
        }
        int ret=stack.pop();
        if(minstack.isEmpty()){
            return ;
        }
        if(ret==minstack.peek()){
            minstack.pop();
        }
    }
    
    public int top() {
        if(stack.isEmpty()){
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minstack.isEmpty()){
            return -1;
        }
        return minstack.peek();
    }
}